Having some problems with Project Euler 31

Question

I've been working on solving Problem 31 from Project Euler. I'm almost finished, but my code is giving me what I know is the wrong answer. My dad showed the right answer, and mine is giving me something completely wrong.

coins = (1,2,5,10,20,50,100,200)
amount = 200
def ways(target, avc):    
    target = amount
    if avc <= 1:
          return 1
    res = 0
    while target >= 0:
        res = res + ways(target, avc-1)
        target = target - coins[avc]
    return res
print(ways(amount, 7))

This is the answer I get.

284130

The answer is supposed to 73682. EDIT: Thank you to everyone who answered my question. Thanks to all of you, I have figured it out!

Answer 1

Firstly, read Thomas Weller's answer. They give some excellent suggestions as to how to improve your coding and problem solving.

Secondly, your code works, and gives the correct answer after the following changes:

• As suggested, remove the target = amount line. You're resigning the argument of the function to global amount on each call (even on the recursive calls). Having removed that the answer comes up to 3275 - still not the right answer.
• The other thing you have to remember is that Python is 0-indexed. Therefore, your simplest case condition ought to read if avc <= 0: ... (not <=1).

Having made these two changes, your code gives the correct answer. Here is your code with these changes:

coins = (1,2,5,10,20,50,100,200)
amount = 200
def ways(target, avc):
    if avc <= 0:
        return 1
    res = 0
    while target >= 0:
        res = res + ways(target, avc-1)
        target = target - coins[avc]
    return res
print(ways(amount, 7))

Lastly, there are plenty of Project Euler answers out there. Having solved the yourself, it might be useful to have a look at what others did. For reference, I have not actually solved this Project Euler before, so I had to do that first. Here is my solution. I've added a pile of comments on top of it to explain what it does.

EDIT

I've just noticed something quite worrying: Your code (after fixes) works only if the first element of coins is 1. All the other elements can be shuffled:

# This still works ok
coins = (1,2,200,10,20,50,100,5)
# But this does not
coins = (2,1,5,10,20,50,100,200)

To ensure that this is always the case, you can just do the following:

coins = ... # <- Some not necessarily sorted tuple
coins = tuple(sorted(coins))

In principle there are a few other issues. Your solution breaks for non-unique values coins, and which don't include 1. The former you could fix with the use of sets, and the latter by modifying your if avc <= 0: case (check for the divisibility of the target by the remaining coin). Here is you piece of code with these changes implemented. I've also renamed the variables and the function to be a bit easier to read, and used coins as the argument, rather that avc pointer (which, by the way, I could not stop reading as avec):

unique = lambda x: sorted(set(x)) # Sorted unique list
def find_combinations(target, coins):
    ''' Find the number of ways coins can make up the target amount '''
    coins = unique(coins)
    if len(coins)==1: # Only one coin, therefore just check divisibility
        return 1 if not target%coins[0] else 0 
    combinations = 0
    while target >= 0:
        combinations += find_combinations(target, coins[:-1])
        target -= coins[-1]
    return combinations

coins = [2,1,5,10,20,50,100,200] # <- Now works
amount = 200

print(find_combinations(amount, coins))

Answer 2

I see several ways how you can improve the way you're working on problems:

• Copy the task description into your source code. This will make you more independent from Internet resources. That allows you to work offline. Even if the page is down or disappears completely, it will enable someone else understanding what problem you're trying to solve.

• Use an IDE that does proper syntax highlighting and gives you hints what might be wrong with your code. The IDE will tell you what @aronquemarr mentioned in the comments:

  

• There's also a thing called magic numbers. Many of the numbers in your code can be explained, but why do you start with an avc of 7?. Where does that number come from? 7 does not occur in the problem description.

• Use better naming, so you understand better what your code does. What does avc stand for? If you think it's available_coins, that's not correct. There are 8 different coins, not 7.

• If it still does not work, reduce the problem to a simpler one. Start with the most simple one you can think of, e.g. make only 1 type of coin available and set the amount to 2 cent. There should only be 1 solution.

• To make sure this simple result will never break, introduce an assertion or unit test. They will help you when you change the code to work with larger datasets. They will also change the way you write code. In your case you'll find that accessing the variable coins from an outer scope is probably not a good idea, because it will break your assertion when you switch to the next level. The change that is needed will make your methods more self-contained and robust.

• Then, increase the difficulty by having 2 different coins etc.

  Examples for the first assertions that I used on this problem:

  # Only 1 way of making 1 with only a 1 coin of value 1
  assert(find_combinations([1], 1) == 1)
  # Still only 1 way of making 1 with two coins of values 1 and 2
  assert(find_combinations([1,2], 1) == 1)
  # Two ways of making 2 with two coins of values 1 and 2
  assert(find_combinations([1,2], 2) == 2)
  

• As soon as the result does no longer match your expectation, use the debugger and step through your code. After every line, check the values in the debugger against the values that you think they should be.

  One time, the debugger will be your best friend. And you can never imagine how you did stuff without it. You just need to learn how to use it.