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]

In reply to Re^3: Challenge: Number of unique ways to reach target sum by fergal
in thread Challenge: Number of unique ways to reach target sum by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.