Project Euler #15 in Python

Question

I've wrote the code for Project Euler #15 and it runs amazingly fast. I know I can write it using binomials but I wanted to calculate by brute force as if I do not know Binomials. But I think it must be taking huge amount of memory so I want to know how I can reduce amount of memory used by program. I've tried to reduce elements in the Dictionary as much as possible but I cannot think of any other thing.

import time
st = time.clock()
results = {}
def routes(a, b):
 if a > b:
 a, b = b, a
 if a == 0:
 return 1
 if a == b:
 if str([a - 1, b]) in results:
 return 2 * results[str([a - 1, b])]
 else:
 part1 = routes(a - 1, b)
 results[str([a - 1, b])] = part1
 return 2 * part1
 if str([a - 1, b]) in results:
 part1 = results[str([a - 1, b])]
 else:
 part1 = routes(a - 1, b)
 results[str([a - 1, b])] = part1
 if str([a, b - 1]) in results:
 part2 = results[str([a, b - 1])]
 else:
 part2 = routes(a, b - 1)
 results[str([a, b - 1])] = part2
 return part1 + part2
number = int(input("Enter n : "))
#print((routes(20, 20)))
print((routes(number, number)))
#print((results))
print((len(results)))
print(("Time took : ", time.clock() - st))

Output 1:

Enter n : 20 
Answer = 137846528820 
Number of elements in hashtable/dictionary are 229 
Time took : 0.002663 seconds.

Output 2:

Enter n : 480 
Answer = 250892214537448775747234101104975594366453286042769782121222122282812207368859289614865150179674097028772541144903685677912632260432728444419421872981795600499773664936037617507243883516784270458848737326769427370361260166492752950426905484595009507753796738842521345046644373977709359600
Number of elements in hashtable/dictionary are 115919 
Time took : 0.483901 seconds.

• Joshua Dawson: Use dynamic programming, basically calculate the binomial coefficient using Pascal's Triangle, and delete irrelevant caches as you go. It's similar to your algorithm except it starts from the bottom (square 0,0) and goes up. Also, your code is getting wrapped up with two concepts, calculating the binomial coefficient and caching results. Look into this article on how to write a method to memoize a function to make your code more modular.
• Gaurish Gangwar: Thanks @Josh Dawson, the link you gave was very helpful.

Answer 1

1. The code converts a pair of numbers to a dictionary key by putting the numbers in a list and then turning the list into a string: str([a, b]). But that's not necessary: you can use the tuple (a, b) as a dictionary key without having to convert it to a string.

   (The reason that you can't use a list [a, b] as a dictionary key is that lists can be modified, which invalidates their use as keys. Tuples can't be modified, and so you can use them as keys.)

2. It would simplify the code if the function routes (i) started by looking up its parameters in the results dictionary to see if it already had an answer; and (ii) always stored its result in the dictionary. If you did both of these, then you could avoid a lot of the cases:

   results = {}
   def routes(a, b):
    "Number of routes from (a, b) to (0, 0) in a grid."
    if (a, b) in results:
    return results[a, b]
    elif a > b:
    r = routes(b, a)
    elif a == 0:
    r = 1
    else:
    r = routes(a - 1, b) + routes(a, b - 1)
    results[a, b] = r
    return r
   

3. This code does two things: it computes the number of routes, and it arranges to cache the results of the computation in a dictionary to avoid having to recompute it. The principle of separation of concerns suggests that we should try to split these two things into different bits of code. That would make them easier to understand, test, and reuse.

   In this case, Python already has built-in support for caching the results of a function: see functools.lru_cache. So all you need to implement is the route-counting part of the code, and let lru_cache do the caching:

   from functools import lru_cache
   @lru_cache(maxsize=None)
   def routes(a, b):
    "Number of routes from (a, b) to (0, 0) in a grid."
    if a > b:
    return routes(b, a)
    elif a == 0:
    return 1
    else:
    return routes(a - 1, b) + routes(a, b - 1)
   

Answer 2

This is a classic Dynamic Programming problem, which significantly reduces your memory consumption to O(n*m). This has been explained quite well in other answers and comments.

However, the problem also has a much simpler combinatorics solution. For a grid of n rows and m columns, the answer is (n+m)Cn. You can calculate this easily, in O(n) time and O(1) memory!