# Project Euler Problem 31 (Coin Sum)

I just finished Project Euler 31: Coin sums, which asks how many ways there are to make £2 using British coins (1p, 2p, 5p, 10p, 20p, 50p, £1, and £2).

When I compared my code and the problem review's algorithms, I found that my code was faster than theirs. Both of them use dynamic programming, but for some unknown reasons, my code meets the recursive limits.

## Project Euler Reference

def problem_31_dynamic_programming(money, coin_index):
count = 0
if coin_index <= 0:
return 1
m = money
if memoiz_list[m][coin_index] > 0:
return memoiz_list[m][coin_index]
while money >= 0:
count += problem_31_dynamic_programming(money, coin_index - 1)
money -= coin_list[coin_index]
memoiz_list[m][coin_index] = count
return count


## My solution

import time

def problem_31(money, coin_index): #My solution (cannot solve big number such as 10000)
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
if memoiz_list[money][coin_index] > 0:
return memoiz_list[money][coin_index]
if coin_list[coin_index] > money:
return problem_31(money, coin_index - 1)
memoiz_list[money][coin_index] = problem_31(money, coin_index-1)+ \
problem_31(money-coin_list[coin_index],coin_index)
return memoiz_list[money][coin_index]

start = time.time()
coin_list = [1,2,5,10,20,50,100,200]
memoiz_list = [[0,0,0,0,0,0,0,0] for i in range(201)]
print(problem_31_dynamic_programming(200,7)) #Replace problem_31_dynamic_programming() with problem_31
elapsed = time.time() - start
print("Result found in %f seconds"%(elapsed))


Depth analysis

def problem_31_a(money, coin_index, depth=1):
global glob_depth
glob_depth = max(glob_depth, depth)
count = 0
if coin_index <= 0:
return 1
m = money
if memoiz_list[m][coin_index] > 0:
return memoiz_list[m][coin_index]
while money >= 0:
count += problem_31_a(money, coin_index - 1, depth=depth+1)
money -= coin_list[coin_index]
memoiz_list[m][coin_index] = count
return count

def problem_31_b(money, coin_index, depth=1):
global glob_depth
glob_depth = max(glob_depth, depth)
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
if memoiz_list[money][coin_index] > 0:
return memoiz_list[money][coin_index]
if coin_list[coin_index] > money:
return problem_31_b(money, coin_index - 1, depth=depth+1)
memoiz_list[money][coin_index] = problem_31_b(money, coin_index-1, depth=depth+1)+ \
problem_31_b(money-coin_list[coin_index],coin_index, depth=depth+1)
return memoiz_list[money][coin_index]

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

for func in [problem_31_a, problem_31_b]:
glob_depth = 0
start = time.time()
memoiz_list = [[0,0,0,0,0,0,0,0] for i in range(201)]
print(func(200,7))
elapsed = time.time() - start
print("Result found in %f seconds - depth:%d" % (elapsed, glob_depth))


And indeed, we get:

73682
Result found in 0.003184 seconds - depth:8
73682
Result found in 0.000919 seconds - depth:107


Your code appears to be faster but also goes much deeper in the function calls. If you exceed the system limits, you could update sys.setrecursionlimit. However, it could be a good idea to try to fix your code.

You could write a solution that doesn't perform any recursive calls: instead of trying to solve your problems by solving smaller and smaller problems and saving the solution as you go, you could simply update all the problems from the smallest to the biggest you need.

For instance, you could write:

def problem_31_c(money, unused):
nb_ways =  +  * money
for c in coin_list:
for v in range(money + 1 - c):
nb_ways[v + c] += nb_ways[v]
return nb_ways[-1]


Actual code review

For both functions, it could be a good idea to make it obvious that we have the following pattern:

if value_from_memoiz_list:
return value_from_memoiz_list
compute_value
store_value_in_memoiz_list
return value


In problem_31 for instance, we can see that a situation leads to a result being computed and returned without being store in the memoized list. Also, that case could be handled with less duplicated logic:

count = problem_31_b(money, coin_index-1)
coin_value = coin_list[coin_index]
if coin_value <= money:
count += problem_31_b(money-coin_value,coin_index)


Finally, your strategy reusing computed value assumes that 0 is a non-existing result. You could use None for this. In your case it doesn't make a difference because no expensive computation leads to 0 but it makes the intent of your code clearer.

def problem_31_a(money, coin_index):
if coin_index <= 0:
return 1
money_rem = money
memo_value = memoiz_list[money][coin_index]
if memo_value is not None:
return memo_value
count = 0
while money_rem >= 0:
count += problem_31_a(money_rem, coin_index - 1)
money_rem -= coin_list[coin_index]
memoiz_list[money][coin_index] = count
return count

def problem_31_b(money, coin_index):
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
memo_value = memoiz_list[money][coin_index]
if memo_value is not None:
return memo_value
count = problem_31_b(money, coin_index-1)
coin_value = coin_list[coin_index]
if coin_value <= money:
count += problem_31_b(money-coin_value,coin_index)
memoiz_list[money][coin_index] = count
return count


Also, you could use a decorator to implement your memoization strategy.

Reusing a generic decorator from https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize , you could write:

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

class memoized(object):
'''Decorator. Caches a function's return value each time it is called.
If called later with the same arguments, the cached value is returned
(not reevaluated).
'''
def __init__(self, func):
self.func = func
self.memoiz_list = [[None]*len(coin_list) for i in range(201)]
def __call__(self, money, coin_index):
try:
memo_value = self.memoiz_list[money][coin_index]
if memo_value is not None:
return memo_value
except IndexError:
pass
ret = self.func(money, coin_index)
try:
self.memoiz_list[money][coin_index] = ret
except IndexError:
pass
return ret
def __repr__(self):
'''Return the function's docstring.'''
return self.func.__doc__
def __get__(self, obj, objtype):
'''Support instance methods.'''
return functools.partial(self.__call__, obj)

@memoized
def problem_31_a(money, coin_index):
if coin_index <= 0:
return 1
money_rem = money
count = 0
while money_rem >= 0:
count += problem_31_a(money_rem, coin_index - 1)
money_rem -= coin_list[coin_index]
return count

@memoized
def problem_31_b(money, coin_index):
if coin_index < 0:
return 0
if coin_index == 0 or money == 0:
return 1
count = problem_31_b(money, coin_index-1)
coin_value = coin_list[coin_index]
if coin_value <= money:
count += problem_31_b(money-coin_value,coin_index)
return count

• memoized = functools.lru_cache(maxsize=None) – Gareth Rees Feb 10 '18 at 16:27