Project Euler 31: Investigating combinations of English currency denominations

Problem 31 of Project Euler honestly baffled me for a while. That lasted until I realised that there is a simple brute force solution. But enough blabbering, the problem reads

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 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?

As mentioned before I have found a brute force solution which is a completely viable way to go, and I have found a dynamic programming solution. For the problem size of 200p the solutions are equally fast, but for larger problems the dynamic programming solution is significantly faster.

Brute Force Solution

The brute force solution consist of a set of nested for loops, where the initial value of the inner loop is dependent on the outer. This way it is possible to test if there is a way of making a solution with 2p and up which is smaller than or equal to £2, we can always top the solution up with 1ps until we reach £2. The C# code looks as

int target  = 200;
int ways = 0;

for (int a = target; a >= 0; a -= 200) {
    for (int b = a; b >= 0; b -= 100) {
        for (int c = b; c >= 0; c -= 50) {
            for (int d = c; d >= 0; d -= 20) {
                for (int e = d; e >= 0; e -= 10) {
                    for (int f = e; f >= 0; f -= 5) {
                        for (int g = f; g >= 0; g -= 2) {
                            ways++;
                        }
                    }
                }
            }
        }
    }
}

I don’t think it is a pretty solution, but it works, and the result of running the code is

£2 can be generated in 73682 number of ways
Solution took 0 ms

Running the code in less than a millisecond is hard to complain about though.

Dynamic Programming

In order to make a solution using Dynamic Programming we need to be able to divide the problem into independent sub-problems. There are dimension which this can be done in for this problem, both the number of different coins but also the value we need to split. The problem is also covered here but I will try to give an alternative description of the solution.

The question we want to answer repeatedly is. “If I have to give change to n pennies, if I give back one coin of x how many ways can I give back the rest n-x pennies using only coins of value x or smaller.” Posing that question means that we can make a smaller problem, which we need to solve. And in the end we get a very small and easy problem to solve “if I want to give change to 1p using 1p, how many ways can this be done?”

Instead of breaking down the problem with the question posed above, we will instead build up an array of solutions so we can look up the answer to the question once we are ready to ask it. And let me show you by hand with a smaller example. Lets figure out how many ways we can give change to 5p using 1p and 2p. This should be doable by hand.

What we will do is build up an array of solutions, at first the array is build up for giving change to 1-5p using only 1p coins.

We need to initialise the array with the question. If we want to give change to 0p using a 1p coin, in how many different ways can we do that. And to that we define the answer to be 1. Now we are ready to answer “If I have to change to 1p using 1p coins, how many ways can I do that?”, so lets give back 1p and look up the value for n-x = 0p, which is 1 add this to the already found 0 solutions for a total of 1 solution.

Now we are ready to answer the question, if I want to give change to 2p using 1p coins, and give back 1p, in how many ways can I give back the remaining 1p?. So subtracting 1 from the solution, we can look up the last part of the question, since that was already answered. This goes on for all 5p until we have a solution array that looks like

If you think about it, it is rather obvious that there is only one way to give change to any amount using only 1p coins.

So now we are ready to treat the case when we have 2p coins as well. Since we can’t give back a 2p coin when we need to change 1p, there is no need to pose that question. Lets instead see how many ways we can give back 2p. If we use the 2p coin, we need to further give change to 0p. So that is a solution. Lets add that to the already found number of solutions, so the solution array looks like

For 3p we can also give a 2p coin and then we need to give change to 1p, which in the table and gives us one solution. So the total number of solutions for giving change on 3p, is 1+1.

Giving change on 4p. To answer that give 2p change and answer the question how many ways can we give change to n-x = 4-2 = 2p using 1p and 2p coins. The answer to that is in the table and is 2. So there are two ways to give back 2p, plus the already found number of solutions. So the result table now looks like

Lets just make a sanity check on that. 4p we can make change in 4x1p, 2p + 2x1p or 2x2p. Yep, that seems correct. We can do the same with the 5 giving change to 5p so the solution table looks like

You get the idea of how to build the solution now? Lets make the algorithm for it. It is completely analogue to what I just showed you by hand just with more coins and a larger value we need to give change to.

In C# it can be implemented as

int target = 200;
int[] coinSizes = { 1, 2, 5, 10, 20, 50, 100, 200 };
int[] ways = new int[target+1];
ways[0] = 1;

for (int i = 0; i < coinSizes.Length; i++) {
    for (int j = coinSizes[i]; j <= target; j++) {
        ways[j] += ways[j - coinSizes[i]];
    }
}

pretty compact piece of code.  Which keeps building up the answer until we reach the final goal.

Running the code results in

£2 can be generated in 73682 number of ways
Solution took 0 ms

So for such a small problem there is no difference in running time.

Closing Remarks

There is no apparent difference in running time between the two algorithms.  But the number of iterations we need to go through differs significantly.  The brute force algorithm needs to go through all 73682 solutions. The dynamic programming has to make 200 calculations for each coin type, which totals 1600 calculations, a difference which becomes even more significant for larger change values.

As usual you can find the source code for download. And once again I encourage you to correct my mistakes, ask questions, find other solutions and so on. I am uncertain if this approach to solving the problem is well enough explained, so let me know.