RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest was about arranging numbers and arithmetical operations.

For the first part, I visualised eight slots between the numbers, each of which could contain +, - or nothing at all. 3^8 is only 6,561, which should present no difficulty in an exhaustive search.

my @base=(1..9);
my @sv=('','-','+');

my $maxdepth=8;
my @si=(0) x $maxdepth;

while (1) {

For each possible combination, we evaluate it and list it if it's a success.

  my $str=join('',map {$base[$_].$sv[$si[$_]]} (0..$maxdepth-1)).$base[$maxdepth];
  my $tot=eval($str);
  if ($tot == 100) {
    print "$str\n";
  }

Then do a standard nested loop increment: start with slot 0 and carry forward when it overflows.

  my $i=0;
  while ($i < $maxdepth) {
    $si[$i]++;
    if ($si[$i] <= $#sv) {
      last;
    }
    $si[$i]=0;
    $i++;
  }
  if ($i >= $maxdepth) {
    last;
  }
}

Perl6 is the same, but eval has been sort-of removed from the language; there's an EVAL function (surrounded with dire warnings), which is desperately slow. On my desktop box, my code above runs in 0.07 seconds; on the same machine, the Perl6 version, which is basically identical apart from syntax details, takes 51.

For the second problem, I decided to do this the amusing way. So I build a list of (working total, operation chain) pairs, starting with 1 and an empty list.

my @seq=([1,[]]);
my $goal=200;

while (1) {

Each time I pull an item off the top of the list, I see if it's the goal (in which case it's a shortest path to the goal, so we print the path and exit).

  my $s=shift @seq;
  if ($s->[0] == $goal) {
    print join(', ',map {['double','add 1']->[$_]} @{$s->[1]}),"\n";
    last;
  }

Otherwise, we create two more list entries, one with each possible path from this point (doubling or adding).

  push @seq,[$s->[0]*2,[@{$s->[1]},0]];
  push @seq,[$s->[0]+1,[@{$s->[1]},1]];
}

On the other hand this is basically just a binary decomposition, if we regard the "double" operation as "add a zero at the end of the number" and the "add 1" operation as "turn the trailing zero to a 1". Thus the Perl6 solution:

my $goal=200;
my @stack;
for sprintf('%b',$goal).split('',:skip-empty) -> $op {
  push @stack,'double';
  if ($op == 1) {
    push @stack,'add 1';
  }
}
@stack.shift;
@stack.shift;

say join(', ',@stack);