Visual Problem Solving and Dynamic Programming in Python
A step-by-step solution to Project Euler Problem 31
I was given an interesting coding problem recently. The problem is Project Euler Problem 31:
In the United Kingdom the currency is made up of pound (£) and pence (p). 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?
I’ll go though the problem solving process I went through when approaching this problem. You can see my solution at the bottom of this page.
Start by considering a simple case
With problems it’s good to start with simpler cases and build up from there. For example how many ways can you can 2p from the available coins?
The answer is 2 ways: 2 x 1p, 1 x 2p
But how could we arrive at this result systematically? A clear way to solve this is to consider each coin in turn and see if they can be subtracted from the target amount, i.e. consider taking away 1p from 2p, then separately consider taking away 2p from 2p.
Visualization helps build our intuition
Visualizations are usually a good tool. In this case we can use a tree to visualize the 2p solution:
Let me explain this visualization:
- Each node (the ovals) represents the current target that we want to make from the coins on the edges below it
- The root node (the top oval) shows the target value we want to make from change
- The number next to each edge (the arrows) represents the coin used to go from one target to the next
- Each branch of the tree terminates when the current target is 0
- Each way of reaching the root target value can be gotten by going back up the tree from each leaf node (nodes with 0) to the top and making a note of the coins on the edges
Visualization helps for more complex cases
The same process to produce the 2p tree can then be used to produce a 3p tree:
However we notice an issue that this tree also counts all permutations of coins to reach 3p: 3 x 1p, 1 x 1p + 1 x 2p, 1 x 2p + 1 x 1p; even though the correct answer is two ways: 3 x 1p, 1 x 1p + 1 x 2p, since 1 x 1p + 1 x 2p and 1 x 2p + 1 x 1p are equivalent.
We could just keep the tree and then remove any permutations, however this would be inefficient. Instead we should think, is there a way of modifying the tree to naturally remove permutations?
The visualization must ignore permutations
It turns out there is a way to naturally not include permutations.
Looking at the 3p tree, let’s go up from each leaf node to the root and noting the edges as we go. We get: (1p, 1p, 1p), (1p, 2p), and (2p, 1p).
By sorting each sequence we would see that there are only two unique ways to total 3p. After sorting we have: (1p, 1p, 1p), (1p, 2p), and (1p, 2p). The unique elements of this list are simply (1p, 1p, 1p), (1p, 2p), and the length of this list is 2, which equals the number of ways we can make change for 3p.
So how could we enforce that the sequence of edges for each leaf node in the tree will be in order?
When we produce the tree (from top to bottom) we should only allow an edge if it is less than or equal to the edge above it. This would remove the edge (2)→(1) in the 3p tree, resulting in 2 leaf nodes.
The resultant trees are shown below.
It’s useful if trees are well defined by a function
Now is there any way we can use these trees to efficiently calculate the ways of making change?
A useful thing to see is that this question has a purely functional answer i.e. we can solve this if we can find a well defined function f such that f(target) = (number ways of making change).
Since a function returns the same answer for the same inputs, we need to see if all (sub)trees with a root node x have the same number of leaf nodes n.
We reach an issue when we check 2p (sub)trees, shown in the boxes below.
We see there are two types of 2p (sub)tree: ones with 1 leaf node, and ones with 2 leaf nodes. The first set has an edge with 1 pointing to its root node, whereas the second set has 2 pointing to its root node (or no edge pointing to the root node). This means the 1-leaf trees correspond to making 2p from 1p whereas the 2-leaf trees correspond to making 2p from 1p or 2p.
What does this mean for our function f?
This means for our function to only depend on its inputs we also need a second input argument for the maximum allowed coin y i.e. f(x, y) = n
Rewriting out the trees with this new way of labeling nodes we get¹:
We can now check again that all (sub)trees with a root node x and max coin y have the same number of leaf nodes n. This time the check passes.
Recursion makes the problem more manageable
Now that f(x, y) is well defined we should consider if we can use one of the common tools in functional programming: recursion. For recursion to work, there needs to be examples of smaller solutions inside larger solutions.
One example in the above trees is f(4, 200) = f(3, 1) + f(2, 2). In words this says “the number of ways of making change for 4p using at most £2 coins is equal to the sum of: the number of ways of making change for 3p using at most 1p coins, and the number of ways of making change for 2p using at most 2p coins”.
More importantly there needs to be a systematic way to relate smaller solutions to larger solutions. We can find this by remembering how the tree is generated in the first place: at each node we make a branch for each possible coin that is less than or equal to the max allowed coin. Therefore f(x, y) is the sum of f(x-b, b) where b is a coin ≤ y.
For recursion we also need a base case, otherwise we will just end up in a loop of defining f(x, y) in terms of another f(x’, y’). The simplest base case is that f(0, y) = 1 for any y.
We can now write a solution using recursion:
coins = (1, 2, 5, 10, 20, 50, 1_00, 2_00)def n_ways(target, max_coin):
# returns number of ways of producing change to reach target,
# using change up to and including the max_coin
# raises error for negative targets
if target == 0:
return 1
if target > 0:
# don't count cases that would lead to a negative target
return sum(
n_ways(target - coin, coin)
for coin in coins
if coin <= max_coin
if target - coin >= 0
)
raise ValueError# 73682
print(n_ways(2_00, 2_00))
If we run this code it works well and gives the correct answer of 73,682.
Adding caching speeds up the code
Note that sometimes we will need to evaluate f(x, y) when we have already previously calculated f(x, y) e.g. f(1, 1) gets calculated twice when we calculate f(4, 200). These cases will actually occur more and more often as we increase x, therefore we should try and store previous values of the function so we can just recall the answer rather than recalculate it.
In Python this can be done in just two lines with the lru_cache. This turns any function into a cached function: a function that stores previously computed values and retrieves the stored value if the function is given the same arguments.
from functools import lru_cachecoins = (1, 2, 5, 10, 20, 50, 1_00, 2_00)@lru_cache(maxsize=None)
def n_ways(target, max_coin):
# returns number of ways of producing change to reach target,
# using change up to and including the max_coin
# raises error for negative targets
if target == 0:
return 1
if target > 0:
# don't count cases that would lead to a negative target
return sum(n_ways(target - coin, coin)
for coin in coins
if coin <= max_coin
if target - coin >= 0)
raise ValueError# 73682
print(n_ways(2_00, 2_00))
# CacheInfo(hits=414, misses=482, maxsize=None, currsize=482)
print(n_ways.cache_info())
This doubles the speed of computing f(200, 200). Not bad for two additional lines. We can also see by inspecting the cache_info that we actually stored 482 values for f in our cache² and that by using the cache we didn’t need to recalculate f 414 times.
Conclusion
This is the final form of our code³. It if flexible enough to be extended to a larger number of coins and higher totals. For example if we add £5 and £10 notes then the code tells us there are 327,631,322 ways to make £10.
The combination of recursion and caching in this solution means this is an example of dynamic programming, which you can read more about here.
Footnotes
[1] By looking at the trees we can see cases of f(x, y) where y > x. These cases will have the same answer as f(x, y*) where y* is the largest coin smaller than y e.g. f(2, 200) = f(2,2) and f(1, 2) = f(1,1). This is because adding coins higher value than the target can’t change how many ways you can make change. Taking this into account could make our code more efficient at the expense of added complexity. However in practice these very rarely occur, and even if f(x, y) is not cached, all nodes below it will have been cached if f(x, y*) is in the cache.
[2] I found other solutions online helpful when thinking how I would solve this problem. However these solutions require calculating f(x, y) for all values of x and y less than or equal to 200. This means f needs to be calculated 200 * 8 = 1600 times. As we’ve seen in comparison the method above only calculates f 482 times, meaning it reduces computation by a factor of 4.
[3] An interesting alternative solution is found if you plug the first 10 values of the sequence into OEIS which gives sequence A057537 and the corresponding generating function for the “number of ways of making change for n Euro-cents using the Euro currency”.
