Project Euler Solution 31: Coin sums

In Problem 31: Coin sums of the Project Euler series we have another nice one with permutations and partitioning.

In the United Kingdom the currency is made up of pound (£) and pence (p). 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?

There are lots of ways to assemble these coins. One naive way would be to take the maximum number of times that a given coin could be used to partition 200 pence if only that coin was used. These numbers would be (2, 4, 10, 40, 100, 200). Then we just take all possible combinations from 0 to that number. This would give us 5,768,123,130 ways to check for. We just check whether the total value of this combination of coins matches the 200 pence.

values = [200, 100, 50, 20, 10, 5, 2, 1]


def solution_brute_force() -> int:
    num_partitions = 0
    ranges = [range(200 // value + 1) for value in values]
    for counts in itertools.product(*ranges):
        total_value = sum(value * count for value, count in zip(values, counts))
        if total_value == 200:
            num_partitions += 1
    return num_partitions

This is not impossible, but I can only check about 1,000,000 combinations per second on my laptop. This means that it would take around two hours to go through all the combinations. That is clearly above the one-minute-rule.

We can do better than that. Once we pick a £1 coin, we know that there are only 100 pence to be partition. There is no point in trying out more than two 50p pieces. And if we take two 50p pieces, there are no pence left to partition and we can skip trying out the smaller coins.

This idea can be implemented recursively. We start and try all multiples of the biggest coin and then try to partition the remainder with the smaller coins in all possible ways. Depending on the remainder, there are few possibilities left. This quickly narrows the options.

def count_partitions(used: tuple, remainder: int) -> int:
    if len(used) == len(values) - 1:
        return 1

    current_value = values[len(used)]

    return sum(
        count_partitions(used + (usage,), remainder - current_value * usage)
        for usage in range(remainder // current_value + 1)
    )


def solution() -> int:
    return count_partitions((), 200)

This computes the correct solution in just 24 ms and therefore is the better solution.

If one takes a look at the solution document on the website, one can find an even faster and better scaling version. But since I didn't come up with it, I won't reproduce the document here.