Project Euler Problem 31: Coin Sums

The source code for this problem can be found here.

Problem Statement

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 \times\) £1 \(+ 1 \times 50p + 2 \times 20p + 1 \times 5p + 1 \times 2p +\) \(3 \times 1p\)

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

Solution Discussion

This solution is inspired by a meet-in-the-middle approach.

We will separate the denominations into three mutually exclusive subsets. Two subsets representing similarly sized subspaces and a final subset consisting of the one pence coin. More specifically:

  • \(\lbrace 2p, 20p, 50p \rbrace\)
  • \(\lbrace 5p, 10p, 100p, 200p \rbrace\)
  • \(\lbrace 1p \rbrace\)

Consider the possible range of coins of a given denomination \(x\) s.t. the sum-total doesn’t exceed £2.

\[0 \le \# \mbox{ coins of denomination } x \le \left \lfloor \frac{200}{x} \right \rfloor\]

These bounds give the size of each search space associated with the denomination \(x\).

The size of the search space associated with each subset is the size of the cross product of the respective denominations. That is:

  • \(|| \lbrace 1p \rbrace || = (200+1) = 201\)
  • \(|| \lbrace 2p, 20p, 50p \rbrace || =\) \((100 + 1) \times (10 + 1) \times (4 + 1) = 101 \times 11 \times 5 = 5555\)
  • \(|| \lbrace 5p, 10p, 100p, 200p \rbrace || =\) \((40 + 1) \times (20 + 1) \times (2 + 1) \times (1 + 1) = 41 \times 21 \times 3 \times 2 = 5166\)

Note

the one pence coin is considered separately for a very specific reason. As long as the total of all other denominations is no greater than two pounds then a solution is possible by adding the required number of one pence coins until two pounds is achieved.

Now, the algorithm is simple. Find all combinations of coins from each of the two non-trivial subsets that do not exceed two pounds. Search through the cross product of these two spaces and every total combination not exceeding two pounds is a valid answer. The difference can simply be padded with one pence coins until two pounds is reached.

Solution Implementation

from itertools import product
from typing import Dict, List


def partial_solutions(bounds: Dict[int, int], threshold: int) -> List[int]:
    """ Produce the set of combinations of coins that doesn't exceed `threshold` pence

    The coins that may be used are specified in `bounds` which is a dictionary mapping denominations to the upper bound
    in the search space for that denomination.

    :param bounds: dictionary mapping denominations to search space upper bounds
    :param threshold: the sum-total threshold
    :return: the list of totals given by combinations of coins not exceeding `threshold`
    """

    rv = []
    for x in product(*(range(bounds[y] + 1) for y in bounds.keys())):
        subtotal = sum([ai * bi for ai, bi in zip(x, bounds.keys())])
        if subtotal <= threshold:
            rv.append(subtotal)
    rv.sort()
    return rv


def solve():
    """ Compute the answer to Project Euler's problem #31 """

    target = 200  # in pence
    subset1, subset2 = [2, 20, 50], [5, 10, 100, 200]  # 1p is not included
    bounds1 = {pence: target // pence for pence in subset1}
    bounds2 = {pence: target // pence for pence in subset2}

    # Independently compute partial solutions based on each non-trivial subset
    partial_solutions1 = partial_solutions(bounds1, target)
    partial_solutions2 = partial_solutions(bounds2, target)

    # Consider the cross-product of partial solutions and identify any combination not exceeding two points
    answer = 0
    for ps1 in partial_solutions1:
        for ps2 in partial_solutions2:
            if ps1 + ps2 <= target:
                answer += 1  # 1p coins can increase this to target as required
            else:
                break  # ps1 + ps2 for all further ps2 will now exceed target due to sorting
    return answer


expected_answer = 73682
solutions.problem31.partial_solutions(bounds, threshold)

Produce the set of combinations of coins that doesn’t exceed threshold pence

The coins that may be used are specified in bounds which is a dictionary mapping denominations to the upper bound in the search space for that denomination.

Parameters:
  • bounds (Dict[int, int]) – dictionary mapping denominations to search space upper bounds
  • threshold (int) – the sum-total threshold
Return type:

List[int]

Returns:

the list of totals given by combinations of coins not exceeding threshold

solutions.problem31.solve()

Compute the answer to Project Euler’s problem #31