Project Euler Problem 31 (Coin Sum)

Question

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))

Answer 1

Depth analysis

A bit of tweaking of your code leads to results about the maximum function call depth:

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 = [1] + [0] * 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

• Gareth Rees: memoized = functools.lru_cache(maxsize=None)