Project Euler31: Understanding Program Solution

Question

I am trying to understand a solution to project euler #31 I found in the forums.

The problem is we are given coins with the following values:

coins=[1,2,5,10,20,50,100,200]

We are tasked with generating all the possible ways of reaching 200. For instance, 10*10+100=200 would be one possible way.

1. Question 2: How does the below code work! It looks very elegant, simple and straightforward compared to my approach, and runs way faster.

As I was browsing the forums, I found this solution:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

The first line is just the list of the coin values. The second line is creating an array with a 1 followed by 200 0's. But the next four lines got me confused. I think it is incrementing the number of possible ways in the array, so case_num[200] will give the last entry in the list, but I have no idea how it works.

Answer 1

This is a very nice solution as you said. The code builds upon itself through each iteration of 1-200 with each coin denomination.

The case_num array initially consists of [1, 0, 0, 0, 0, 0...0, 0, 0]

What these numbers (aside from the initial 1) mean are how many ways you can build up to the given total (represented by the index of the number) using the coins in p_list you have iterated through with so far.

The first coin in p_list is 1. So if 1 can fit inside the index then you take the value in the previous index and add it to your current index. This works because if there are 5 known ways to get to 25 and you have just found coins of size 1 then there will also be 5 ways to get to 26. [Each of the previous 5 ways to get to 25] + one 1 coin.

So after iterating through with 1's you will end up with [1, 1, 1, 1, 1...1, 1]

Now you move up in coins. This time you are using a coin of 2. Lets walk through the process 1 more time. If 2 is less then the index then you add the number of ways to get to the previous index to your current index.

For example 2 doesn't fit inside index 1 but does fit within index 2. So you just created a new way to get to 2 from 0 so you take all of the ways you could get to 0 and add them to your current index. On index 27, 2 fits within the index so you take the number of ways you could get to 25 and add them to 27 because now you have (all of those ways to get to 25 + one 2 coin) + (all of the ways you had to get to 27 before you knew you had coins of size 2).

So after iterating through with 2's you will end up with [1, 1, 2, 2, 3, 3, 4, 4...]

If you are still having trouble it may be worth it to try and walk through the entire program (maybe at a reduced total like 50 instead of 200).