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";
}
}
}
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.