puzzle contents
Contents
raw puzzle

Problem 31

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:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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

Solution

This problem is a typical case of dynamic programming. Let's follow the normal way of solving such a problem; we identify a small sub-problem and build a table for all possible values. When we begin with 1p, how many ways are there to change it with 1p coins, 2p coins and so on? 1p can be expressed by only one 1p coin:

Targetonly 1p≤ 2p≤ 5p≤ 10p≤ 20p≤ 50p≤ 100p≤ 200p
1p1

With a 2p coin and so on is it not possible to express the amount. However, we want to calculate the number of ways we can express the target value with, so we include the lower coins for each column and express the maximum number of possible ways in each cell:

Targetonly 1p≤ 2p≤ 5p≤ 10p≤ 20p≤ 50p≤ 100p≤ 200p
1p1 1111111

This table means that there is only one way to express 1p, no matter what coins are being used. When we go on, we can continue with two pence:

Targetonly 1p≤ 2p≤ 5p≤ 10p≤ 20p≤ 50p≤ 100p≤ 200p
1p11111111
2p12222222

With only 1p coins, 2p can be expressed with 1p+1p. 2p can be expressed with a 2p coin as well, which gives 2 possibilities, but with all additional coins the result remain the same. We continue this pattern for 3, 4 and 5 pence:

Targetonly 1p≤ 2p≤ 5p≤ 10p≤ 20p≤ 50p≤ 100p≤ 200p
1p11111111
2p12222222
3p12222222
4p13333333
5p13444444

Now that we have an intuition of the table creation process, we can draw some conclusions. The first conclusion is that the first column is always one, meaning that there is only one way to form a target \(n\) with the use of \(n\) times 1p coins.

The second conclusion is that we always walk from left to right. If the corresponding coin fits into the target amount we build the value of the cell by adding the number of ways we can form the target without using the coin (the cell to the left) plus the number of ways we can form \(\text{target}-\text{columnValue}\), i.e. the number of ways to form the remainder if we subtract the coin from the target. If the corresponding coin does not fit, we just copy over the value from the cell to the left.

As an example take the last line with target 5p. The first column is 1 as stated before and the second column is \(\text{target}-\text{columnValue}=5p-2p=3p\), which we already have calculated. That means we can simply lookup the value from the table, which is two here. This algorithm can now be implemented quite easily in JavaScript:

function solution(target) {
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];
  var table = new Array(target + 1);
  for (var i = 0; i <= target; i++) {
    table[i] = new Array(coins.length);
    table[i][0] = 1;
  }

  for (var i = 0; i <= target; i++) {
    for (var j = 1; j < coins.length; j++) {
      table[i][j] = table[i][j - 1];
      if (coins[j] <= i)
        table[i][j]+= table[i - coins[j]][j];
    }
  }
  return table[i-1][j-1];
}

This approach works totally fine and computes the results within miliseconds. But the solution isn't perfect yet. We can turn the bottom-up approach into a top-down approach and skip a table creation. All that is needed is a 1d array, and we create column after column in-place, since we only depend on smaller values that are calculated earlier. At the end the array will represent the last column of the table. So how do we get to the solution? For ease of use we define 0p to be 1, which makes it easier to lookup direct coin-changes without a hard-coded check and as arrays are zero-indexed anyway this makes the algorithm even smoother. After that we start with a 1p coin. As before, we can express any amount exactly one time with 1p coins:

Targetonly 1p
0p1
1p1
2p1
3p1
4p1
5p1

When we go ahead and focus on a 2p coin, we can't make changes for any value less than 2p. But for any other target value, we can create the difference of the target value and the coin value 2p. That means we take away 2p and lookup the rest in the table, which is lower than 2p and is already known. After we go through all possible target values this way, we get:

Target≤ 2p
0p1
1p1
2p2
3p2
4p3
5p3

At the end we only have a 5p coin. Using it, we can skip all values below 5p again. But 5p itself can be expressed by one more 5p coin, which results in the final table:

Target≤ 5p
0p1
1p1
2p2
3p2
4p3
5p4

So what we did here is, we ran over all coins. For each coin value, we started with the current value and went to the target value. Each entry of the array is then the previous value plus the number of ways the amount can be expressed, when the coin value is already excluded. When implemented, this results in the following pretty piece of code:

function solution(target) {
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];
  var table = new Uint32Array(target + 1);
  table[0] = 1;
  for (var i = 0; i < coins.length; i++) {
    for (var j = coins[i]; j <= target; j++) {
      table[j]+= table[j - coins[i]];
    }
  }
  return table[target];
}

It's fun to see that two derivations result in a pretty similar implementation. Only the loops are swapped and matrix preparation is a bit different.