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 17centpiece then the average number of coins that a person carried would be reduced. A reader followed up with, "we do have a 17centpiece, 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[@c1]; # $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:
 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.
 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 $b_{0}.
 Lines 90 90 start timer.
 Lines 91113 compute GCDs.
 Lines 114121 setup for outer loop
 Lines 122174 outer loop (see above).
 Lines 123132 setup for inter loop, GCD calculation
 Lines 133156 inner loop (all the magic happens here in 25 lines).
 Lines 175185 stop the clock, report time, goto end.
 Lines 186194 GCD subroutine.
 Lines 195211 pretty padded print.
References
G. Polya, "On picturewriting," American Mathematical Monthly 63 (1956), 689697.
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
