challenge for a snowy day... « Next Oldest | Next Newest »

 ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 01-31-2009, 09:36 AM 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. ▼ Gene Wright Posting Freak Posts: 1,545 Threads: 168 Joined: Jul 2005 01-31-2009, 09:47 AM How many of each coin are present? One of each or ? ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 01-31-2009, 09:50 AM 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...... :) Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 01-31-2009, 12:32 PM David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 01-31-2009, 12:39 PM 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. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 01-31-2009, 04:21 PM 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 ``` ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 01-31-2009, 04:27 PM Good one Don!!! :-) Namir Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 01-31-2009, 04:57 PM 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 ``` Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 01-31-2009, 04:51 PM 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. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 01-31-2009, 07:12 PM 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! ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 02-01-2009, 10:15 AM 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. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 02-01-2009, 12:06 PM 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. ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 02-01-2009, 01:48 PM 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. David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 01-31-2009, 08:27 PM 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 #include 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 == 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); int result = ways(total, coins); printf("%d ways\n", result); return 0; } ``` ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 01-31-2009, 08:44 PM Thanks, David. Good work! I'm not conversant in C (or RPL, for that matter), but I respect people who are! Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 02-01-2009, 04:00 PM 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 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 Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 02-04-2009, 08:20 PM 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: 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 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 ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 02-04-2009, 09:17 PM 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. David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 02-05-2009, 09:13 AM Thanks for the detailed description of your solution Egan. I particularly appreciate the explanation of the code. Dave Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 02-05-2009, 04:49 PM 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 ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 02-05-2009, 08:48 PM 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. David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 02-05-2009, 09:37 PM 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. ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 02-10-2009, 01:33 AM 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. Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 02-10-2009, 10:27 AM 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: 5 pennies must be a special nickel to conserve memory. 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. 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). 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: Hardcoded coins and sum. No requirement for SIZE 130 (SIZE 40 will do). No GCD printed. Barcode, source, binaries, etc...: http://www.hpmuseum.org/guest/eganford/coins2.zip 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"; ```

 Possibly Related Threads... Thread Author Replies Views Last Post An amazing day: Giving a talk at HP about their calculators Geir Isene 9 3,256 12-16-2013, 06:14 PM Last Post: aurelio HHC 2013 Day 2 Highlights Eddie W. Shore 6 1,818 09-23-2013, 04:03 PM Last Post: Kimberly Thompson HHC 2013: Day 1 Highlights Eddie W. Shore 28 5,565 09-23-2013, 03:22 PM Last Post: Brad Barton Happy Mother's Day! Eddie W. Shore 1 867 05-12-2013, 11:35 AM Last Post: Walter B happy fibonacci day 5/8/13 Allen 8 2,170 05-09-2013, 01:48 AM Last Post: Gerson W. Barbosa Stupid idea of the day: 41-compatible watch bhtooefr 0 741 03-31-2013, 08:23 AM Last Post: bhtooefr OT: Happy Pi Day! Eddie W. Shore 13 2,590 03-22-2013, 10:44 AM Last Post: Les Koller Totally OT ... Pi Day for my car Maximilian Hohmann 18 3,237 03-10-2013, 01:15 PM Last Post: chris smith [OT] Happy Father's Day! Les Wright 7 1,747 06-18-2012, 07:54 AM Last Post: Andrés C. Rodríguez (Argentina) Happy PI Day from Europe Raymund Heuvel 22 4,243 03-14-2012, 09:19 AM Last Post: Eddie W. Shore

Forum Jump: 