BrainDen.com - Brain Teasers

# Quantum.Mechanic

Members

90

1. ## Who can go the lowest?

Since the integer requirement, there haven't been any replies, so I'll go with an obvious, and not-likely-to-be-optimal one.

3. ## Probability of selecting two blue discs back to back

OK, I thought that would be a good little puzzle program to write. I'm sure there's an easier way to figure this on paper though, waiting for y'all to clue me in. The first few elements led me to the following:
4. ## Half as old as my brother

Are we assuming a mammalian birth process? Then splitting is in utero, and age origin is time of birth. When in Thailand...
5. ## Relatively prime

Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.
6. ## dice problem

Maximum sum, or highest numbered side?

9. ## The army of ants

I saw this puzzle in the same Peter Winkler book I mentioned elsewhere.

Testing a few targets other than 99,

I wrote a program to check.
12. ## optimal game strat

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; }
13. ## Prisoners sorting cards - this puzzle is not for the faint of heart

I just read an equivalent puzzle in a puzzle book, so I'll sit this one out...

15. ## optimal game strat

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.)
16. ## optimal game strat

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?
17. ## optimal game strat

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.
18. ## Lost in the jungle

If you give us a link, we might be able to visit the site and suggest other sites. I have always liked http://www.ferryhalim.com/orisinal/.
19. ## optimal game strat

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. Here's the latest code.
20. ## optimal game strat

Possibly not. One problem I've seen is that allowing intermediate numbers larger than the upper limit (e.g., 256) generates a lot of intermediate results of little use, which could be trimmed. And this is Perl, so the overhead for arrays and hashes is larger than you might expect. From http://perlmaven.com/how-much-memory-do-perl-variables-use, in bytes: size total_size SCALAR 24 24 ARRAY 64 64 HASH 120 120 Those are empty, unassigned variables. When the structure for each start number is filled out, it could be trimmed down to the useful bits and saved long term.
21. ## optimal game strat

Doh! Yes, of course. With path merging, there will be longer and shorter ways to get the same result. So I need to either run them all, and find the shortest; or generate in order by shortest new path length. The latter should be less space and less run time.
22. ## optimal game strat

OK, now I've added path merging, and fixed a bug where some paths didn't progress. (Thanks plasmid for checking my work.) Here's a run with 256, also printing out details for a worst start/goal pair of (195,170), and some other stats that might be interesting. Note that order is not preserved in the path listing. This can be done, but it takes more work, and is usually thrown away. Here's the code, much of it just for recording info for stats. Note that it has to dump the full list of paths after each start value. Otherwise, the memory blows up. I've also limited the upper end to twice the \$last value. There may be a few rare results that find a shorter path via a large power, but I can't prove or disprove this. Anyone have a counter example?
23. ## optimal game strat

I see now that my algorithm doesn't merge paths. I'll go off and chew on that a bit, and see what I can do.
24. ## optimal game strat

I wrote a Perl program. These results took about 5 minutes: The Perl program is below. To avoid blowing up memory, it only keeps the paths long enough to compute the worst one for each start. However, it is easily tweaked to keep the longest path for each start value. There is also a speedup by limiting paths to less than the square of the highest allowed starting value. This makes a few paths a bit longer, but doesn't seem to affect the overall results much.
25. ## optimal game strat

Just some random analysis... Any choice of start and goal can be a winner. If we have the matrix of shortest path lengths from each start to each goal, is it not the case that we would use some game theory, and randomly choose our start and goal values based on this matrix? For instance, if choosing a starting value of 23 has a 1% chance of winning, and 24 has a 0.1% chance of winning, we should choose 23 ten times more often than 24. But we should still choose 24 sometimes, to keep the opponent honest. While it might be interesting to note what the initial matrix looks like (what are good starting numbers and good goals), it seems the best approach is to iteratively generate start and goal vectors.
×