Nope, that code is only memoized for generation, the output stage is unmemoized and hence very slow.
The semi-memoized output code is in my followup. Here's the whole thing joined up and ready to run.
use List::Util 'min';
use POSIX 'ceil';
use strict;
use warnings;
sub make_ways {
my ($N, $S, $T) = @_;
# one coin left can we do it?
if ($S == 1) {
if ($T <= $N) {
return ["$T"];
} else {
return 0;
}
}
my $min = (2*$T-$S+$S**2)/(2*$S); ## more correctly, ceil() of thi
+s
my $max = min( $T-(($S-1)*$S/2), $N );
my @all_ways;
for my $K ($min .. $max) {
my $ways = make_ways( $K-1, $S-1, $T-$K );
if ($ways) {
push(@all_ways, ["$K", $ways]);
}
}
if (@all_ways) {
return \@all_ways;
} else {
return 0
}
}
use Memoize;
memoize 'make_ways';
my $ways = make_ways(100, 10, 667);
my $printed = 0;
nasty_print_ways($ways, "", 6);
print "$printed\n";
# do my own memoizing as I couldn't get Memoize to work, for this func
+tion
# possibly to do with the arguments being array refs
my %strings;
sub string_ways {
my $ways = $_[0];
if (my $strings = $strings{$ways})
{
#die "already $strings";
return $strings
}
my @strings;
for my $way (@$ways) {
if (ref $way) {
my ($coin, $more_ways) = @$way;
push(@strings, map {"$_+$coin"} (@{string_ways($more_ways)}));
} else {
push(@strings, $way);
}
}
return $strings{$ways} = \@strings;
}
sub nasty_print_ways {
my ($ways, $base, $depth) = @_;
if ($depth == 0) {
my $strings = string_ways($ways);
for my $string (@$strings) {
$printed++;
#print STDERR "$printed\n" unless ($printed % 10000000);
#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 "$base+$way\n";
}
}
}
}
The reason I wanted you to run blokheads quick code was to be able to get a quick comparison of my machine and your machine. It's not important.
I ran your C and it took 2 or 3 hours. I'm running it again with your optimisations, although that fomit-pointer (or whatever it was) make my gcc complain.
By the way, your code printed out -114xxx. That's because
j is a double (a kind of float) and you format is "%d" but %d is for int. I've changed j to unsigned long long int and printf("%lld", j). I'm waiting for it to complete.