Combining coins to form a sum - Project Euler, problem 31

I had some free time these past few days, so I got back to Project Euler: I like fooling around with the problems there, particularly because the process reminds me of what it felt like when I begun working with computers; the ecstasy of "pure" problem solving, without the nasty side-effects of dealing with clients :‑)

Hey, on occasion I am even known to pretend to be a scientist :‑)

The problem I've enjoyed most so far, is problem 31:

Hmm...In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is therefore possible to make £2 in the following way:

1x£1, 1x50p, 2x20p, 1x5p, 1x2p, 3x1p

How many different ways can £2 be made using any number of coins?

Being the trigger-happy engineer that I am, I quickly tried to brute-force:

#include <stdio.h> #include <signal.h> // We want to accumulate 200 cents (2 pounds) #define TARGET 200 int coins[] = {1, 2, 5, 10, 20, 50, 100, 200}; long long total = 0LL; int newCoin(int s) { if (s == TARGET) { total ++; // landed right on 200 cents, increase total return 1; // and report "break out of the loop" } else if (s>TARGET) { // we overflowed, go back and report "break out of the loop" return 1; } else { // recurse, adding each available coin in turn for(int idx=0; idx<sizeof(coins)/sizeof(coins[0]); idx++) { int earlyAbort = newCoin(s+coins[idx]); // if the callee reported non-zero, we break if (earlyAbort) return 0; } } return 0; } void pr(int i) { // SIGINT (Ctrl-C) triggered reports printf("\n%lld\n", total); } int main() { signal(SIGINT, pr); newCoin(0); // start the game printf("%lld\n", total); }

Sure, sure, I am not handling the signals properly, printf is not re-entrant - but who cares,
I just want to quickly see if this solves the problem or not; Ctrl-C
will print how high `total` is, so trying it out...

ttsiod@elrond:tmp$ g++ -O2 problem31.brute.cc ttsiod@elrond:tmp$ ./a.out ^C 32378168 ^C 51764088 ^C 81886592 ^C 168584448 ^C 225451092 ^Z [1]+ Stopped ./a.out ttsiod@elrond:tmp$ kill %1 [1]+ Killed ./a.outOoops. This thing grows rapidly (too rapidly)!

And it doesn't seem to finish. After 1 minute of running...

To make matters worse, the speed at which `total` goes up makes it clear
that I am being an idiot: the blind recursion will obviously measure 1p+2p as a different combination
to 2p+1p. Order is not supposed to count; the problem statement says "how many different ways",
and this is clearly violating it.

Target in cents | Using only 1p | Using <= 2p | Using <= 5p | ... |

1 | 1 | ... |

Only one way - so, fill up the cell of column "Using only 1p" with 1.

Moving on - what if I could use coins less than or equal to 2p?

Target in cents | Using only 1p | Using <= 2p | Using <= 5p | ... |

1 | 1 | 1 | ... |

So all the first line fills up with 1s:

Target in cents | only 1p | <= 2p | <= 5p | <= 10p | <= 20p | <= 50p | <= 100p | <= 200p |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

Target in cents | only 1p | <= 2p | <= 5p | <= 10p | <= 20p | <= 50p | <= 100p | <= 200p |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 |

When using coins less than or equal to 2p, however, we can also do it via a single 2p coin - so there are now 2 ways:

Target in cents | only 1p | <= 2p | <= 5p | <= 10p | <= 20p | <= 50p | <= 100p | <= 200p |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |

Target in cents | only 1p | <= 2p | <= 5p | <= 10p | <= 20p | <= 50p | <= 100p | <= 200p |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |

3 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |

4 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |

5 | 1 | 3 | 4 | 4 | 4 | 4 | 4 | 4 |

- 3 cents can be formed as (1p+1p+1p,1p+2p), so starting from column "<=2p", the number is 2
- 4 cents can be formed as (4x1p, 2x1p+1x2p, 2x2p), so starting from column "<=2p", the number is 3
- 5 cents can be formed as (5x1p, 3x1p+1x2p, 1x1p+2x2p, 1x5p), so starting from column "<=5p", the number is 4
- etc...

- We notice that when forming the values in a line, the first column is always 1. There is only one way to form any target N, if you just use 1p coins: Nx1p.
- We also notice that when filling up a cell, we check to see if the corresponding coin "fits" in. If it doesn't, we just copy the value of the cell on the left - i.e. the number of ways to form a target sum doesn't change, since we can't use this column's coin.
- If the coin *does* fit, however, we then form a number by adding two things: (a) the number of ways we can form the target WITHOUT using the coin (which is on the cell on our left) plus (b) the number of ways we can form the
`target-columnCoin`, i.e. the number of ways to form the remainder, if we subtract (i.e. use) the coin from our target.

- There is 1 way to form a target of 5 cents using only 1p coins (the cell on the left has value 1)
- If we use a coin of 2p, then the remainder is
`target-2p`=`5p-2p`=`3p`, which we can**lookup**above, on line 3, and see that there are 2 ways to reach it, using "<=2p".

OK, we can now write it down in Python...

#!/usr/bin/env python # the 8 coins correspond to 8 columns coins = [1, 2, 5, 10, 20, 50, 100, 200] TARGET=200 matrix = {} for y in xrange(0, TARGET+1): # There is only one way to form a target sum N # via 1-cent coins: use N 1-cents! matrix[y, 0] = 1 # equivalent to matrix[(y,0)]=1 for y in xrange(0, TARGET+1): print y, ":", 1, for x in xrange(1, len(coins)): matrix[y, x] = 0 # Is the target big enough to accomodate coins[x]? if y>=coins[x]: # If yes, then the number of ways to form # the target sum are obtained via: # # (a) the number of ways to form this target # using ONLY coins less than column x # i.e. matrix[y][x-1] matrix[y, x] += matrix[y, x-1] # plus # (b) the number of ways to form this target # when USING the coin of column x # which means for a remainder of y-coins[x] # i.e. matrix[y-coins[x]][x] matrix[y, x] += matrix[y-coins[x], x] else: # if the target is not big enough to allow # usage of the coin in column x, # then just copy the number of ways from the # column to the left (i.e. with smaller coins) matrix[y, x] = matrix[y, x-1] print matrix[y, x], print

ttsiod@elrond:tmp$ python code/problem31.py 0 : 1 1 1 1 1 1 1 1 1 : 1 1 1 1 1 1 1 1 2 : 1 2 2 2 2 2 2 2 3 : 1 2 2 2 2 2 2 2 4 : 1 3 3 3 3 3 3 3 5 : 1 3 4 4 4 4 4 4 6 : 1 4 5 5 5 5 5 5 7 : 1 4 6 6 6 6 6 6 8 : 1 5 7 7 7 7 7 7 9 : 1 5 8 8 8 8 8 8 10 : 1 6 10 11 11 11 11 11 11 : 1 6 11 12 12 12 12 12 ... 195 : 1 98 1980 14140 43450 62156 65934 65934 196 : 1 99 2000 14350 44275 63500 67425 67425 197 : 1 99 2020 14560 45100 64844 68916 68916 198 : 1 100 2040 14770 45925 66188 70407 70407 199 : 1 100 2060 14980 46750 67532 71898 71898 200 : 1 101 2081 15211 47696 69118 73681 73682

The above method, in case you've never seen it before, is called dynamic programming - and just as was done here, can be used to quickly solve problems that are impossible to brute force.

OK, project Euler... one more down, three hundred to go! :‑)

My CV About me Back to index | Last update on: Sun Apr 13 15:14:09 2014 (Valid HTML) |

comments powered by Disqus