in reply to Re^2: Challenge: Number of unique ways to reach target sum
in thread Challenge: Number of unique ways to reach target sum

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