Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
The code can be made to not only count the solutions, but to iterate over them as well (using a callback & accumulation of the solution): ... But this takes a lot longer, as memoizing does you no good.

No need to abandon Memoize. First generate all the answers (takes about 6 seconds on my computer, your original takes about a second less just to count them), then print them out (this can take considerably longer depending on the format.

The key is to not generate strings in the first stage but to generate a tree (a very lispish tree). So say our target is 197 and we can use 2 coins. We would generate

$VAR1 = [ [ '99', [ '98' ] ], [ '100', [ '97' ] ] ];

You can see that there are 2 possibilities, 100+97 and 99+98. Slightly more complex 3 coins and a target of 295 the result is

$VAR1 = [ [ '100', [ [ '98', [ '97' ] ], [ '99', [ '96' ] ] ] ] ];

This you can think of this as 100 + (98+97 or 99+96).

In some ways you can say that just dumping out this stucture answers the question. Recursing over it and printing out x+y+...+z for each solution goes at a bit more than 100,000 results per second on my computer (which is slower than I'd expected).

Memory-wise, this is very efficient because when the same subtree appears in 2 places, you don't get 2 copies, you just get a reference to the same subtree.

It is possible to use memoization for the printing process too but the problem is that you can't memoize the whole thing or you'll run out of memory. I've written something that starts to use memoized data after a certain level and it's doing > 1 million per second (and it's accelerating as it benefits more and more from the cache). I reckon it should take about 3 hours but I don't know how much acceleration there is so I'm going for a bath :)

Code for the simpler version is below (based on blokhead's original)

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'; #useful for printing out details of a sane set use Data::Dumper; my $ways = make_ways(100, 10, 667); #my $ways = make_ways(20, 5, 30); #print Dumper($ways); print_ways($ways, "", 3); my $printed = 0; sub print_ways { my ($ways, $base) = @_; for my $way (@$ways) { if (ref $way) { my ($coin, $more_ways) = @$way; my $new_base = length($base) ? "$coin+$base" : $coin; print_ways($more_ways, $new_base); } else { print STDERR "printed $printed\n" unless (++$printed % 1000000); print "$base+$way\n"; } } }

In reply to Re^2: 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, 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, 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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    [Corion]: Tabish: What are "tow" packages? Maybe you want to use PAR::Packer to copy them and your main program into one (ugly) script for distribution?

    How do I use this? | Other CB clients
    Other Users?
    Others having an uproarious good time at the Monastery: (4)
    As of 2017-12-11 09:55 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      What programming language do you hate the most?




















      Results (288 votes). Check out past polls.

      Notices?