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

> time four_banger.pl 256 1 187 Best starts have 7 worst case steps: 2 => 87 3 => 139 4 => 107 5 => 183 6 => 165 7 => 234 <...and many more...> Worst starts have 8 worst case steps: 1 => 187 17 => 245 20 => 233 24 => 179 25 => 239 31 => 237 32 => 213 33 => 251 34 => 249 Best starts have 4.68 mean steps: 6, 4.68 mean steps 7, 4.70 mean steps 5, 4.70 mean steps 8, 4.73 mean steps 10, 4.78 mean steps 11, 4.79 mean steps 9, 4.80 mean steps 3, 4.82 mean steps 14, 4.85 mean steps Worst goals have 6.48 mean steps: 247, 6.48 mean steps 233, 6.47 mean steps 251, 6.46 mean steps 253, 6.39 mean steps 235, 6.38 mean steps 137, 6.38 mean steps <...and many more...> Steps for 1 => 187 (not in order): 4 + 1 = 5 192 - 5 = 187 16 * 12 = 192 1 + 1 = 2 2 + 1 = 3 2 + 2 = 4 4 * 4 = 16 4 * 3 = 12 real 7m28.947s user 7m24.456s sys 0m0.260s

So, not too bad at 7.5 minutes.

Here's the latest code.

Spoiler for Perl code

Go to the full post
#!/usr/bin/env perl # # http://brainden.com/forum/index.php/topic/17088-optimal-game-strat/ # # Two players pick 2 numbers each from 1..256. The first number is that # player's starting number, and the second number is the opponent's goal # number. Using +-*/ only, get from start to goal in the least number of # operations. Players may only use numbers previously generated in their # sequence. # # What is the best starting number, and worst goal number, in terms of # number of moves? # # Generate all start=>goal shortest paths. Report the start with the # smallest "longest" path, and the goal with the longest "shortest" # path. # Method: # Use a hash like this to keep track: # $m = {goal1 => { list => { n1 => 1, # n2 => 1, # }, # path => { "n1 op n2" => result1, # "n3 op n4" => result2, # }, # }, # goal2 => {...}, # }; # # As operations are tried, each generated value is added to the hash, until # the goal is generated. The number of steps is the size of the array for # each seen. Any seen value with a size of 1 is an immediate child. # Any generated values larger than $last*2 are not saved. use strict; use warnings; use integer; my $last = (shift // 10); my $upper_limit = $last; my $my_start = (shift // 0); my $my_goal = (shift // 0); my $START = q/start/; my $GOAL = q/goal/; my $STEPS = q/steps/; my $COUNT = q/count/; my $MEAN = q/mean/; my $PLUS = '+'; my $MINUS = '-'; my $TIMES = '*'; my $DIVIDE = '/'; my @ops = ($PLUS, $MINUS, $TIMES, $DIVIDE); my %matrix; # %matrix = ($start1 => {$goal1 => { $path1 => $result1, # $path2 => $result2 }, # {$goal2 => { ... }, # $start2 => {...} ) # For each $start, record the $goal with the longest $path my %start; # %start = {$start => {STEPS => steps, GOAL => goal}; # For each $start or $goal, sum the steps and update count, to compute mean later on my %mean; # %mean = {$START => {$start => {STEPS => steps, COUNT => count}, # $GOAL => {$goal => {STEPS => steps, COUNT => count}}; for my $start (1..$last) { print STDERR "$start "; my $m = {}; $m->{$start} = {}; # Generate results until no new or shorter results are found. # This loop is limited by the value of $upper_limit. 1 while generate($m); # Now walk through all goals, saving highest steps, summing steps and update counts my $steps_max = 0; for my $goal (1..$last) { my $steps = scalar keys %{$m->{$goal}}; $steps_max = $steps if ($steps > $steps_max); if (not exists($start{$start}) or ($steps > $start{$start}{$STEPS})) { $start{$start}{$STEPS} = $steps; $start{$start}{$GOAL} = $goal; } $mean{$START}{$start}{$STEPS} += $steps; $mean{$START}{$start}{$COUNT}++; $mean{$GOAL}{$goal}{$STEPS} += $steps; $mean{$GOAL}{$goal}{$COUNT}++; } $matrix{$start} = $m; } # Find the starts with the lowest and highest max steps my ($start_best,$start_worst) = (sort {$start{$a}{$STEPS} <=> $start{$b}{$STEPS}} keys %start)[0,-1]; # Best starts print "\nBest starts have $start{$start_best}{$STEPS} worst case steps:\n"; for my $s (1..$last) { if ($start{$s}{$STEPS} == $start{$start_best}{$STEPS}) { printf "\t%4d => %4d\n", $s, $start{$s}{$GOAL}; } } # Worst starts print "\nWorst starts have $start{$start_worst}{$STEPS} worst case steps:\n"; for my $s (1..$last) { if ($start{$s}{$STEPS} == $start{$start_worst}{$STEPS}) { printf "\t%4d => %4d\n", $s, $start{$s}{$GOAL}; } } no integer; # Find the start and goal with the highest mean steps for my $ENDPOINT ($START, $GOAL) { for my $n (1..$last) { $mean{$ENDPOINT}{$n}{$MEAN} = $mean{$ENDPOINT}{$n}{$STEPS} / $mean{$ENDPOINT}{$n}{$COUNT}; } } # Report the best start means my @start_best = sort {$mean{$START}{$a}{$MEAN} <=> $mean{$START}{$b}{$MEAN}} keys %{$mean{$START}}; $start_best = $start_best[0]; # Report all mean starts near the best mean printf "\nBest starts have %3.2f mean steps:\n", $mean{$START}{$start_best}{$MEAN}; my $start_best_mean_plus_2tenths = $mean{$START}{$start_best}{$MEAN} + 0.2; for my $s (@start_best) { if ($mean{$START}{$s}{$MEAN} <= $start_best_mean_plus_2tenths) { printf "\t%4d, %3.2f mean steps\n", $s, $mean{$START}{$s}{$MEAN}; } } # Report the worst goal means my @goal_worst = sort {$mean{$GOAL}{$b}{$MEAN} <=> $mean{$GOAL}{$a}{$MEAN}} keys %{$mean{$GOAL}}; my $goal_worst = $goal_worst[0]; # Report all mean goals near the worst mean printf "\nWorst goals have %3.2f mean steps:\n", $mean{$GOAL}{$goal_worst}{$MEAN}; my $goal_worst_mean_less_2tenths = $mean{$GOAL}{$goal_worst}{$MEAN} - 0.2; for my $g (@goal_worst) { if ($mean{$GOAL}{$g}{$MEAN} >= $goal_worst_mean_less_2tenths) { printf "\t%4d, %3.2f mean steps\n", $g, $mean{$GOAL}{$g}{$MEAN}; } } # If you want a specific start/goal path, print it here. # Order is not preserved. if ($my_start and $my_goal) { print "\nSteps for $my_start => $my_goal (not in order):\n"; for my $path (keys %{$matrix{$my_start}{$my_goal}}) { print "\t$path = $matrix{$my_start}{$my_goal}{$path}\n"; } print "\n"; } exit; use integer; # From the given list of results, compute additional results # using all combinations of operands and operators. # Only record the shortest paths of unique results. sub generate { my $m = shift; my $results_added = 0; # The currently known goals, sorted in descending order for compute my @seen = sort {$b <=> $a} keys %$m; # Walk through @seen x @seen, but avoid obvious redundancies for my $i1 (0..$#seen) { my $s1 = $seen[$i1]; for my $i2 ($i1..$#seen) { my $s2 = $seen[$i2]; # Try every operation for my $op (@ops) { my ($result,$expression) = compute($s1,$s2,$op); next unless $result; next unless ($result <= $upper_limit); # speedup, might lose some shorter paths # Add unique paths to get this result my $new_path = {%{$m->{$s1}}, %{$m->{$s2}}, $expression => $result }; # 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; } } } } return $results_added; } # Take 2 numbers, sorted in descending order, and an operator. # Return the result and the string expression used. # Subtract and divide are managed to avoid negative or non-integer results. sub compute { my $n1 = shift; # larger my $n2 = shift; # smaller or equal to $n1 my $op = shift; my ($result,$expression); if ($op eq $PLUS) { $result = $n1 + $n2; $expression = "$n1 $PLUS $n2"; } elsif ($op eq $MINUS) { $result = $n1 - $n2; $expression = "$n1 $MINUS $n2"; } elsif ($op eq $TIMES) { $result = $n1 * $n2; $expression = "$n1 $TIMES $n2"; } elsif ($op eq $DIVIDE) { $result = $n1 / $n2; # only integer results allowed ("use integer" in effect) return(0,undef) if ($result * $n2 != $n1); $expression = "$n1 $DIVIDE $n2"; } else { die "Error: unknown operand ($op), aborting...\n"; } return($result,$expression); } # compute