Project Euler #15 in Python

Question

I am newbie in Python. I'm stuck on doing Problem 15 in Project-Euler in reasonable time. The problem in memoize func. Without memoize all working good, but only for small grids. I've tried to use Memoization, but result of such code is "1" for All grids.

def memoize(f): #memoization
    memo = {}

    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper


@memoize
def search(node):
    global route
    if node[0] >= k and node[1] >= k:
        route += 1
        return route
    else:
        if node[0] < k + 1 and node[1] < k + 1:
            search((node[0] + 1, node[1]))
            search((node[0], node[1] + 1))
    return route


k = 2 #grid size
route = 0
print(search((0, 0)))

If commenting out code to disable memoize func:

#@memoize

all works, but to slow for big grids. What am i doing wrong? Help to debbug. Thx a lot!

Update1:

Thank for your help, I've found answer too:

def memoize(f):
    memo = {}

    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper


@memoize
def search(node):
    n = 0
    if node[0] == k and node[1] == k:
        return 1
    if node[0] < k+1 and node[1] < k+1:
        n += search((node[0] + 1, node[1]))
        n += search((node[0], node[1] + 1))
    return n

k = 20
print(search((0, 0)))

Problem was not in memoize func as i thought before. Problem was in 'search' function. Whithout globals it wroiking right i wished. Thx for comments, they was really usefull.

Answer 1

This problem can be solved in O(1) time by using the code below:

from math import factorial as f
n, m = map(int, input("Enter dimensions (separate by space)?").split())
print ("Routes through a", n, "x", m, "grid", f(n+m) // f(n) // f(m))

Here's a link for a proof of the equation: Project Euler Problem 15 Solution

Answer 2

Try this code. It works fast even with grids over 1000x1000! Not nessesarily square. But I didn't know about memoization yet...

import time
def e15():
    x=int(input("Enter X of grid: "))
    y=int(input("Enter Y of grid: "))
    start = time.time()
    lst=list(range(1,x+2))
    while lst[1]!=y+1:
        i=0
        for n in lst[1:]:
            i+=1
            lst[i]=n+lst[i-1]
    print(f"There are {lst[-1]} routes in {x}x{y} grid!")
    end = time.time() - start
    print("Runtime =", end)
e15()

Answer 3

Your memoization function is fine, at least for this problem. For the more general case, I'd use this:

def memoize(f):
    f.cache = {}                         # - one cache for each function
    def _f(*args, **kwargs):             # - works with arbitrary arguments
        if args not in f.cache:          #   as long as those are hashable
            f.cache[args] = f(*args, **kwargs)
        return f.cache[args]
    return _f

The actual problem -- as pointed out by Kevin in the comments -- is that memoization only works if the function does not work via side effects. While your function does return the result, you do not use this in the recursive calculation, but just rely on incrementing the global counter variable. When you get an earlier result via memoization, that counter is not increased any further, and you do not use the returned value, either.

Change your function to sum up the results of the recursive calls, then it will work.

You can also simplify your code somewhat. Particularly, the if check before the recursive call is not necessary, since you check for >= k anyway, but then you should check whether the x component or the y component is >= k, not both; once either has hit k, there's just one more route to the goal. Also, you could try to count down to 0 instead of up to k so the code does not need k anymore.

@memoize
def search(node):
    x, y = node
    if x <= 0 or y <= 0:
        return 1
    return search((x - 1, y)) + search((x, y - 1))

print(search((20, 20)))