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 meetinthemiddle 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 sumtotal doesn’t exceed £2.
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 nontrivial 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 sumtotal 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 nontrivial subset
partial_solutions1 = partial_solutions(bounds1, target)
partial_solutions2 = partial_solutions(bounds2, target)
# Consider the crossproduct 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 sumtotal threshold
Return type: List
[int
]Returns: the list of totals given by combinations of coins not exceeding threshold
 bounds (

solutions.problem31.
solve
()¶ Compute the answer to Project Euler’s problem #31