Python Implementation of Problem 31

View source code here on GitHub!

Problem Solution

Project Euler Problem 31

This took a while to get in a form that I was happy with. I wanted something more flexible than "let's take 8 for loops", so I did my best to make this as modular as I could think to do.

Problem:

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×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many different ways can £2 be made using any number of coins?

python.src.p0031.calculate(counts: Iterable[int], units: Iterable[int]) → int
python.src.p0031.coin_combinations(amount: int, units: Sequence[int], counts: MutableSequence[int]) → int
python.src.p0031.main() → int
 1"""
 2Project Euler Problem 31
 3
 4This took a while to get in a form that I was happy with. I wanted something
 5more flexible than "let's take 8 for loops", so I did my best to make this as
 6modular as I could think to do.
 7
 8Problem:
 9
10In England the currency is made up of pound, £, and pence, p, and there are
11eight coins in general circulation:
12
131p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
14It is possible to make £2 in the following way:
15
161×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
17How many different ways can £2 be made using any number of coins?
18"""
19from typing import Iterable, MutableSequence, Sequence
20
21
22def calculate(counts: Iterable[int], units: Iterable[int]) -> int:
23    return sum(a * b for a, b in zip(counts, units))
24
25
26def coin_combinations(amount: int, units: Sequence[int], counts: MutableSequence[int]) -> int:
27    answer = total = 0
28    while total <= amount:
29        total = calculate(counts, units)
30        if total == amount:
31            # print(
32            #     ",  ".join(
33            #         "{:03}p * {{:03}}".format(unit) for unit in units
34            #     ).format(*counts)
35            # )
36            answer += 1
37        counts[-1] += 1
38        key = len(counts)
39        while total > amount:
40            key -= 1
41            counts[key] = 0
42            counts[key - 1] += 1
43            total = calculate(counts, units)
44            if key == 1:
45                break
46    return answer
47
48
49def main() -> int:
50    units = (200, 100, 50, 20, 10, 5, 2, 1)
51    counts = [0 for _ in units]
52    return coin_combinations(200, units, counts)

Tags: partition, combinatorics