|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 31: Coin Sums |
|
3
|
|
|
=================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem31 |
|
6
|
|
|
:synopsis: My solution to problem #31. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem31.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
In England the currency is made up of pound, :raw-html:`£`, and pence, p, and there are eight coins in general |
|
|
|
|
|
|
15
|
|
|
circulation: |
|
16
|
|
|
|
|
17
|
|
|
:math:`1p, 2p, 5p, 10p, 20p, 50p,` :raw-html:`£1` :math:`(100p)` and :raw-html:`£2` :math:`(200p)`. |
|
|
|
|
|
|
18
|
|
|
|
|
19
|
|
|
It is possible to make :raw-html:`£2` in the following way: |
|
20
|
|
|
|
|
21
|
|
|
:math:`1 \\times` :raw-html:`£1` :math:`+ 1 \\times 50p + 2 \\times 20p + 1 \\times 5p + 1 \\times 2p +` |
|
|
|
|
|
|
22
|
|
|
:math:`3 \\times 1p` |
|
23
|
|
|
|
|
24
|
|
|
How many different ways can :raw-html:`£2` be made using any number of coins? |
|
25
|
|
|
|
|
26
|
|
|
Solution Discussion |
|
27
|
|
|
################### |
|
28
|
|
|
|
|
29
|
|
|
This solution is inspired by a `meet-in-the-middle approach <https://en.wikipedia.org/wiki/Meet-in-the-middle_attack>`_. |
|
|
|
|
|
|
30
|
|
|
|
|
31
|
|
|
We will separate the denominations into three mutually exclusive subsets. Two subsets representing similarly sized |
|
|
|
|
|
|
32
|
|
|
subspaces and a final subset consisting of the one pence coin. More specifically: |
|
33
|
|
|
|
|
34
|
|
|
* :math:`\\lbrace 2p, 20p, 50p \\rbrace` |
|
35
|
|
|
* :math:`\\lbrace 5p, 10p, 100p, 200p \\rbrace` |
|
36
|
|
|
* :math:`\\lbrace 1p \\rbrace` |
|
37
|
|
|
|
|
38
|
|
|
Consider the possible range of coins of a given denomination :math:`x` s.t. the sum-total doesn't exceed |
|
|
|
|
|
|
39
|
|
|
:raw-html:`£2`. |
|
40
|
|
|
|
|
41
|
|
|
.. math:: |
|
42
|
|
|
|
|
43
|
|
|
0 \\le \\# \\mbox{ coins of denomination } x \\le \\left \\lfloor \\frac{200}{x} \\right \\rfloor |
|
|
|
|
|
|
44
|
|
|
|
|
45
|
|
|
These bounds give the size of each search space associated with the denomination :math:`x`. |
|
46
|
|
|
|
|
47
|
|
|
The size of the search space associated with each subset is the size of the cross product of the respective |
|
|
|
|
|
|
48
|
|
|
denominations. That is: |
|
49
|
|
|
|
|
50
|
|
|
* :math:`|| \\lbrace 1p \\rbrace || = (200+1) = 201` |
|
51
|
|
|
* :math:`|| \\lbrace 2p, 20p, 50p \\rbrace || =` |
|
52
|
|
|
:math:`(100 + 1) \\times (10 + 1) \\times (4 + 1) = 101 \\times 11 \\times 5 = 5555` |
|
53
|
|
|
* :math:`|| \\lbrace 5p, 10p, 100p, 200p \\rbrace || =` |
|
54
|
|
|
:math:`(40 + 1) \\times (20 + 1) \\times (2 + 1) \\times (1 + 1) = 41 \\times 21 \\times 3 \\times 2 = 5166` |
|
|
|
|
|
|
55
|
|
|
|
|
56
|
|
|
.. note:: the one pence coin is considered separately for a very specific reason. As long as the total of all other |
|
|
|
|
|
|
57
|
|
|
denominations is no greater than two pounds then a solution is possible by adding the required number of one |
|
|
|
|
|
|
58
|
|
|
pence coins until two pounds is achieved. |
|
59
|
|
|
|
|
60
|
|
|
Now, the algorithm is simple. Find all combinations of coins from each of the two non-trivial subsets that do not |
|
|
|
|
|
|
61
|
|
|
exceed two pounds. Search through the cross product of these two spaces and every total combination not exceeding |
|
|
|
|
|
|
62
|
|
|
two pounds is a valid answer. The difference can simply be padded with one pence coins until two pounds is reached. |
|
|
|
|
|
|
63
|
|
|
|
|
64
|
|
|
Solution Implementation |
|
65
|
|
|
####################### |
|
66
|
|
|
|
|
67
|
|
|
.. literalinclude:: ../../solutions/problem31.py |
|
68
|
|
|
:language: python |
|
69
|
|
|
:lines: 72- |
|
70
|
|
|
""" |
|
71
|
|
|
|
|
72
|
|
|
from itertools import product |
|
73
|
|
|
from typing import Dict, List |
|
74
|
|
|
|
|
75
|
|
|
|
|
76
|
|
|
def partial_solutions(bounds: Dict[int, int], threshold: int) -> List[int]: |
|
77
|
|
|
""" Produce the set of combinations of coins that doesn't exceed `threshold` pence |
|
78
|
|
|
|
|
79
|
|
|
The coins that may be used are specified in `bounds` which is a dictionary mapping denominations to the upper bound |
|
|
|
|
|
|
80
|
|
|
in the search space for that denomination. |
|
81
|
|
|
|
|
82
|
|
|
:param bounds: dictionary mapping denominations to search space upper bounds |
|
83
|
|
|
:param threshold: the sum-total threshold |
|
84
|
|
|
:return: the list of totals given by combinations of coins not exceeding `threshold` |
|
85
|
|
|
""" |
|
86
|
|
|
|
|
87
|
|
|
rv = [] |
|
|
|
|
|
|
88
|
|
|
for x in product(*(range(bounds[y] + 1) for y in bounds.keys())): |
|
|
|
|
|
|
89
|
|
|
subtotal = sum([ai * bi for ai, bi in zip(x, bounds.keys())]) |
|
90
|
|
|
if subtotal <= threshold: |
|
91
|
|
|
rv.append(subtotal) |
|
92
|
|
|
rv.sort() |
|
93
|
|
|
return rv |
|
94
|
|
|
|
|
95
|
|
|
|
|
96
|
|
|
def solve(): |
|
97
|
|
|
""" Compute the answer to Project Euler's problem #31 """ |
|
98
|
|
|
|
|
99
|
|
|
target = 200 # in pence |
|
100
|
|
|
subset1, subset2 = [2, 20, 50], [5, 10, 100, 200] # 1p is not included |
|
101
|
|
|
bounds1 = {pence: target // pence for pence in subset1} |
|
102
|
|
|
bounds2 = {pence: target // pence for pence in subset2} |
|
103
|
|
|
|
|
104
|
|
|
# Independently compute partial solutions based on each non-trivial subset |
|
105
|
|
|
partial_solutions1 = partial_solutions(bounds1, target) |
|
106
|
|
|
partial_solutions2 = partial_solutions(bounds2, target) |
|
107
|
|
|
|
|
108
|
|
|
# Consider the cross-product of partial solutions and identify any combination not exceeding two points |
|
|
|
|
|
|
109
|
|
|
answer = 0 |
|
110
|
|
|
for ps1 in partial_solutions1: |
|
111
|
|
|
for ps2 in partial_solutions2: |
|
112
|
|
|
if ps1 + ps2 <= target: |
|
113
|
|
|
answer += 1 # 1p coins can increase this to target as required |
|
114
|
|
|
else: |
|
115
|
|
|
break # ps1 + ps2 for all further ps2 will now exceed target due to sorting |
|
116
|
|
|
return answer |
|
117
|
|
|
|
|
118
|
|
|
|
|
119
|
|
|
expected_answer = 73682 |
|
|
|
|
|
|
120
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.