2

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.

Improve this question
5
  • 3
    Generally, memoization only works for functions with no side effects. That is, the function must not make any changes to values outside of the function. But your function violates this rule; it modifies the global value route. Try writing your function without any globals. Commented Jul 24, 2014 at 11:53
  • Also, helper have incorrect signature - it should be helper(x,y) Commented Jul 24, 2014 at 11:53
  • @J0HN, helper should have the same number of arguments as search. search takes one argument, so helper should take one argument as well. It's a little confusing in this example since search's argument is a single tuple that contains two values, so it looks like it takes two arguments if you miss the extra parentheses. Commented Jul 24, 2014 at 11:54
  • Oh, right, I missed it, it's two elements tuple. Commented Jul 24, 2014 at 11:57
  • I suppose it is cheating to check the return values for smaller sizes and finding what sequence it is? The answer is in the order of 10^11, so any way will probably take time. Commented Jul 24, 2014 at 12:58

3 Answers 3

Reset to default
1

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)))
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I would suggest have search take x and y directly and also the if only check if e.g. x is 0 to save some compute
0

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()
Improve this answer

Comments

0

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.