optimal game strat

[phil1882]

in this two player game, each  player secretly picks two  numbers, one of  which is his own starting number and the other is his opponents goal number. numbers are allowed to be any integer value between 1 and 256. then both players reveal the numbers, and may use addition, subtraction, multiplication, and division, to try to get to the  goal number using only numbers they generate from their starting value.

for example, player A may pick start 36 goal 47, and player B may pick start 123 goal 123.

player A does 36/36 for 1. player B does 123/123 for 1.

player A does 1+1 for 2. player B does 1+1 for 2.

player A does 1+2 for 3. player B does 1+2 for 3.

player A does 36*3 for 104. player B does 123/3 for 41.

player A does 36/2 for 18. player B does 41+3 for 44.

player A does 104+18 for 126. player B does 44 +3 for 47. therefore player B wins.

note ties are possible if both players get it  in the same number of operations.

so you know the drill, whats the best starting value and worst ending value, assuming you don't know what your opponent is going to pick?

[Quantum.Mechanic]

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.

> 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.

#!/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

[bonanova]

Nice problem.

 

Are you asking for the starting and ending values to chose, that would maximize your chance to win?

By this question I'm trying to clarify "worst ending value."

 

Also, by your example, can we conclude that only two numbers can be combined on each turn?

 

Thanks.

 

One's starting number should be factor-rich, like 30 or 210, and opponent's number should be the opposite - a prime, and probably a large prime, like 251.

[phil1882]

close enough. best starting value to chose, and the worst goal value your opponent could chose given your starting value.

correct. you can only combine two previously generated numbers each step.

Edited July 25, 2014 by phil1882

[plasmid]

It looks like this will be more of a programming exercise than anything.

And it looks like it won't be all that amenable to a simple greedy algorithm. (It would probably be solved with some sort of greedy algorithm, but not the simple one I'm thinking of.)

 

For example, getting from 1 to 7 would involve

1+1=2

2*2=4

2+1=3

4+3=7

 

It takes two steps to generate 3 (1+1=2, 2+1=3) and two steps to generate 4 (1+1=2, 2+2=4).

But it does not take [two steps to make 3] + [two steps to make 4] + [a step to combine 3 and 4] = 5 steps to generate 7 because the 1+1=2 is shared by the generation of 3 and 4.

[bonanova]

Agree. What it seems to boil down to is constructing a 255 x 255 matrix, looking for the smallest number in each column and selecting the row having the largest minimum, for the second answer, and the column through the smallest maximum for the first part. That's a lot of computing, once an algorithm is found to get from any A to any B in the fewest moves.

[wolfgang]

a start number should be 210 which is factor-rich( 1 to 7)

while the goal number should be a prime number which has the biggest difference between it and the two prime numbers before and after it , and this number is 127.
because,
131-127=4 steps
127-113=14 steps
so to win he should choose 210 as a start number, and 127 as a goal number.

[plasmid]

Perl's dynamic arrays make things easy to program (relatively). This program works if you have a small range that you're working over -- if the maximum value of the numbers is 10 instead of 255 -- but would be horribly inefficient if you wanted to calculate it for 255. It does give an algorithm that would work in principle, though. If there were an easy way of eliminating redundant arrays and repeated terms within arrays (which I imagine there are a bunch of) then it might be feasible for 255.

#!/usr/bin/perl
use strict;
use warnings;

# For each starting number from 1 to $max, this creates
#   a 3-dimensional array called @sets.
# @sets starts off with just one term -- $sets[0][0][0]
#   which is the starting number for the calculations.
# The first dimension of @sets represents the round number;
#   after doing zero rounds of calculations you only have
#   the starting number, and after doing N calculations you
#   can generate one of many possible sets of terms.
# Each of those possible sets of terms that can be generated
#   after N rounds is stored in $sets[$round][$setnumber].
# Each element within those sets is stored in
#   $sets[$round][$setnumber][$elementnumber].

# What the program will do is on round N, it will look
#   at each set of numbers that could be generated by round N
#   and performs every possible operation on every pair of
#   numbers in the set. It then creates a new set for round
#   N+1 containing the original set plus a number that can
#   be generated by an operation on two numbers in that set.
# So there can potentially be many, many different sets created
#   for round N+1 by every set from round N (one new set for
#   every operation between every pair of elements in the
#   parent set).

# After doing however many rounds it takes to get from the
#   starting number to every other number within the range,
#   the program will create @matrix, where the element of
#   $matrix[x][y] is the minimum number of rounds in which
#   a solution to get from a starting point of x to an
#   ending point of y could be found.

my $max = 10; # maximum value of any number in a list
my @matrix = (); # moves to get from number x to y
for my $i (1..$max) {
  for my $j (1..$max) {
    $matrix[$i][$j] = -1;
  }
}

for my $start (1..$max) {
  my @sets = ();
  $sets[0][0][0] = $start;
  my $round = 0;
  my $done = 0;
  until ($done) {
    for my $set (@{$sets[$round]}) {
      for my $x (@$set) {
        for my $y (@$set) {
          if ($x+$y <= $max) {
            push @{$sets[$round+1]}, [@$set, $x+$y];
          }
          if ($x-$y > 0) {
            push @{$sets[$round+1]}, [@$set, $x-$y];
          }
          if ($x*$y <= $max) {
            push @{$sets[$round+1]}, [@$set, $x*$y];
          }
          if ($x%$y == 0) {
            push @{$sets[$round+1]}, [@$set, $x/$y];
          }
        }
      }
    }
    
    $round++;
    print "Starting from $start, round $round \n";
    $done = 1;
    for my $x (1..$max) {
      my $found = 0;
      for my $set (@{$sets[$round]}) {
        for my $element (@$set) {
          $found = $found || ($element == $x);
        }
      }
      $done *= $found;
    }
  }

  for my $x (1..$max) {
    for my $round (0..$#sets) {
      for my $set (@{$sets[$round]}) {
        for my $element (@$set) {
          if ($element == $x) {
            if ($matrix[$start][$x] == -1) {
              $matrix[$start][$x] = $round;
            }
          }
        }
      }
    }
    print "From $start to $x took $matrix[$start][$x] moves\n";
  }
}

From 1 to 1 took 0 moves

From 1 to 2 took 1 moves

From 1 to 3 took 2 moves

From 1 to 4 took 2 moves

From 1 to 5 took 3 moves

From 1 to 6 took 3 moves

From 1 to 7 took 4 moves

From 1 to 8 took 3 moves

From 1 to 9 took 3 moves

From 1 to 10 took 4 moves

From 2 to 1 took 1 moves

From 2 to 2 took 0 moves

From 2 to 3 took 2 moves

From 2 to 4 took 1 moves

From 2 to 5 took 3 moves

From 2 to 6 took 2 moves

From 2 to 7 took 4 moves

From 2 to 8 took 2 moves

From 2 to 9 took 3 moves

From 2 to 10 took 3 moves

From 3 to 1 took 1 moves

From 3 to 2 took 2 moves

From 3 to 3 took 0 moves

From 3 to 4 took 2 moves

From 3 to 5 took 3 moves

From 3 to 6 took 1 moves

From 3 to 7 took 3 moves

From 3 to 8 took 3 moves

From 3 to 9 took 1 moves

From 3 to 10 took 3 moves

From 4 to 1 took 1 moves

From 4 to 2 took 2 moves

From 4 to 3 took 2 moves

From 4 to 4 took 0 moves

From 4 to 5 took 2 moves

From 4 to 6 took 3 moves

From 4 to 7 took 3 moves

From 4 to 8 took 1 moves

From 4 to 9 took 3 moves

From 4 to 10 took 3 moves

From 5 to 1 took 1 moves

From 5 to 2 took 2 moves

From 5 to 3 took 3 moves

From 5 to 4 took 2 moves

From 5 to 5 took 0 moves

From 5 to 6 took 2 moves

From 5 to 7 took 3 moves

From 5 to 8 took 3 moves

From 5 to 9 took 3 moves

From 5 to 10 took 1 moves

From 6 to 1 took 1 moves

From 6 to 2 took 2 moves

From 6 to 3 took 3 moves

From 6 to 4 took 3 moves

From 6 to 5 took 2 moves

From 6 to 6 took 0 moves

From 6 to 7 took 2 moves

From 6 to 8 took 3 moves

From 6 to 9 took 4 moves

From 6 to 10 took 3 moves

From 7 to 1 took 1 moves

From 7 to 2 took 2 moves

From 7 to 3 took 3 moves

From 7 to 4 took 3 moves

From 7 to 5 took 3 moves

From 7 to 6 took 2 moves

From 7 to 7 took 0 moves

From 7 to 8 took 2 moves

From 7 to 9 took 3 moves

From 7 to 10 took 4 moves

From 8 to 1 took 1 moves

From 8 to 2 took 2 moves

From 8 to 3 took 3 moves

From 8 to 4 took 3 moves

From 8 to 5 took 4 moves

From 8 to 6 took 3 moves

From 8 to 7 took 2 moves

From 8 to 8 took 0 moves

From 8 to 9 took 2 moves

From 8 to 10 took 3 moves

From 9 to 1 took 1 moves

From 9 to 2 took 2 moves

From 9 to 3 took 3 moves

From 9 to 4 took 3 moves

From 9 to 5 took 4 moves

From 9 to 6 took 4 moves

From 9 to 7 took 3 moves

From 9 to 8 took 2 moves

From 9 to 9 took 0 moves

From 9 to 10 took 2 moves

From 10 to 1 took 1 moves

From 10 to 2 took 2 moves

From 10 to 3 took 3 moves

From 10 to 4 took 3 moves

From 10 to 5 took 3 moves

From 10 to 6 took 4 moves

From 10 to 7 took 4 moves

From 10 to 8 took 3 moves

From 10 to 9 took 2 moves

From 10 to 10 took 0 moves

Edited July 27, 2014 by plasmid

[bonanova]

Wondering if the "moves from A to B" calculation could be put into an Excel macro to paste into the cells of a 255x255 Excel array.

Just thinking.

Or maybe there's an Aha! Solution...

Wolfgang's answer answer has merit.

[plasmid]

I got the code a little more efficient (thanks to the magical ~~ operator in perl) so it could work with a max value of 30 instead of 10, running for a matter of hours, but it's still far less than the 255 in the OP.

The answer was surprising.

This is a matrix where the row number is the number you're starting from, and the column number is the number you're trying to reach, and the number in that cell is the number of moves needed to get there. The starting point with the fewest maximum number of moves needed is 7, which was surprising. The ending point that takes the most moves to reach (based on just taking the average of each column) is not surprising -- primes take a lot and the larger primes take more than the smaller ones.

0 1 2 2 3 3 4 3 3 4 4 4 5 4 4 3 4 4 5 4 5 5 5 4 4 5 4 5 5 5
1 0 2 1 3 2 4 2 3 3 4 3 5 3 4 2 4 3 5 3 5 4 5 3 4 4 4 4 5 4
1 2 0 2 3 1 3 3 1 3 4 2 4 4 3 3 4 2 4 4 3 5 5 3 4 4 2 4 5 3
1 2 2 0 2 3 3 1 3 3 4 2 4 4 3 1 3 4 4 2 4 5 5 3 3 4 4 3 4 4
1 2 3 2 0 2 3 3 3 1 3 3 4 4 2 3 4 4 4 2 4 4 4 3 1 3 4 5 4 2
1 2 3 3 2 0 2 3 4 3 3 1 3 3 4 4 4 2 4 4 4 4 4 2 3 4 5 4 4 3
1 2 3 3 3 2 0 2 3 4 4 3 3 1 3 3 4 4 4 4 2 4 4 4 4 4 4 2 4 4
1 2 3 3 4 3 2 0 2 3 4 4 4 3 3 1 3 3 4 4 4 4 4 2 4 4 4 4 5 4
1 2 3 3 4 4 3 2 0 2 3 4 4 4 4 3 3 1 3 3 4 4 5 4 4 4 2 4 4 4
1 2 3 3 3 4 4 3 2 0 2 3 4 4 4 4 4 3 3 1 3 3 4 4 4 5 4 4 4 2
1 2 3 3 4 4 4 4 3 2 0 2 3 4 4 4 5 4 4 3 3 1 3 3 4 4 5 5 5 4
1 2 3 3 4 3 4 4 4 3 2 0 2 3 4 4 5 4 5 4 4 3 3 1 3 3 4 4 5 4
1 2 3 3 4 4 4 4 4 4 3 2 0 2 3 4 4 5 5 5 5 4 4 3 3 1 3 3 4 4
1 2 3 3 4 4 3 4 4 4 4 3 2 0 2 3 4 4 5 5 4 5 5 4 4 3 3 1 3 3
1 2 3 3 4 4 4 4 4 5 4 4 3 2 0 2 3 4 4 5 5 5 5 5 5 4 4 3 3 1
1 2 3 3 4 4 4 3 4 4 5 4 4 3 2 0 2 3 4 4 5 5 5 4 5 5 5 4 4 3
1 2 3 3 4 4 5 4 4 5 5 5 4 4 3 2 0 2 3 4 4 5 5 5 5 5 5 5 5 4
1 2 3 3 4 4 4 4 3 4 4 5 5 4 4 3 2 0 2 3 4 4 5 5 5 5 4 5 5 5
1 2 3 3 4 4 5 4 4 4 5 5 5 5 4 4 3 2 0 2 3 4 4 5 5 6 5 5 5 5
1 2 3 3 4 4 5 4 4 3 4 4 5 5 5 4 4 3 2 0 2 3 4 4 5 5 5 5 5 4
1 2 3 3 4 4 4 4 4 4 4 5 5 5 5 4 4 4 3 2 0 2 3 4 4 5 5 5 5 5
1 2 3 3 4 4 5 4 4 4 3 4 4 5 5 4 5 4 4 3 2 0 2 3 4 4 5 5 6 5
1 2 3 3 4 4 5 4 4 5 4 4 5 5 5 4 5 5 4 4 3 2 0 2 3 4 4 5 5 6
1 2 3 3 4 4 5 4 4 4 4 3 4 4 5 4 5 5 5 4 4 3 2 0 2 3 4 4 5 5
1 2 3 3 4 4 5 4 4 5 5 4 4 5 5 4 5 5 5 5 4 4 3 2 0 2 3 4 4 5
1 2 3 3 4 4 5 4 4 5 4 4 3 4 4 4 5 5 6 5 5 4 4 3 2 0 2 3 4 4
1 2 3 3 4 4 5 4 4 5 5 5 4 4 5 4 5 5 5 5 5 5 4 4 3 2 0 2 3 4
1 2 3 3 4 4 4 4 4 5 5 4 4 3 4 4 5 5 5 5 5 5 5 4 4 3 2 0 2 3
1 2 3 3 4 4 5 4 4 5 5 5 5 4 4 4 5 5 6 5 5 6 5 5 4 4 3 2 0 2
1 2 3 3 4 4 5 4 4 4 5 5 4 4 3 4 4 5 5 5 5 5 6 5 5 4 4 3 2 0

#!/usr/bin/perl
use strict;
use warnings;

# For each starting number from 1 to $max, this creates
#   a 3-dimensional array called @sets.
# @sets starts off with just one term -- $sets[0][0][0]
#   which is the starting number for the calculations.
# The first dimension of @sets represents the round number;
#   after doing zero rounds of calculations you only have
#   the starting number, and after doing N calculations you
#   can generate one of many possible sets of terms.
# Each of those possible sets of terms that can be generated
#   after N rounds is stored in $sets[$round][$setnumber].
# Each element within those sets is stored in
#   $sets[$round][$setnumber][$elementnumber].

# What the program will do is on round N, it will look
#   at each set of numbers that could be generated by round N
#   and performs every possible operation on every pair of
#   numbers in the set. It then creates a new set for round
#   N+1 containing the original set plus a number that can
#   be generated by an operation on two numbers in that set.
# So there can potentially be many, many different sets created
#   for round N+1 by every set from round N (one new set for
#   every operation between every pair of elements in the
#   parent set).

# After doing however many rounds it takes to get from the
#   starting number to every other number within the range,
#   the program will create @matrix, where the element of
#   $matrix[x][y] is the minimum number of rounds in which
#   a solution to get from a starting point of x to an
#   ending point of y could be found.

my $max = 30; # maximum value of any number in a list

# Initialize @matrix with -1 in a cell meaning that you have
#   yet to find an optimal path from x to y.
my @matrix = ();
for my $x (1..$max) {
  for my $y (1..$max) {
    $matrix[$x][$y] = -1;
  }
}

# Run this loop for each different starting number
for my $start (1..$max) {

  # Initialize @sets to just have the starting number in
  #   the first set.
  my @sets = ();
  $sets[0][0][0] = $start;
  $matrix[$start][$start] = 0;
  my $round = 0;
  my $done = 0;

  # This loop tries every possible calculation on every
  #   pair of terms in the sets so far.
  # If the result of the calculation is an integer from 1
  #   to $max, and if it's not already in the set, then
  #   a new set for the next round is created where that
  #   result is added to the current set (as long as
  #   that set has not already been created as a set going
  #   into the next round).
  # Perl seems to choke unless I specifically push the
  #   new arrays' addresses rather than the arrays
  #   themselves now; it seems to get confused about
  #   whether it's looking up an array or a pointer to
  #   an array if there's only one set in $sets[$round].
  until ($done) {
    for my $set (@{$sets[$round]}) {
      for my $x (@$set) {
        for my $y (@$set) {
          if (($x+$y <= $max) && !($x+$y ~~ @$set)) {
            my @tempset = sort(@$set, $x+$y);
            my $alreadyin = 0;
            for my $compareset (@{$sets[$round+1]}) {
              $alreadyin += (@$compareset ~~ @tempset);
            }
            if (! $alreadyin) {
              push @{$sets[$round+1]}, \@tempset;
            }
          }
          if (($x-$y > 0) && !($x-$y ~~ @$set)) {
            my @tempset = sort(@$set, $x-$y);
            my $alreadyin = 0;
            for my $compareset (@{$sets[$round+1]}) {
              $alreadyin += (@$compareset ~~ @tempset);
            }
            if (! $alreadyin) {
              push @{$sets[$round+1]}, \@tempset;
            }
          }
          if (($x*$y <= $max) && !($x*$y ~~ @$set)) {
            my @tempset = sort(@$set, $x*$y);
            my $alreadyin = 0;
            for my $compareset (@{$sets[$round+1]}) {
              $alreadyin += (@$compareset ~~ @tempset);
            }
            if (! $alreadyin) {
              push @{$sets[$round+1]}, \@tempset;
            }
          }
          if (($x%$y == 0) && !($x/$y ~~ @$set)) {
            my @tempset = sort(@$set, $x/$y);
            my $alreadyin = 0;
            for my $compareset (@{$sets[$round+1]}) {
              $alreadyin += (@$compareset ~~ @tempset);
            }
            if (! $alreadyin) {
              push @{$sets[$round+1]}, \@tempset;
            }
          }
        }
      }
    }
    
    # Set values for the terms in @matrix that you have
    #   reached, and see if you need to do another round.
    $round++;
    for my $x (1..$max) {
      if ($matrix[$start][$x] == -1) {
        for my $set (@{$sets[$round]}) {
          if ($x ~~ @$set) {
            $matrix[$start][$x] = $round;
          }
        }
      }
    }
    $done = !(-1 ~~ @{$matrix[$start]}[1..$max]);
  }

  # Once you figure out the distance from $start to every
  #   other term, print the results.
#  for my $x (1..$max) {
#    print "From $start to $x took $matrix[$start][$x] moves\n";
#  }
  print "@{$matrix[$start]}[1..$max]\n";
}

[plainglazed]

along with plasmid's findings, am thinking the factor rich approach may not be optimal as it takes a fair amount of steps to get one of a factor pair. what may be best are powers of two. using 8 as the starting number, one can generate all numbers between 1 and 64 in five steps except 53 and 59 which can be done in six steps (one of which can be 8 x 8). from there 65 - 128 can be constructed in at most two more steps: 8 x 8 and 64 + (1-64). Then 129-256 can be constructed similarly: 64 + 64 and 128 + (1-128) for a maximum number of nine steps. some of the 129-256 can probably be reduced to fewer steps but thinking not all. have not run the spreadsheet past 64.

though certainly have no clue as to proving this as best or an analytical way to go about finding the best starting number without a brute force exhaustive search.

[Quantum.Mechanic]

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.

[Quantum.Mechanic]

I wrote a Perl program. These results took about 5 minutes:

 

Best starts have 7 worst case steps:
2 => 89, 7 steps
3 => 139, 7 steps
4 => 139, 7 steps
5 => 141, 7 steps
6 => 233, 7 steps
7 => 165, 7 steps
8 => 87, 7 steps
9 => 95, 7 steps
10 => 107, 7 steps
11 => 115, 7 steps
12 => 115, 7 steps
13 => 137, 7 steps
14 => 163, 7 steps
17 => 143, 7 steps
18 => 155, 7 steps
19 => 107, 7 steps
20 => 173, 7 steps
21 => 161, 7 steps
22 => 75, 7 steps
23 => 124, 7 steps
24 => 129, 7 steps
25 => 165, 7 steps
26 => 201, 7 steps
27 => 71, 7 steps
28 => 67, 7 steps
29 => 69, 7 steps
30 => 101, 7 steps
31 => 73, 7 steps
32 => 53, 7 steps
33 => 86, 7 steps
34 => 45, 7 steps
35 => 59, 7 steps
36 => 86, 7 steps
38 => 62, 7 steps
39 => 61, 7 steps
40 => 26, 7 steps
41 => 52, 7 steps
42 => 133, 7 steps
43 => 67, 7 steps
45 => 71, 7 steps
51 => 23, 7 steps
53 => 76, 7 steps
54 => 87, 7 steps

Worst goals have 6.5 mean steps:
247 => 6.50 mean steps
233 => 6.49 mean steps
235 => 6.46 mean steps
251 => 6.45 mean steps
137 => 6.44 mean steps
139 => 6.42 mean steps
151 => 6.41 mean steps
229 => 6.41 mean steps
179 => 6.40 mean steps
149 => 6.40 mean steps
141 => 6.39 mean steps
249 => 6.39 mean steps
199 => 6.39 mean steps
173 => 6.39 mean steps
211 => 6.38 mean steps
239 => 6.38 mean steps
131 => 6.38 mean steps
237 => 6.38 mean steps
193 => 6.37 mean steps
205 => 6.37 mean steps
157 => 6.37 mean steps
253 => 6.37 mean steps
241 => 6.36 mean steps
187 => 6.36 mean steps
245 => 6.36 mean steps
191 => 6.36 mean steps
133 => 6.36 mean steps
181 => 6.35 mean steps
203 => 6.35 mean steps
167 => 6.35 mean steps
217 => 6.35 mean steps
175 => 6.34 mean steps
185 => 6.34 mean steps
197 => 6.33 mean steps
103 => 6.32 mean steps
227 => 6.32 mean steps
215 => 6.32 mean steps
201 => 6.32 mean steps
177 => 6.32 mean steps
183 => 6.32 mean steps
207 => 6.32 mean steps
134 => 6.32 mean steps
213 => 6.31 mean steps
231 => 6.31 mean steps
163 => 6.30 mean steps
223 => 6.30 mean steps
155 => 6.30 mean steps
206 => 6.30 mean steps
221 => 6.30 mean steps

 

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.

 

#!/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 => [ [ num1, op, num2 ] ],
#               },
#      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;

my $last = (shift // 10);
my $last_squared = $last**2;

my $LIST = q/list/;
my $PATH = q/path/;
my $START = q/start/;
my $GOAL = q/goal/;
my $STEPS = q/steps/;
my $COUNT = q/count/;
my $MEAN = q/mean/;

my $PLUS = q/+/;
my $MINUS = q/-/;
my $TIMES = q/*/;
my $DIVIDE = q#/#;

my @ops = ($PLUS, $MINUS, $TIMES, $DIVIDE);

# For each $start, record the $goal with the longest $path
my %start; # %start = {$start => {STEPS => steps, GOAL => goal};
# For each $goal, sum the steps and update count, to compute mean later on
my %goal; # %goal = {$goal => {STEPS => steps, COUNT => count};

for my $start (1..$last) {
    print STDERR "$start ";
    my $m = {};
    $m->{$start} = {$LIST => {}, # zero length path for identity
                    $PATH => [],
                   };
    for my $goal (1..$last) {
        while (not exists($m->{$goal})) {
            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 @{$m->{$goal}{$PATH}};
        $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;
        }
        $goal{$goal}{$STEPS} += $steps;
        $goal{$goal}{$COUNT}++;
    }
}

# Find the start with the lowest max steps
my ($start_best) = (sort {$start{$a}{$STEPS} <=> $start{$b}{$STEPS}} keys %start)[0];
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 "%d => %d, %d steps\n", $s, $start{$s}{$GOAL}, $start{$s}{$STEPS};
    }
}

# Find the goal with the highest mean steps
for my $g (1..$last) {
    $goal{$g}{$MEAN} = $goal{$g}{$STEPS} / $goal{$g}{$COUNT};
}
my @goal_worst = sort {$goal{$b}{$MEAN} <=> $goal{$a}{$MEAN}} keys %goal;
my $goal_worst = $goal_worst[0];
# Report all mean goals within 1 of the worst mean
print "\nWorst goals have $goal{$goal_worst}{$MEAN} mean steps:\n";
my $goal_worst_mean_less_2tenths = $goal{$goal_worst}{$MEAN} - 0.2;
for my $g (@goal_worst) {
    if ($goal{$g}{$MEAN} >= $goal_worst_mean_less_2tenths) {
        printf "%3d => %3.2f mean steps\n", $g, $goal{$g}{$MEAN};
    }
}

exit;

sub generate {
    my $m = shift;

    my @seen = keys %$m;

    for my $n1 (@seen) {
        my @list = keys %{$m->{$n1}{$LIST}};
        for my $n2 (@list,$n1) {
            for my $op (@ops) {
                my ($result,$expression) = compute($n1,$n2,$op);
                next unless $result;
                next unless ($result < $last_squared); # speedup, loses some shorter paths
                next if (exists($m->{$result}));
                my $new = $m->{$result} = {};
                $new->{$LIST} = {%{$m->{$n1}{$LIST}}, $n1 => 1, $n2 => 1};
                my @path = @{$m->{$n1}{$PATH}}; # existing path for $n1
                $new->{$PATH} = [@path,$expression]; # extend path
            }
        }
    }
}

sub compute {
    my $n1 = shift;
    my $n2 = shift;
    my $op = shift;

    # sort descending, for subtract and divide
    ($n1,$n2) = sort {$b <=> $a} ($n1,$n2);

    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
        return(0,undef) if $result =~ m/\D/;
        $expression = [$n1, $DIVIDE, $n2];
    } else {
        die "Error: unknown operand ($op), aborting...\n";
    }
    return($result,$expression);
} # compute

Edited August 5, 2014 by Quantum.Mechanic

[bonanova]

Let's assume a matrix of fewest moves from A to B for all A and all B exists.

Let's call opponent's starting and ending numbers A and B, and our starting and ending numbers C and D, respectively.

 

Keep in mind the table does not give winning percentages for our choices of C and D.

For the table to usefully guide our choice of C and D, we need to know something about A and B.

And that knowledge might simply be that we know nothing about them -- that for our purposes they're random.

 

Strategy 0:

 

Suppose we know A and B exactly.

The table gives us C and D values that will guarantee a win.

 

Alas, we don't know A and B.

 

Strategy 1:

 

Suppose we have no clue about A and B and assume they are randomly chosen.

 

In that case:

Averages of table rows give expected moves to D for each D.

Averages of table columns give expected moves from C for each C.

 

Pick the C and D with least and greatest expected moves, respectively.

That does not guarantee a win, but it gives us the highest probability of winning.

 

Strategy 2:

 

Since row and column averages differ:

Assume that those differences have guided opponents' choice of A and B.

Assume A and B are not randomly chosen, but based rather on expected moves vs. a random opponent.

 

Calculate expected moves from the appropriately weighted row and column averages.

Pick C and D, again, having the least and greatest expected moves.

 

Strategy 3:

 

Assume opponent's probability distribution is based on expected moves vs. a weighted-average opponent.

Calculate expected moves again, but now weighted by that probability distribution.

Pick C and D accordingly.

 

And so on...

 

This process might converge to a best overall choice for C and D.

 

But here's the kicker:

 

Anything we can calculate, opponent can calculate.

If opponent can anticipate our C and D, however good we think they might be,

the table will then give him values of A and B that will beat them.

 

But of course, we can find those values too, and the table then gives us values of C and D that will beat them.

 

And the problem is now seen to resemble a poker game.

 

My final answer:

 

Since the OP gives us no clue as to how opponent would play poker, we cannot anticipate his strategy.

That's another way of saying we don't know A and B -- that we may as well model them as being random.

 

That says Strategy 1 is best:

 

Pick the D that has the greatest row average and the C that has the smallest column average.

[plasmid]

I've been trying to figure out what makes your code run so much faster, and I think I can more or less follow its logic but I'm not sure about one point. If you wanted to get from a starting point of 1 to an ending point of 7, you could do that with

1+1=2

2*2=4

2+1=3

4+3=7

With the algorithm, after you get one path with

1, 2, 4

and another path with

1, 2, 3

it looks like the first of those sets wouldn't allow you to add 4 in the next round because there is already a different path to reach 4, and the second of those sets wouldn't allow you to add 3 in the next round because there is already a different path to reach 3. (This is from the next if (exists($m->{$result})); line.) I'm wondering if it would have a way of discovering that path to 7?

For the most part our algorithms seem to agree, but when I set the max size for both algorithms to 30, mine said you can go from 25 to 13 in 4 steps (from the matrix in my earlier post) while yours said that 25 to 13 took 6 steps (when I commented out the

if ($start{$s}{$STEPS} == $start{$start_best}{$STEPS}) {

and subsequent close bracket surrounding the print statement). A path with four steps is:

25/25 = 1

25+1 = 26

1+1 = 2

26/2 = 13

[Quantum.Mechanic]

I've been trying to figure out what makes your code run so much faster, and I think I can more or less follow its logic but I'm not sure about one point. If you wanted to get from a starting point of 1 to an ending point of 7, you could do that with

1+1=2

2*2=4

2+1=3

4+3=7

With the algorithm, after you get one path with

1, 2, 4

and another path with

1, 2, 3

it looks like the first of those sets wouldn't allow you to add 4 in the next round because there is already a different path to reach 4, and the second of those sets wouldn't allow you to add 3 in the next round because there is already a different path to reach 3. (This is from the next if (exists($m->{$result})); line.) I'm wondering if it would have a way of discovering that path to 7?

 

 

 

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.

[Quantum.Mechanic]

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.

> time four_banger.pl 256 195 170
Steps for 195 => 170 (not in order):
        390 - 1 = 389
        195 + 1 = 196
        195 / 195 = 1
        389 - 2 = 387
        2 + 1 = 3
        195 - 1 = 194
        195 + 195 = 390
        196 + 2 = 198
        392 - 387 = 5
        192 / 4 = 48
        390 + 1 = 391
        193 - 66 = 127
        194 - 2 = 192
        48 - 5 = 43
        1 + 1 = 2
        127 + 43 = 170
        198 / 3 = 66
        194 - 1 = 193
        391 + 1 = 392
        2 + 2 = 4
        
Best starts have 10 worst case steps:
        3 => 65
        4 => 74
        5 => 38
        6 => 58
        7 => 31
        8 => 165
        9 => 13
        10 => 52
        11 => 17
        12 => 16
        13 => 36
        14 => 23
        15 => 23
        16 => 94
        18 => 23

Worst starts have 20 worst case steps:
        195 => 170
        202 => 124
        218 => 246
        219 => 173

Best starts have 6.45 mean steps:
      8, 6.45 mean steps
      4, 6.53 mean steps
      6, 6.61 mean steps

Worst goals have 9.70 mean steps:
    247, 9.70 mean steps
    202, 9.64 mean steps
    206, 9.61 mean steps
    218, 9.56 mean steps
    203, 9.55 mean steps
    239, 9.54 mean steps
    185, 9.54 mean steps
     13, 9.53 mean steps
    249, 9.53 mean steps
    191, 9.52 mean steps
    173, 9.52 mean steps
    205, 9.51 mean steps
    213, 9.50 mean steps

real    2m43.196s
user    2m42.342s
sys     0m0.120s

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.

#!/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 $last_x2 = $last*2;

my $my_start = (shift // 0);
my $my_goal  = (shift // 0);

my $LIST = q/list/;
my $PATH = q/path/;
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);

# 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} = {$LIST => {}, # zero length path for identity
                    $PATH => {},
                   };
    # Potential infinite loop, if every goal is not achievable
    for my $goal (1..$last) {
        while (not exists($m->{$goal})) {
            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}{$PATH}};
        $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}++;
    }

    # If you want a specific start/goal path, print it here.
    # Order is not preserved.
    if ($my_start == $start) {
        print "\nSteps for $my_start => $my_goal (not in order):\n";
        for my $path (keys %{$m->{$my_goal}{$PATH}}) {
            print "\t$path = $m->{$my_goal}{$PATH}{$path}\n";
        }
        print "\n";
    }
}

# 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};
    }
}

exit;

use integer;

sub generate {
    my $m = shift;

    my @seen = keys %$m;

    for my $i1 (0..$#seen) {
        my $n1 = $seen[$i1];
        for my $i2 ($i1..$#seen) {
            my $n2 = $seen[$i2];
            for my $op (@ops) {
                my ($result,$expression) = compute($n1,$n2,$op);
                next unless $result;
                next unless ($result < $last_x2); # speedup, might lose some shorter paths
                next if (exists($m->{$result}));
                my $new = $m->{$result} = {};
                # Add these 2 operands to the list, duplicates removed.
                $new->{$LIST} = {%{$m->{$n1}{$LIST}}, $n1 => 1, $n2 => 1};
                # Merge paths, duplicates removed, order is not preserved.
                $new->{$PATH} = {%{$m->{$n1}{$PATH}},
                                 %{$m->{$n2}{$PATH}},
                                 $expression => $result
                                };
            }
        }
    }
}

sub compute {
    my $n1 = shift;
    my $n2 = shift;
    my $op = shift;

    # sort descending, for subtract and divide
    ($n1,$n2) = sort {$b <=> $a} ($n1,$n2);

    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

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?

Edited August 6, 2014 by Quantum.Mechanic

[plasmid]

Unless I'm reading it incorrectly, under Best starts with 10 worst case steps, it seems to say that it takes 10 steps to get from 9 to 13. But that's clearly not optimal.

It isn't giving me quite the same answers when I tried running the code. I set $last to 20 and forced $start to just be 9, and it said the worst case was 9 => 14 in 9 steps. Setting $my_start and $my_goal to 9 and 14 and rearranging the operations, it seemed to have taken

9/9 = 1

9-1 = 8

1+1 = 2

9+9 = 18

18+9 = 27

27+8 = 35

18+1 = 19

19+2 = 21

35-21 = 14

It didn't pick a path like

9/9 = 1

1+1 = 2

2+2 = 4

9+4 = 13 (to get to 13 in four steps)

13+1 = 14 (to get to 14 in five steps)

My best guess about what's going on is that, when it goes through the "generate" subroutine, it just looks at all the numbers that it reached so far and finds some combination of two numbers that have been reached that leads to a number that hasn't been reached yet, without regard to the number of steps it took to reach the intervening numbers. So for example to reach 14: after one round of "generate" the algorithm will have reached 9+9 = 18 and 9/9 = 1. In the second round it could reach 9-1 = 8 and 1+1 = 2 and 18+9 = 27 and 18+1 = 19. In the third round it could reach 27+8 = 35 and 19+2 = 21. Then in the fourth round it could reach 35-21 = 14. So it only takes four rounds of the generate subroutine to reach 14 via that route which requires nine operations, as opposed to five rounds of generate to reach 14 with the five operations shown above. Essentially, it finds the path that invokes generate the fewest number of times rather than the path that uses the smallest number of operations.

[bonanova]

Does it blow memory to keep a tree structure for each starting number?

That's the same storage requirement as a 255x255 matrix.

[Quantum.Mechanic]

My best guess about what's going on is that, when it goes through the "generate" subroutine, it just looks at all the numbers that it reached so far and finds some combination of two numbers that have been reached that leads to a number that hasn't been reached yet, without regard to the number of steps it took to reach the intervening numbers.

 

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.

[Quantum.Mechanic]

Does it blow memory to keep a tree structure for each starting number?

That's the same storage requirement as a 255x255 matrix.

 

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.

[phil1882]

well done guys.

[plasmid]

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.

[Quantum.Mechanic]

 

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.

[Quantum.Mechanic]

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?

 

[plasmid]

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.