Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: puzzle: how many ways to make $100

by jdalbec (Deacon)
on Apr 29, 2006 at 00:07 UTC ( #546444=note: print w/ replies, xml ) Need Help??


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

This is just a variation on partitions where the size of the parts is restricted to a finite set of values. I've adapted some partition code that I had lying around:

#! /usr/bin/perl -w use strict; my @parts = (100, 50, 20, 10, 5, 1); sub partitions { my $n = shift; return partmax($n, $n) }; sub partmax { my ($n, $maxpart) = @_; return [] if $n < 0; return [[]] if $n == 0; my $partitions = []; foreach my $part (grep {$_<=$maxpart} @parts) { my $subpartitions = partmax($n - $part, $part); foreach (@$subpartitions) { unshift @$_, $part; } push @$partitions, @$subpartitions; } return $partitions; } my $example = partitions shift; print "count: ", scalar @$example, "\n"; foreach my $partition (@$example) { print join(" ", @$partition), "\n"; }


Comment on Re: puzzle: how many ways to make $100
Download Code
Re^2: puzzle: how many ways to make $100
by GrandFather (Cardinal) on Apr 29, 2006 at 01:01 UTC

    When I run your code I get the following (partial) output:

    count: 344 100 50 50 50 20 20 10 50 20 20 5 5 50 20 20 5 1 1 1 1 1 50 20 20 1 1 1 1 1 1 1 1 1 1 ... 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 +1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

    which does not quite accord with some of the other results given.


    DWIM is Perl's answer to Gödel
      Updates in bold below.

      You have to change the original line

      my @parts = (100, 50, 20, 10, 5, 1);
      to match the allowed parts when comparing output. In your post (and TedPride's post) you allow $2 bills, so to get the same answer from my code you would change itthe original line above to
      my @parts = (100, 50, 20, 10, 5, 2, 1);
      and then the count matches. In blokhead's post, he uses coins instead of bills, so to get his answer you would change itthe original line above to
      my @parts = (50, 25, 10, 5, 1);
      and then the count matches.

      Further update: My "original" and "change to" lines are not swapped. I'm using "original" and "change to" in reference to the code in my post above. I have added some text above to clarify which line is the "original" line and which lines are the "changed" lines.

      There is a $2 bill. Just try finding one nowadays. Apparently the U.S. MintBureau of Engraving and Printing (thanks for the correction halley) is still printing them, but it must not be issuing large quantities because I almost never see one. I think it's unrealistic to expect to be able to make $100 with 50 $2 bills, for example.

      Also, in the OP's $10 problem, $2 bills were not allowed:
      It took them awhile, but they came up with the correct answer:
      (1 ten), (2 5's), (1 5 and 5 1's), and (10 1's)

        Ah, stupid USA money. Us foreign devils what don't use American money aren't aware of the quirky distribution of the denominations of notes and the OP doesn't actually mention what is available.

        It is interesting to note that the addition of 2 dollar denomination increases the opportunity for making $100 by an order of magnitude.

        Minor point, your "original" and "change to" lines are swapped.

        Update later answers say there ought be a $2 bill. I stick by my original answer.


        DWIM is Perl's answer to Gödel
        There is a $2 bill. Just try finding one nowadays. Apparently the U.S. Mint is still printing them, but it must not be issuing large quantities because I almost never see one. I think it's unrealistic to expect to be able to make $100 with 50 $2 bills, for example.

        Just a total nit, but the US Bureau of Engraving and Printing makes the paper stuff in D.C.; the US Mint makes the coins in Denver and Philadelphia.

        If you visit the USBEP, or their website, you can order as many $2 bills as you like, even in odd collectables such as uncut sheets of multiple consecutively-numbered bills.

        --
        [ e d @ h a l l e y . c c ]

        The two dollar bill is available from banks, like the $1 gold-colored coins. You find $2 bills at racetracks, mostly. People tend to avoid them, because they're so easy to mistake for $1 bills.

        Since the original problem omitted $2 bills, there doesn't seem any compelling reason to include them. But I submit that it's no less reasonable to make change with 50 $2 bills, as it is to do it with 100 $1 bills.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (8)
As of 2014-08-22 23:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (168 votes), past polls