The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

challenge for a snowy day...
Message #1 Posted by Don Shepherd on 31 Jan 2009, 9:36 a.m.

OK, here's a simple challenge for a snowy day (in Louisville Kentucky USA). How many ways are there to use coins to make $1? Coins are: $1, .50, .25, .10, .05, and the lowly .01.

      
Re: challenge for a snowy day...
Message #2 Posted by Gene Wright on 31 Jan 2009, 9:47 a.m.,
in response to message #1 by Don Shepherd

How many of each coin are present?

One of each or ?

            
Re: challenge for a snowy day...
Message #3 Posted by Don Shepherd on 31 Jan 2009, 9:50 a.m.,
in response to message #2 by Gene Wright

As many as you need to make $1, like one way would be 10 dimes, another way would be 3 quarters + 2 dimes + 5 pennies......

:)

      
Re: challenge for a snowy day...
Message #4 Posted by Allen on 31 Jan 2009, 12:32 p.m.,
in response to message #1 by Don Shepherd

Ironically, The answer is on the last page of the book I'm reading this weekend.

      
Re: challenge for a snowy day...
Message #5 Posted by David Hayden on 31 Jan 2009, 12:39 p.m.,
in response to message #1 by Don Shepherd

I get 293 using a recursive approach. I suspect that some of the members who remember their math better than I do will come up with much more clever solutions.

Below is my solution in RPL. To use it, store the program in 'COINS' (it must be called COINS because it's recursive). Put the list of possible coins, valued highest to lowest on level 2, put the number of cents you're trying to come up with on level 1 and run the program.

Example for the challenge given:

{ 100 50 25 10 5 1 } ENTER
100
COINS
It returns the answer on level 1.

Dave

----------------------------------

@ This is a program to find the number of ways @ to get a total from a set of coins. For example, @ how to get $1.00 from coins worth $1, $0.50, @ $0.25, $0.10, $0.05 and $0.01

@ The program is recursive and assumes it is called @ "COINS"

@ arguments: @ Level 2: list containing the value of each coin @ as an integer. The list must be sorted @ (highest to lowest) @ Level 1: the total that you're looking for. @ @ Results: Total number of ways on level 1. 0. 0. 0. 0. coinList total @ list of coins result @ # ways for this highCoin @ val of highest coin fewerCoins @ coin list without highCoin maxHighCoin @ max # of highCoin @ coins that you can use IF total 0. > coinList SIZE 0. > AND THEN @ initialize local vars coinList HEAD 'highCoin' STO coinList TAIL 'fewerCoins' STO total highCoin / IP 'maxHighCoin' STO

@ 1 solution if you can do it with @ just the highest coin IF highCoin maxHighCoin * total == THEN 'result' INCR DROP END

IF fewerCoins SIZE THEN @ Now add in the solutions with fewer @ coins. For example, if your total is 75 cents @ and your highest coin is a quarter, then @ there's a solution of 75 cents in smaller coins, @ plus 1 quarter and 50 cents in smaller coins, @ plus 2 quarters and 25 cents in smaller coins. 0 maxHighCoin FOR i fewerCoins total i highCoin * - COINS 'result' STO+ NEXT END END result

Edited: 31 Jan 2009, 12:41 p.m.

            
Re: challenge for a snowy day...
Message #6 Posted by Don Shepherd on 31 Jan 2009, 4:21 p.m.,
in response to message #5 by David Hayden

Hi David. I did the brute-force approach in VBScript. It executed in about 3 seconds, and found 293 also.

' find out the number of ways to combine coins to make a dollar (ans=293)
for i = 0 to 1  'dollar
  for j = 0 to 2  'half-dollar
    for k = 0 to 4  'quarter
      for l = 0 to 10  'dime
        for m = 0 to 20  'nickel
          for n = 0 to 100  'penny
            t=i*100+j*50+k*25+l*10+m*5+n
            if t=100 then
              p=p+1
            end if
          next
        next
      next
    next
  next
next
msgbox p
                  
Re: challenge for a snowy day...
Message #7 Posted by Namir on 31 Jan 2009, 4:27 p.m.,
in response to message #6 by Don Shepherd

Good one Don!!!

:-)

Namir

                  
Re: challenge for a snowy day...
Message #8 Posted by Egan Ford on 31 Jan 2009, 4:57 p.m.,
in response to message #6 by Don Shepherd

You can cut your iterations by almost 5x if you treat 5 pennies as a different type of nickle. I.e. 5 will always divide the number of pennies.

Change:

for n = 0 to 100  'penny
  t=i*100+j*50+k*25+l*10+m*5+n
To:
for n = 0 to 20  'penny
  t=i*100+j*50+k*25+l*10+(m+n)*5
            
Re: challenge for a snowy day...
Message #9 Posted by Egan Ford on 31 Jan 2009, 4:51 p.m.,
in response to message #5 by David Hayden

Quote:
more clever solutions.
This problem is discussed in detail in Concrete Mathematics, Ch 7, Generating Functions. Mathematically the answer is:
 6       5       4
( ) + 45( ) + 52( ) + 1 = 293
 4       4       4
50g:
6 4 COMB 5 4 COMB 45 * + 4 4 COMB 52 * + 1 +
I'll try to come up with a general solution for any type of coin and sum.
                  
Re: challenge for a snowy day...
Message #10 Posted by Don Shepherd on 31 Jan 2009, 7:12 p.m.,
in response to message #9 by Egan Ford

Thanks for that reference, Egan, I'm going to check it out. And thanks also for the 5x speed improvement. I noticed that

          for n = 0 to 100 step 5 'penny
has the same effect. I'm going to make that change and try it again on my NSpire. The original version was still running after about 5 minutes when I shut it off. I hate to waste batteries!
                        
Re: challenge for a snowy day...
Message #11 Posted by Egan Ford on 1 Feb 2009, 10:15 a.m.,
in response to message #10 by Don Shepherd

Quote:
I'm going to make that change and try it again on my NSpire. The original version was still running after about 5 minutes when I shut it off. I hate to waste batteries!
There are other simple optimizations that you can also do to reduce your number of iterations. I do not know how do this in basic, but here is my Perl prototype:
$c = 1;
for($i = 0; $i <= 100; $i+=5) {
    for($j = 0; $j <= 100; $j+=5) {
        $A = $i + $j;
        if($A > 100) { last; }
        for($k = 0; $k <= 100; $k+=10) {
            $B = $A + $k;
            if($B > 100) { last; }
            for($l = 0; $l <= 100; $l+=25) {
                $C = $B + $l;
                if($C > 100) { last; }
                for($m = 0; $m <= 100; $m+=50) {
                    if($C + $m == 100) { $c++; }
                }
            }
        }
    }
}
print "$c\n";
IANS, since all of your loops increment, check for excess of 100 and skip rest of loop and inner loops.

Your original program iterated 349965 times. With the 'step 5' for your pennies it will iterate 72765 times. With the above checks only 4758 times. Of course David's recursive approach only iterates 337 times.

I should add that your dollar loop is costing you 2x your time, and if you do the above checks in your loops you will be better off with pennies as your outer loop, then nickels, etc...

Edited: 1 Feb 2009, 10:27 a.m.

                              
Re: challenge for a snowy day...
Message #12 Posted by Don Shepherd on 1 Feb 2009, 12:06 p.m.,
in response to message #11 by Egan Ford

Hi Egan. I was responding when my electricity went out... :(

Quote:
IANS, since all of your loops increment, check for excess of 100 and skip rest of loop and inner loops. Your original program iterated 349965 times. With the 'step 5' for your pennies it will iterate 72765 times. With the above checks only 4758 times. Of course David's recursive approach only iterates 337 times.

I should add that your dollar loop is costing you 2x your time, and if you do the above checks in your loops you will be better off with pennies as your outer loop, then nickels, etc...


IANS? Don't know that one.

OK, I see what you mean about checking for excess of 100 and exiting the loops at that point. Good idea. By my calculations, my original VBScript version iterated 2x3x5x11x21x101 = 699,930 times, and the "step 5" reduced it to 138,600 times, I think. That optimization had little effect on the PC, but it did let the NSpire get the answer in a couple of minutes.

Yes, the dollar loop takes twice as long. If we change the goal to "how many ways can you make change for a dollar" instead of "how many combinations of coins comprise a dollar, including the dollar coin," then we can get rid of the outer dollar loop.

It's an interesting problem. I am intrigued by the use of combinations to solve it. I don't have the book you mentioned; can you elaborate some on why those particular combination parameters work in this problem? Thanks.

                                    
Re: challenge for a snowy day...
Message #13 Posted by Egan Ford on 1 Feb 2009, 1:48 p.m.,
in response to message #12 by Don Shepherd

Quote:
IANS? Don't know that one.
In A Nut Shell
Quote:
Yes, the dollar loop takes twice as long. If we change the goal to "how many ways can you make change for a dollar" instead of "how many combinations of coins comprise a dollar, including the dollar coin," then we can get rid of the outer dollar loop.
Or just get rid of it and add one to your sum, or start with one. I do not think its necessary to calculate the obvious. That is why my iterative counts are 1/2 of yours.
Quote:
It's an interesting problem. I am intrigued by the use of combinations to solve it. I don't have the book you mentioned; can you elaborate some on why those particular combination parameters work in this problem? Thanks.
You've got mail.
            
Re: challenge for a snowy day...
Message #14 Posted by David Hayden on 31 Jan 2009, 8:27 p.m.,
in response to message #5 by David Hayden

Here's my recursive version again in C. On a PC, it gives the answer instantly. Takes one command line argument - the number of cents that you're trying to find (100 in the example)

#include <stdio.h>
#include <stdlib.h>

int ways(int total, int *coins) { int result = 0; int highest; // value of the highest coin int *withoutHighest; // list of coins without highest int maxHighest; // maximum number of "highest" coins // that you can have in a group of "total"

if (total == 0) return 0; if (*coins==0) return 0; // coins list is empty

highest = *coins; withoutHighest = coins+1; maxHighest = total/highest;

if (maxHighest * coins[0] == total) { result += 1; } if (*withoutHighest == 0) { return result; // no coins left } for (int i = 0; i <= maxHighest; ++i) { result += ways(total - i*highest, withoutHighest); } return result; }

int main(int argc, char **argv) { int coins[] = {100, 50, 25, 10, 5, 1, 0}; int total = atoi(argv[1]);

int result = ways(total, coins); printf("%d ways\n", result); return 0; }

                  
Re: challenge for a snowy day...
Message #15 Posted by Don Shepherd on 31 Jan 2009, 8:44 p.m.,
in response to message #14 by David Hayden

Thanks, David. Good work! I'm not conversant in C (or RPL, for that matter), but I respect people who are!

      
Re: challenge for a snowy day...
Message #16 Posted by Paul Dale on 1 Feb 2009, 4:00 p.m.,
in response to message #1 by Don Shepherd

Here is my little solution to the problem in C.

This should be small enough to convert over to a keystroke RPN and still have it finish.

#include <stdio.h>

int main() { int c100, c50, c25, c10, c5; int n = 0;

for (c100=0; c100 <= 100; c100+=100) for (c50 = c100; c50 <= 100; c50 += 50) for (c25 = c50; c25 <= 100; c25 += 25) for (c10 = c25; c10 <= 100; c10 += 10) for (c5=c10; c5<=100; c5 += 5) { printf("%04d: $1 %d\t.50 %d\t.25 %d\t%10 %d\t.05 %d\t.01 %d\n", n++, c100, c50-c100, c25-c50, c10-c25, c5-c10, 100-c5); } return 0; }

- Pauli

      
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #17 Posted by Egan Ford on 4 Feb 2009, 8:20 p.m.,
in response to message #1 by Don Shepherd

Quote:
OK, here's a simple challenge for a snowy day (in Louisville Kentucky USA). How many ways are there to use coins to make $1? Coins are: $1, .50, .25, .10, .05, and the lowly .01.
I finally found some time yesterday to work on this. Below is my Perl prototype I developed with a 41 RPN version in mind. I took an iterative approach since a recursive approach using the same logic would have been more difficult to code for the 41.
my @c = (1,5,10,25,50,100);
my $n = 100;
my $z = 0;
my @b = (1);
  • The array @c contains the coins (sorted).
  • $n is one dollar.
  • $z is the number if iterations.
  • The array @b is initialized with one element, the first element is one.
for(my $i = @c - 1; $i >= 0; $i--) {
    $g[$i] = gcd($c[$i],$g[$i+1]);
}
This first loop caches the GCD from the largest coin to the smallest. The GCD is computed between the last GCD and the current coin.
for(my $i = 0; $i < @c; $i++) {
    for(my $j = $n % $c[$i]; $j <= $n; $j += $g[$i]) {
        if($j - $c[$i] >= 0) {
            $b[$j] = $b[$j - $c[$i]] + $b[$j];
        }
        $z++;
    }
    print $c[$i] . "\t" . $b[$n] . "\t" . $z . "\n";
}
The outer loop iterates through all the coins, while the inner loop counts up the permutations. The inner loop is accelerated by using a step of the cached GCD.

At the end of each coin a running total is printed, e.g.:

1       1       101
5       21      122
10      121     143
25      242     148
50      292     151
100     293     153
The first column is the coin, the 2nd is the number of ways the current and all previous coins can make 100 (one dollar). The last column is the number of iterations required. This is a lot less than the aforementioned 699,930 and 337. As the GCD between pairs of coins gets larger as does the acceleration. One way to cut the iterations in half (specific to this problem) is to use 2 different types of nickels and replace the pennies with one of them. This can only be done if the GCD of all of the coins, the target total ($n = 100), and the first coin are the same. In this case 1 or 5 is safe:
5       1       21
5       21      42
10      121     63
25      242     68
50      292     71
100     293     73
However in the case of the Canadian Quarter a penny must be a penny and not a special nickel:
         Correct                             WRONG!

Canadian Quarter: A while back an article was published about a mathematician that determined if the US had a 17-cent-piece then the average number of coins that a person carried would be reduced. A reader followed up with, "we do have a 17-cent-piece, it is a Canadian Quarter." Before the US economy started to head south, it was actually close to true. :-)

Larger denominations can also be quickly calculated. E.g. by changing @c and $n to:

my @c = (5,5,10,25,50,100,200,500,1000,2000,5000,10000);
my $n = $c[@c-1]; # $n = last value in array @c.
you can quickly calculate all the ways to make change for $100.00:
5       1               2001
5       2001            4002
10      1002001         6003
25      134235101       6404
50      6794128501      6605
100     139946140451    6706
200     1248652567476   6807
500     4292026472606   6828
1000    7980922016001   6839
2000    9764693427886   6850
5000    9823546661905   6853
10000   9823546661906   6855
Most of the work is with the smaller coins. Above, after the number of ways to change $100 with pennies, nickels, and dimes have been calculated the rest quickly add up. I'd be curious how the other posted solutions to this problem would fair. :-)

41CX Version

My 41 version is the same as my Perl version. However, most of the code is fluff (prompting for input, sorting the input, pretty print, etc...).

Limitations:

  1. Because this algorithm requires one register for each penny $n must be <= 100. This can be optimized if the problem is known ahead of time.
  2. I have also restricted the number of coins to <= 9.

Output:

Original Problem:

99 Cents:

Barcode, source, binaries, etc...: http://www.hpmuseum.org/guest/eganford/coins.zip

i41CX: http://sense.net/~egan/41cx

Source:

 01 LBL "COINS"             55 PSE                    109 +                      163 6                      
 02 SIZE?                   56 GTO 04                 110 X<>Y                   164 RCL IND 23             
 03 130                     57 LBL 05                 111 STO IND Y              165 XEQ 16                 
 04 X=Y?                    58 STO 21                 112 DSE 25                 166 ARCL IND 23            
 05 GTO 00                  59 RCL 00                 113 GTO 09                 167 4                      
 06 "SIZE <> 130"           60 1000                   114 1                      168 RCL 24                 
 07 AVIEW                   61 /                      115 STO 27                 169 XEQ 16                 
 08 GTO 20                  62 1                      116 RCL 00                 170 ARCL 24                
 09 LBL 00                  63 +                      117 1000                   171 PRA                    
 10 0                       64 SIGN                   118 /                      172 RUNSW                  
 11 SETSW                   65 LBL 06                 119 1                      173 ISG 25                 
 12 CLRG                    66 LASTX                  120 +                      174 GTO 10                 
 13 FIX 00                  67 LASTX                  121 STO 25                 175 STOPSW                 
 14 CF 29                   68 RCL IND L              122 LBL 10                 176 ADV                    
 15 LBL 01                  69 LBL 07                 123 RCL 25                 177 FIX 06                 
 16 9                       70 X<=NN?                 124 10                     178 RCLSW                  
 17 "N COINS?"              71 GTO 08                 125 +                      179 "TIME: "               
 18 PROMPT                  72 X<>Y                   126 RCL IND X              180 ATIME24                
 19 INT                     73 STO Y                  127 STO 24                 181 PRA                    
 20 X<=Y?                   74 RCL IND X              128 RCL 21                 182 RCL IND 23             
 21 GTO 02                  75 LBL 08                 129 RCL IND 25             183 SF 29                  
 22 "COINS > 9"             76 ISG Y                  130 MOD                    184 FIX 09                 
 23 AVIEW                   77 GTO 07                 131 +                      185 GTO 20                 
 24 PSE                     78 X<> IND L              132 STO 26                 186 LBL 15                 
 25 PSE                     79 STO IND Z              133 LBL 11                 187 X<>Y                   
 26 PSE                     80 ISG L                  134 RCL 26                 188 RCL Y                  
 27 GTO 01                  81 GTO 06                 135 RCL IND 25             189 MOD                    
 28 LBL 02                  82 "N = "                 136 -                      190 X#0?                   
 29 STO 00                  83 ARCL 21                137 X<0?                   191 GTO 15                 
 30 1000                    84 PRA                    138 GTO 12                 192 RDN                    
 31 /                       85 ADV                    139 27                     193 ABS                    
 32 1                       86 "  c      n  gcd"      140 +                      194 RTN                    
 33 +                       87 PRA                    141 RCL IND X              195 LBL 16                 
 34 STO 25                  88 "---  -----  ---"      142 RCL 26                 196 X#0?                   
 35 LBL 03                  89 PRA                    143 27                     197 GTO 18                 
 36 "COIN "                 90 RUNSW                  144 +                      198 RDN                    
 37 ARCL 25                 91 RCL 00                 145 STO 23                 199 1                      
 38 >"?"                    92 10                     146 RDN                    200 LBL 18                 
 39 PROMPT                  93 +                      147 RCL IND 23             201 LOG                    
 40 INT                     94 RCL IND 00             148 +                      202 INT                    
 41 STO IND 25              95 STO IND Y              149 STO IND 23             203 -                      
 42 ISG 25                  96 RCL 00                 150 LBL 12                 204 X=0?                   
 43 GTO 03                  97 1                      151 RCL 24                 205 RTN                    
 44 LBL 04                  98 -                      152 ST+ 26                 206 STO 22                 
 45 100                     99 STO 25                 153 RCL 21                 207 LBL 17                 
 46 "N?"                   100 LBL 09                 154 RCL 26                 208 >" "                   
 47 PROMPT                 101 RCL 25                 155 X<=Y?                  209 DSE 22                 
 48 INT                    102 11                     156 GTO 11                 210 GTO 17                 
 49 X<=Y?                  103 +                      157 STOPSW                 211 RTN                    
 50 GTO 05                 104 RCL IND X              158 CLA                    212 LBL 20                 
 51 "N > 100"              105 RCL IND 25             159 2                      213 END                    
 52 AVIEW                  106 XEQ 15                 160 RCL IND 25             
 53 PSE                    107 RCL 25                 161 XEQ 16                 
 54 PSE                    108 10                     162 ARCL IND 25            
  • Lines 01- 08 check for a SIZE of 130.
  • Lines 09- 58 prompt for the number of coins and the value of each and the sum.
  • Lines 59- 81 sort the input from low to high.
  • Lines 82- 89 print header and setup $n and $b0.
  • Lines 90- 90 start timer.
  • Lines 91-113 compute GCDs.
  • Lines 114-121 setup for outer loop
  • Lines 122-174 outer loop (see above).
  • Lines 123-132 setup for inter loop, GCD calculation
  • Lines 133-156 inner loop (all the magic happens here in 25 lines).
  • Lines 175-185 stop the clock, report time, goto end.
  • Lines 186-194 GCD subroutine.
  • Lines 195-211 pretty padded print.

References

G. Polya, "On picture-writing," American Mathematical Monthly 63 (1956), 689-697.

2nd Challenge

When Polya wrote about this problem in 1956 the US did not have 50 state quarters (or 50 states :-). Answer the original question, but consider the value and type of each quarter.

Update: fixed GCD issues

Edited: 10 Feb 2009, 1:27 a.m. after one or more responses were posted

            
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #18 Posted by Don Shepherd on 4 Feb 2009, 9:17 p.m.,
in response to message #17 by Egan Ford

Absolutely fascinating. Thanks to Egan and all who participated. Such elegant and insightful solutions to a simple problem! I showed the problem (and solution) to my middle school kids and they were fascinated as well.

            
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #19 Posted by David Hayden on 5 Feb 2009, 9:13 a.m.,
in response to message #17 by Egan Ford

Thanks for the detailed description of your solution Egan. I particularly appreciate the explanation of the code.

Dave

            
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #20 Posted by Paul Dale on 5 Feb 2009, 4:49 p.m.,
in response to message #17 by Egan Ford

Would this run faster if you treat the pennies like I did and compute them last up as the difference between the rest of the coins and the target value? I guess a possible slight loss of generality for a currency without a unit cent (like ours BTW).

The extended challenge is an interesting extension but shouldn't be a lot harder -- think combinations and permutations.

- Pauli

                  
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #21 Posted by Egan Ford on 5 Feb 2009, 8:48 p.m.,
in response to message #20 by Paul Dale

Quote:
Would this run faster if you treat the pennies like I did and compute them last up as the difference between the rest of the coins and the target value? I guess a possible slight loss of generality for a currency without a unit cent (like ours BTW).
Give it a go.
Quote:
The extended challenge is an interesting extension but shouldn't be a lot harder -- think combinations and permutations.
It is not that hard. A 10 digit model can find the answer.
            
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #22 Posted by David Hayden on 5 Feb 2009, 9:37 p.m.,
in response to message #17 by Egan Ford

Quote:
The inner loop is accelerated by using a step of the GCD of the current and the next coin (that is why the last coin is doubled, the alternative would be to check for last coin and then step that value, but then each outer loop would have an extra "if" statement--the goal was to optimize for the 41).

The gcd trick works for the original challenge, but not for the case of the Canadian quarter. For that case (adding a coin worth 17 cents), I get 608 combinations, not 152.

I believe the GCD trick only works when each coin is worth an even multiple of the next cheapest coin.

                  
Re: challenge for a snowy day..., Fast 41CX version, Canadian Quarters, a 2nd Challenge, and more...
Message #23 Posted by Egan Ford on 10 Feb 2009, 1:33 a.m.,
in response to message #22 by David Hayden

My original (non accelerated) version got 608 as well. In my haste to post before vacation I did not verify all output (my bad).

I have updated my previous post with a different GCD calculation. This time it starts from the largest to the smallest. The GCD is computed from the previous GCD and the current coin. This allows the same acceleration with the original problem and some acceleration with the Canadian Quarter.

Edited: 10 Feb 2009, 1:38 a.m.

            
50 State Quarters Solution
Message #24 Posted by Egan Ford on 10 Feb 2009, 10:27 a.m.,
in response to message #17 by Egan Ford

Quote:
OK, here's a simple challenge for a snowy day (in Louisville Kentucky USA). How many ways are there to use coins to make $1? Coins are: $1, .50, .25, .10, .05, and the lowly .01.
Quote:
2nd Challenge

When Polya wrote about this problem in 1956 the US did not have 50 state quarters (or 50 states :-). Answer the original question, but consider the value and type of each quarter.


No takers?

The answer is: 650868

Perl Prototype

#!/usr/bin/perl
my @c = (5,5,10,25,50,100,100);
my $n = 100;
my $z = 0;
my @b = (1);
for(my $i = 0; $i < @c - 1; $i++) {
    my $g = gcd($c[$i],$c[$i+1]);
    for(my $j = $n % $c[$i]; $j <= $n; $j += $g) {
        if($j - $c[$i] >= 0) {
            $b[$j/5] = $b[($j - $c[$i])/5] + $b[$j/5];
        }
        $z++;
    }
    print $c[$i] . "\t" . $b[$n/5] . "\t" . $z . "\n";
    if($c[$i] != 25) { next }
    $k++;
    if($k > 50) { next }
    $i--;
}
Previous version differences:
  1. 5 pennies must be a special nickel to conserve memory.
  2. GCD is not cached and is calculated up. This was required to conserve memory and will work in most cases where the GCD of the next larger coin matches the current or previous coin.
  3. The addresses for the @b array are divided by 5 to reduce the number of registered required to 21 (that is why pennies must be grouped).
  4. There is a hack at the bottom that continues through all 51 quarters (50 state and one regular).
Results:
  5       1   21       25    9526  123       25   77692  193       25  293691  263      
  5      21   42       25   11613  128       25   86926  198       25  317912  268      
 10     121   63       25   14009  133       25   96938  203       25  343576  273      
 25     242   68       25   16741  138       25  107769  208       25  370738  278      
 25     426   73       25   19837  143       25  119461  213       25  399454  283      
 25     688   78       25   23326  148       25  132057  218       25  429781  288      
 25    1044   83       25   27238  153       25  145601  223       25  461777  293      
 25    1511   88       25   31604  158       25  160138  228       25  495501  298      
 25    2107   93       25   36456  163       25  175714  233       25  531013  303      
 25    2851   98       25   41827  168       25  192376  238       25  568374  308      
 25    3763  103       25   47751  173       25  210172  243       25  607646  313      
 25    4864  108       25   54263  178       25  229151  248       25  648892  318      
 25    6176  113       25   61399  183       25  249363  253       50  650867  321      
 25    7722  118       25   69196  188       25  270859  258      100  650868  323      
The first column is the coin, the 2nd is the number of ways the current and all previous coins can make 100 (one dollar). The last column is the number of iterations required. In this case only 323 iterations where required to find the solution. On a PC this takes a second. A 41 takes a bit longer (~5.5 minutes).

To verify my results I wrote a program to generate a brute force program (see end of post).

41CX Version

In addition to the above the following differs from my previous version:

  1. Hardcoded coins and sum.
  2. No requirement for SIZE 130 (SIZE 40 will do).
  3. No GCD printed.
Barcode, source, binaries, etc...: http://www.hpmuseum.org/guest/eganford/coins2.zip

i41CX: http://sense.net/~egan/41cx

Source:

 01 LBL "COINS2"         38 STO 10               75 ST+ 11              112 ATIME24             
 02 0                    39 LBL 10               76 RCL 16              113 PRA                 
 03 SETSW                40 RCL 10               77 RCL 11              114 RCL IND 14          
 04 CLRG                 41 1                    78 X<=Y?               115 SF 29               
 05 FIX 00               42 +                    79 GTO 11              116 FIX 09              
 06 CF 29                43 RCL IND X            80 STOPSW              117 GTO 99              
 07 6                    44 RCL IND 10           81 CLA                 118 LBL 30              
 08 STO 00               45 XEQ 30               82 2                   119 X<>Y                
 09 5                    46 STO 13               83 RCL IND 10          120 RCL Y               
 10 STO 01               47 RCL 16               84 XEQ 40              121 MOD                 
 11 STO 02               48 RCL IND 10           85 ARCL IND 10         122 X#0?                
 12 10                   49 MOD                  86 8                   123 GTO 30              
 13 STO 03               50 +                    87 RCL IND 14          124 RDN                 
 14 25                   51 STO 11               88 XEQ 40              125 ABS                 
 15 STO 04               52 LBL 11               89 ARCL IND 14         126 RTN                 
 16 50                   53 RCL 11               90 PRA                 127 LBL 40              
 17 STO 05               54 RCL IND 10           91 RUNSW               128 X#0?                
 18 100                  55 -                    92 RCL IND 10          129 GTO 42              
 19 STO 06               56 X<0?                 93 25                  130 RDN                 
 20 STO 07               57 GTO 12               94 X#Y?                131 1                   
 21 STO 16               58 5                    95 GTO 13              132 LBL 42              
 22 "N = "               59 /                    96 1                   133 LOG                 
 23 ARCL 16              60 17                   97 ST+ 09              134 INT                 
 24 PRA                  61 +                    98 50                  135 -                   
 25 ADV                  62 RCL IND X            99 RCL 09              136 X=0?                
 26 "  c        n"       63 RCL 11              100 X>Y?                137 RTN                 
 27 PRA                  64 5                   101 GTO 13              138 STO 15              
 28 "---  -------"       65 /                   102 1                   139 LBL 41              
 29 PRA                  66 17                  103 ST- 10              140 >" "                
 30 RUNSW                67 +                   104 LBL 13              141 DSE 15              
 31 1                    68 STO 14              105 ISG 10              142 GTO 41              
 32 STO 17               69 RDN                 106 GTO 10              143 RTN                 
 33 RCL 00               70 RCL IND 14          107 ADV                 144 LBL 99              
 34 1000                 71 +                   108 STOPSW              145 END                 
 35 /                    72 STO IND 14          109 FIX 06              
 36 1                    73 LBL 12              110 RCLSW               
 37 +                    74 RCL 13              111 "TIME: "            
Output:

Brute Force (25 second run time on a modern computer):

#!/usr/bin/perl
$n=1;
for($v0 = 0; $v0 <= 100; $v0+=5) { $w0 = $v0;
for($v1 = 0; $v1 <= 100; $v1+=5) { $w1 = $v1 + $w0; if($w1 > 100) { last }
for($v2 = 0; $v2 <= 100; $v2+=10) { $w2 = $v2 + $w1; if($w2 > 100) { last }
for($v3 = 0; $v3 <= 100; $v3+=25) { $w3 = $v3 + $w2; if($w3 > 100) { last }
for($v4 = 0; $v4 <= 100; $v4+=25) { $w4 = $v4 + $w3; if($w4 > 100) { last }
for($v5 = 0; $v5 <= 100; $v5+=25) { $w5 = $v5 + $w4; if($w5 > 100) { last }
for($v6 = 0; $v6 <= 100; $v6+=25) { $w6 = $v6 + $w5; if($w6 > 100) { last }
for($v7 = 0; $v7 <= 100; $v7+=25) { $w7 = $v7 + $w6; if($w7 > 100) { last }
for($v8 = 0; $v8 <= 100; $v8+=25) { $w8 = $v8 + $w7; if($w8 > 100) { last }
for($v9 = 0; $v9 <= 100; $v9+=25) { $w9 = $v9 + $w8; if($w9 > 100) { last }
for($v10 = 0; $v10 <= 100; $v10+=25) { $w10 = $v10 + $w9; if($w10 > 100) { last }
for($v11 = 0; $v11 <= 100; $v11+=25) { $w11 = $v11 + $w10; if($w11 > 100) { last }
for($v12 = 0; $v12 <= 100; $v12+=25) { $w12 = $v12 + $w11; if($w12 > 100) { last }
for($v13 = 0; $v13 <= 100; $v13+=25) { $w13 = $v13 + $w12; if($w13 > 100) { last }
for($v14 = 0; $v14 <= 100; $v14+=25) { $w14 = $v14 + $w13; if($w14 > 100) { last }
for($v15 = 0; $v15 <= 100; $v15+=25) { $w15 = $v15 + $w14; if($w15 > 100) { last }
for($v16 = 0; $v16 <= 100; $v16+=25) { $w16 = $v16 + $w15; if($w16 > 100) { last }
for($v17 = 0; $v17 <= 100; $v17+=25) { $w17 = $v17 + $w16; if($w17 > 100) { last }
for($v18 = 0; $v18 <= 100; $v18+=25) { $w18 = $v18 + $w17; if($w18 > 100) { last }
for($v19 = 0; $v19 <= 100; $v19+=25) { $w19 = $v19 + $w18; if($w19 > 100) { last }
for($v20 = 0; $v20 <= 100; $v20+=25) { $w20 = $v20 + $w19; if($w20 > 100) { last }
for($v21 = 0; $v21 <= 100; $v21+=25) { $w21 = $v21 + $w20; if($w21 > 100) { last }
for($v22 = 0; $v22 <= 100; $v22+=25) { $w22 = $v22 + $w21; if($w22 > 100) { last }
for($v23 = 0; $v23 <= 100; $v23+=25) { $w23 = $v23 + $w22; if($w23 > 100) { last }
for($v24 = 0; $v24 <= 100; $v24+=25) { $w24 = $v24 + $w23; if($w24 > 100) { last }
for($v25 = 0; $v25 <= 100; $v25+=25) { $w25 = $v25 + $w24; if($w25 > 100) { last }
for($v26 = 0; $v26 <= 100; $v26+=25) { $w26 = $v26 + $w25; if($w26 > 100) { last }
for($v27 = 0; $v27 <= 100; $v27+=25) { $w27 = $v27 + $w26; if($w27 > 100) { last }
for($v28 = 0; $v28 <= 100; $v28+=25) { $w28 = $v28 + $w27; if($w28 > 100) { last }
for($v29 = 0; $v29 <= 100; $v29+=25) { $w29 = $v29 + $w28; if($w29 > 100) { last }
for($v30 = 0; $v30 <= 100; $v30+=25) { $w30 = $v30 + $w29; if($w30 > 100) { last }
for($v31 = 0; $v31 <= 100; $v31+=25) { $w31 = $v31 + $w30; if($w31 > 100) { last }
for($v32 = 0; $v32 <= 100; $v32+=25) { $w32 = $v32 + $w31; if($w32 > 100) { last }
for($v33 = 0; $v33 <= 100; $v33+=25) { $w33 = $v33 + $w32; if($w33 > 100) { last }
for($v34 = 0; $v34 <= 100; $v34+=25) { $w34 = $v34 + $w33; if($w34 > 100) { last }
for($v35 = 0; $v35 <= 100; $v35+=25) { $w35 = $v35 + $w34; if($w35 > 100) { last }
for($v36 = 0; $v36 <= 100; $v36+=25) { $w36 = $v36 + $w35; if($w36 > 100) { last }
for($v37 = 0; $v37 <= 100; $v37+=25) { $w37 = $v37 + $w36; if($w37 > 100) { last }
for($v38 = 0; $v38 <= 100; $v38+=25) { $w38 = $v38 + $w37; if($w38 > 100) { last }
for($v39 = 0; $v39 <= 100; $v39+=25) { $w39 = $v39 + $w38; if($w39 > 100) { last }
for($v40 = 0; $v40 <= 100; $v40+=25) { $w40 = $v40 + $w39; if($w40 > 100) { last }
for($v41 = 0; $v41 <= 100; $v41+=25) { $w41 = $v41 + $w40; if($w41 > 100) { last }
for($v42 = 0; $v42 <= 100; $v42+=25) { $w42 = $v42 + $w41; if($w42 > 100) { last }
for($v43 = 0; $v43 <= 100; $v43+=25) { $w43 = $v43 + $w42; if($w43 > 100) { last }
for($v44 = 0; $v44 <= 100; $v44+=25) { $w44 = $v44 + $w43; if($w44 > 100) { last }
for($v45 = 0; $v45 <= 100; $v45+=25) { $w45 = $v45 + $w44; if($w45 > 100) { last }
for($v46 = 0; $v46 <= 100; $v46+=25) { $w46 = $v46 + $w45; if($w46 > 100) { last }
for($v47 = 0; $v47 <= 100; $v47+=25) { $w47 = $v47 + $w46; if($w47 > 100) { last }
for($v48 = 0; $v48 <= 100; $v48+=25) { $w48 = $v48 + $w47; if($w48 > 100) { last }
for($v49 = 0; $v49 <= 100; $v49+=25) { $w49 = $v49 + $w48; if($w49 > 100) { last }
for($v50 = 0; $v50 <= 100; $v50+=25) { $w50 = $v50 + $w49; if($w50 > 100) { last }
for($v51 = 0; $v51 <= 100; $v51+=25) { $w51 = $v51 + $w50; if($w51 > 100) { last }
for($v52 = 0; $v52 <= 100; $v52+=25) { $w52 = $v52 + $w51; if($w52 > 100) { last }
for($v53 = 0; $v53 <= 100; $v53+=25) { $w53 = $v53 + $w52; if($w53 > 100) { last }
for($v54 = 0; $v54 <= 100; $v54+=50) { $w54 = $v54 + $w53; if($w54 > 100) { last }
if($w54 == 100) {$n++}
}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
print "$n\n";


[ Return to Index | Top of Index ]

Go back to the main exhibit hall