Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

optimal game strat


Best Answer Quantum.Mechanic, 08 August 2014 - 04:52 PM

After further study, I realized that the first path to a goal generated may not be the shortest path. It needs to keep generating goals until no new or shorter paths are found. It seems this doesn't happen all that often, so it hardly affects the runtime.

 

Eliminating some of the low level structure, the full matrix including paths can be saved, at least as high as 256. Judging by the memory usage, it could probably go a bit higher.

 

Here's the results I have for 256. Hopefully they pass all of plasmid's tests this time.

Spoiler for Results for 256

 

Here's the latest code.

Spoiler for Perl code
Go to the full post


  • Please log in to reply
29 replies to this topic

#21 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 08 August 2014 - 04:52 PM   Best Answer

After further study, I realized that the first path to a goal generated may not be the shortest path. It needs to keep generating goals until no new or shorter paths are found. It seems this doesn't happen all that often, so it hardly affects the runtime.

 

Eliminating some of the low level structure, the full matrix including paths can be saved, at least as high as 256. Judging by the memory usage, it could probably go a bit higher.

 

Here's the results I have for 256. Hopefully they pass all of plasmid's tests this time.

Spoiler for Results for 256

 

Here's the latest code.

Spoiler for Perl code

  • 0

#22 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 538 posts

Posted 08 August 2014 - 07:06 PM

well done guys.


  • 0

#23 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1431 posts
  • Gender:Male

Posted 09 August 2014 - 05:35 AM

The only potential pitfall I can think of is theoretical (at least I can't come up with a concrete example of it right now):

Suppose you start from A and need to reach D, which can be reached from B and C.
There's an optimal path from A to B in, say, four moves.
There's an optimal path from A to C in, say, five moves.
So it would look like it would take 4 moves to reach B, 5 to reach C, and therefore a total of 10 to reach D.

What if there were some number E that could be reached from A in two moves, and it would take five moves to reach B if E is included the path from A to B, and it would take six moves to reach C if E is included in the path from A to C. So E would not be included in the optimal paths to either B or C.

But suppose if you have both B and E in a set already (although such a set would never be formed by the algorithm because they don't form an optimal path), then you could reach C in two moves from {A, B, E}. Bear in mind that this still would involve a total path length from A to C of eight moves, which is far worse than the optimal five, so it would not be preserved as an optimal path.

That would create a possible path from A to D in 2 (A to E) + 4 ({A,E} to B) + 2 ({A,B,E} to C) + 1 ({A,B,C,E} to D) = 9 moves instead of 10.

I think that such a path might not be detected by this algorithm. But I'm not sure if such a scenario actually exists, or even if it's possible to prove that such a scenario cannot exist.
  • 0

#24 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 11 August 2014 - 11:03 AM

 

Suppose you start from A and need to reach D, which can be reached from B and C.
There's an optimal path from A to B in, say, four moves.
There's an optimal path from A to C in, say, five moves.
So it would look like it would take 4 moves to reach B, 5 to reach C, and therefore a total of 10 to reach D.

I think you've left something out here, or perhaps meant something else. For pedantic clarity, I'll say this anyway:

 

You didn't say how many moves it was from B to D, or C to D. If it's the same for both, let's say 1, then A->B->D = 4+1 = 5, and A->C->D = 5+1 = 6. So the optimal is A->B->D = 5. Paths don't simply add together -- any duplicate steps only count once.

 

The rest of your statement is worth consideration. The algorithm I use is greedy -- it only keeps the shortest path to any result. But I think it is provable that if there are 2 paths A->B->D = 5 and A->C->D = 4, it will pick the latter. While it might find A->B->D first, it still checks any other paths to D, and keeps generating paths to all results until no new results are added, and no shorter paths are found.

    # This result might already exist. Keep the new one if the path is shorter.   
    if (not exists($m->{$result})                                                 
     or (scalar keys %$new_path < scalar keys %{$m->{$result}})) {                
#         print STDERR "\tAdded $expression = $result\n";                          
        $m->{$result} = $new_path;                                                
        ++$results_added;                                                         

What you are proposing is that there's some way to get to a result E through a non-optimal path to D, that's shorter than the optimal path to D, plus D->E. I'm a little rusty on my proofs, but I think this falls into the "proof by contradiction" class.

 

Earlier versions of my program didn't do this, but instead stopped when the first path to a result was found. This depended on the generation order, which wasn't necessarily generating shortest path first, instead of the path order. So if a non-optimal path to D was found, it was kept, and no further paths to D were even checked for length.

 

On the other hand, I don't think it was ever stated explicitly if all paths could only go through numbers less than or equal to the limit value. There might be some edge cases where, say, an abundant number >> limit provides a path to a goal with fewer steps than any path <= limit.


  • 0

#25 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 11 August 2014 - 04:20 PM

Checking for paths that go above the limit (last number):

 

Not allowing any intermediate results above 25:

Steps for 14 => 25 (not in order):
        13 - 2 = 11
        14 + 11 = 25
        14 - 1 = 13
        1 + 1 = 2
        14 / 14 = 1

 

Allowing intermediate results above 25:

Steps for 14 => 25 (not in order):
        14 - 1 = 13
        13 + 13 = 26
        14 / 14 = 1
        26 - 1 = 25

So this is 1 shorter.

 

On a whim, I ran it with the max intermediate step = last**2, or 625 in this case, and found this path with 4 steps:

Path above 25 for (15,10):
        15 + 15 = 30
        450 / 45 = 10
        30 + 15 = 45
        30 * 15 = 450

Limiting search to 25*2 = 50, found this path with 5 steps:

Steps for 15 => 10 (not in order):
        1 + 1 = 2
        14 - 4 = 10
        15 - 1 = 14
        2 + 2 = 4
        15 / 15 = 1

I wonder how big the search range needs to be in relation to the last number to guarantee the optimal path?

 


  • 0

#26 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1431 posts
  • Gender:Male

Posted 12 August 2014 - 04:40 AM

Here's a concrete example.

I tried modifying the code so it generates a matrix of steps to get from each starting point to each goal, just like the matrix I posted earlier, and runs from 1 to 30 so I could directly compare the matrices they produce. They differ at some spots, one of which is the path going from 11 to 3. For some reason it took four steps and went 11/11=1, 11+11=22, 22/11=2, 2+1=3. Obviously a shorter path would be 11/11=1, 1+1=2, 1+2=3.

Apparently there are two equally short paths from 11 to 2: {11/11=1, 1+1=2} and {11+11=22, 22/11=2}, and the algorithm ended up storing the second path as the most efficient path to get to 2. However, since it didn't store the path to 2 that creates 1 as an intermediate rather than 22, it wasn't able to discover that you could reach 3 from a path going to 2 through 1 that had a useful intermediate already generated.
  • 1

#27 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 13 August 2014 - 04:55 PM

Here's a concrete example.

I tried modifying the code so it generates a matrix of steps to get from each starting point to each goal, just like the matrix I posted earlier, and runs from 1 to 30 so I could directly compare the matrices they produce. They differ at some spots, one of which is the path going from 11 to 3. For some reason it took four steps and went 11/11=1, 11+11=22, 22/11=2, 2+1=3. Obviously a shorter path would be 11/11=1, 1+1=2, 1+2=3.

Apparently there are two equally short paths from 11 to 2: {11/11=1, 1+1=2} and {11+11=22, 22/11=2}, and the algorithm ended up storing the second path as the most efficient path to get to 2. However, since it didn't store the path to 2 that creates 1 as an intermediate rather than 22, it wasn't able to discover that you could reach 3 from a path going to 2 through 1 that had a useful intermediate already generated.

 

Yes, that was possible for earlier versions. The current version gives me this:

four_banger.pl 30 11 3

[...snip...]

Steps for 11 => 3 (not in order):
        11 / 11 = 1
        1 + 1 = 2
        2 + 1 = 3

[...snip...]

because it compares multiple paths to the same goal, and keeps the shortest. (In case of ties, it takes the path with the smallest max operand.)


  • 0

#28 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1431 posts
  • Gender:Male

Posted 14 August 2014 - 04:26 AM

I was using the code from post #21; is there another version?
  • 0

#29 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 14 August 2014 - 11:57 AM

I was using the code from post #21; is there another version?

Are you sure? Because starting at line 193, it has:

    # This result might already exist. Keep the new one if the path is shorter.
    if (not exists($m->{$result})
     or (scalar keys %$new_path < scalar keys %{$m->{$result}})) {
        # print STDERR "\tAdded $expression = $result\n";
        $m->{$result} = $new_path;
        ++$results_added;
    }

  • 0

#30 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1431 posts
  • Gender:Male

Posted 14 August 2014 - 03:05 PM

Yep, using the version straight from the post and not the one I tweaked to output a matrix. That block even shows up if I show the code from the command line to make sure I didn't do something silly like forget to save the most recent version from the text editor. Ran it with command line parameters of 30 11 3 just like you did and I'm still getting the same four-step answer. Very bizarre that we're getting different answers from it; it should be completely deterministic.
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users