Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: puzzle: how many ways to make $100

by GrandFather (Cardinal)
on Apr 29, 2006 at 00:44 UTC ( #546446=note: print w/ replies, xml ) Need Help??


in reply to puzzle: how many ways to make $100

Here's a recursive routine that does the trick:

use strict; use warnings; my @values = (100, 50, 20, 10, 5, 2, 1); my $total = 100; my $count = 0; my @results; @values = map {[$_, 0]} @values; # Generate counters and init to 0 findSubSums ($total, 0); print "$_\n" for @results; print scalar @results, " combinations found\n"; sub findSubSums { my ($remaining, $index) = @_; return if $remaining <= 0; my $value = $values[$index][0]; my $counter = \$values[$index][1]; if ($index == $#values) { #Special case for last element $$counter = int ($remaining / $value); dumpResult ($index) if $value * $$counter == $remaining; return; } while ($remaining >= $value * $$counter) { dumpResult ($index), last if $value * $$counter == $remaining; findSubSums ($remaining - $value * $$counter, $index + 1); ++$$counter; } $$counter = 0; # Reset counter } sub dumpResult { my @denoms = grep {$values[$_][1]} (0..shift); push @results, join ' ', map {"\$$values[$_][0] x $values[$_][1]"} + @denoms; return; }

Partial output

$1 x 100 $2 x 1 $1 x 98 $2 x 2 $1 x 96 $2 x 3 $1 x 94 ... $2 x 50 $5 x 1 $1 x 95 $5 x 1 $2 x 1 $1 x 93 $5 x 1 $2 x 2 $1 x 91 ... $5 x 19 $1 x 5 $5 x 19 $2 x 1 $1 x 3 $5 x 19 $2 x 2 $1 x 1 $5 x 20 $10 x 1 $1 x 90 $10 x 1 $2 x 1 $1 x 88 $10 x 1 $2 x 2 $1 x 86 ... $20 x 5 $50 x 1 $1 x 50 $50 x 1 $2 x 1 $1 x 48 $50 x 1 $2 x 2 $1 x 46 $50 x 1 $2 x 3 $1 x 44 $50 x 1 $2 x 4 $1 x 42 ... $50 x 1 $20 x 2 $5 x 2 $50 x 1 $20 x 2 $10 x 1 $50 x 2 $100 x 1 4563 combinations found

DWIM is Perl's answer to Gödel


Comment on Re: puzzle: how many ways to make $100
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://546446]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (9)
As of 2014-12-26 20:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (175 votes), past polls