When I came back it was using 500M of memory (growing very very slowly) and was clocking 1.9M answers per second which puts it at a total time between 2 and 3 hours. Which isn't bad.

I'm leaving it running overnight on a machine to verfiy that.

By the way, to store the answers would require > 400GB of space!

The code below has functions. string_ways() generates an array of strings from a tree of ways of summing things, it's memoized. nasty_print_ways() is like print_ways() but it also takes a depth. When it reaches that depth it starts making calls to string_ways() to get lists of strings to finish off the current way. This avoids recomputing a lot of stuff. You can adjust the depth if you have more or less memory but I think a change of 1 results in about a 100-fold difference in memory usage.

This dumps out performance other stats every million lines. You get how many have been printed, how many times string_ways was called, how many times it was really called (that is the memoization didn't help us) and a rate of lines/CPU second

nasty_print_ways($ways, "", 6);

# do my own memoizing as I couldn't get Memoize to work, possibly
# to do with the arguments being array refs
my %strings;
my $real_stringed = 0;
sub string_ways {
  my $ways = $_[0];

  if (my $strings = $strings{$ways})
  {
    #die "already $strings";
    return $strings
  }
  $real_stringed++;
  my @strings;
  for my $way (@$ways) {
    if (ref $way) {
      my ($coin, $more_ways) = @$way;
      # print STDERR "coin is $coin, making ".@{$more_ways}." ways\n";
      push(@strings, map {"$_+$coin"} (@{string_ways($more_ways)}));
    } else {
      push(@strings, $way);
    }
  }

  return $strings{$ways} = \@strings;
}

my $stringed = 0;
sub nasty_print_ways {
  my ($ways, $base, $depth) = @_;

  if ($depth == 0) {
      $stringed++;
      my $strings = string_ways($ways);
      for my $string (@$strings) {
          $printed++;
          print STDERR "p/s/r $printed / $stringed / $real_stringed  r
+ate = ".($printed/(times())[0])."\n" unless ($printed % 1000000);
          print "$string+$base\n";
        }
  }
  else {
    $depth--;
    for my $way (@$ways) {
      if (ref $way) {
        my ($coin, $more_ways) = @$way;
        my $new_base = length($base) ? "$coin+$base" : $coin;
        nasty_print_ways($more_ways, $new_base, $depth);
      } else {
        print STDERR "printed $printed\n" unless (++$printed % 100000)
+;
        print "way+$base\n";
      }
    }
  }
}
[download]