in reply to Re^10: Challenge: Number of unique ways to reach target sum
in thread Challenge: Number of unique ways to reach target sum
Nope, that code is only memoized for generation, the output stage is unmemoized and hence very slow.
The semimemoized 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(($S1)*$S/2), $N ); my @all_ways; for my $K ($min .. $max) { my $ways = make_ways( $K1, $S1, $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 fomitpointer (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.


Replies are listed 'Best First'.  

Re^12: Challenge: Number of unique ways to reach target sum
by Limbic~Region (Chancellor) on Feb 16, 2006 at 18:14 UTC  
by fergal (Chaplain) on Feb 16, 2006 at 20:29 UTC 