▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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.
▼
Posts: 1,545
Threads: 168
Joined: Jul 2005
How many of each coin are present?
One of each or ?
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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......
:)
Posts: 562
Threads: 27
Joined: Oct 2006
Posts: 528
Threads: 40
Joined: Dec 2008
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.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
Good one Don!!!
:-)
Namir
Posts: 1,619
Threads: 147
Joined: May 2006
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
Posts: 1,619
Threads: 147
Joined: May 2006
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.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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!
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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.
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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.
Posts: 528
Threads: 40
Joined: Dec 2008
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;
}
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
Thanks, David. Good work! I'm not conversant in C (or RPL, for that matter), but I respect people who are!
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
Posts: 1,619
Threads: 147
Joined: May 2006
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
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
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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.
Posts: 528
Threads: 40
Joined: Dec 2008
Thanks for the detailed description of your solution Egan. I particularly appreciate the explanation of the code.
Dave
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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.
Posts: 528
Threads: 40
Joined: Dec 2008
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.
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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.
Posts: 1,619
Threads: 147
Joined: May 2006
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
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";
|