Just another Perl shrine PerlMonks

### comment on

 Need Help??
Here's a kinda lispish solution. It's recursive and to generate the solution it calls the breakup function 46 times (thanks to the magic of Memoize).

The basic idea is that breakup is called with a target and a list of usable notes it then subtracts the biggest usable note from the target and calls breakup with the new target and the list of usable notes. When it's got all the possible solutions it can get it crosses the largest note off the list and tries again.

The cleverness comes in where instead of passing in the array of available notes, I just pass in a number that indicates how many notes have been crossed off so far. So in breakup(100, 0) the 0 indicates that all of [100,50,20,10,5] are available, whereas a 2 would mean that only [20,10,5] are available.

breakup being a function of 2 scalars makes it ideal for Memoize. This basically means it caches the results of the function calls so that for example when we are calculating

```100 = 50 + 10 + 10 + 10 + 10 + 10
the 10s will come from a call to breakup(50, 3) but we'll also call breakup(50,3) when we're calculating
```100 = 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10
Memoize means the second time we call it, we get the result for free. Without Memoize it require 411 calls, almost 10 times as many.

Here's the output (in case I missed a solution)

```100
50, 50
50, 20, 20, 10
50, 20, 20, 5, 5
50, 20, 10, 10, 10
50, 20, 10, 10, 5, 5
50, 20, 10, 5, 5, 5, 5
50, 20, 5, 5, 5, 5, 5, 5
50, 10, 10, 10, 10, 10
50, 10, 10, 10, 10, 5, 5
50, 10, 10, 10, 5, 5, 5, 5
50, 10, 10, 5, 5, 5, 5, 5, 5
50, 10, 5, 5, 5, 5, 5, 5, 5, 5
50, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 20, 20, 20
20, 20, 20, 20, 10, 10
20, 20, 20, 20, 10, 5, 5
20, 20, 20, 20, 5, 5, 5, 5
20, 20, 20, 10, 10, 10, 10
20, 20, 20, 10, 10, 10, 5, 5
20, 20, 20, 10, 10, 5, 5, 5, 5
20, 20, 20, 10, 5, 5, 5, 5, 5, 5
20, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 10, 10, 10, 10, 10, 10
20, 20, 10, 10, 10, 10, 10, 5, 5
20, 20, 10, 10, 10, 10, 5, 5, 5, 5
20, 20, 10, 10, 10, 5, 5, 5, 5, 5, 5
20, 20, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 10, 10, 10, 10, 10, 10, 10
20, 10, 10, 10, 10, 10, 10, 10, 5, 5
20, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5
20, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5
20, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 10, 10, 10, 10, 10, 10
10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 5
10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5
10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
count = 46
I like the pattern it makes :-)
```use strict;
use warnings;

my @all = (100, 50, 20, 10, 5);

use Memoize;

memoize('breakup');

my \$count = 0;
sub nice
{
my (\$target, \$sub) = @_;
my @solns = breakup(\$target, \$sub);
foreach my \$sol (@solns)
{
print join(", ", @\$sol)."\n";
}
}
nice(100, 0);
print "count = \$count\n";

sub breakup
{
my (\$target, \$sub) = @_;
\$count++;

my \$cur = \$all[\$sub];

my @solns;
if (\$target == \$cur)
{
push(@solns, [\$cur]);
}

if (\$target >= \$cur)
{
push(@solns, map {[\$cur, @\$_]} (breakup(\$target - \$cur, \$sub)));
}

push(@solns, breakup(\$target, \$sub + 1)) unless (\$sub == \$#all);

return @solns;
}

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.
• 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: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2020-10-26 22:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite web site is:

Results (254 votes). Check out past polls.

Notices?