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


solutions.problem31.partial_solutions(bounds, threshold)
Parameters: bounds (Dict[int, int]) – dictionary mapping denominations to search space upper bounds threshold (int) – the sum-total threshold List[int] the list of totals given by combinations of coins not exceeding threshold
solutions.problem31.solve()