Lattice paths algorithm does not finish running for 20 X 20 grid

I wrote the following code in python to solve problem 15 from Project Euler:

grid_size = 2
def get_paths(node):
        global paths

        if  node[0]  >= grid_size and node[1] >= grid_size:
                paths += 1
                return
        el开发者_C百科se:
                if node[0]<grid_size+1 and node[1] < grid_size+1:
                     get_paths((node[0]+1,node[1]))
                     get_paths((node[0],node[1]+1))
        return paths

def euler():
                print get_paths((0,0))

paths = 0
if __name__ == '__main__':
    euler()

Although it runs quite well for a 2 X 2 grid, it's been running for hours for a 20 X 20 grid. How can I optimise the code so that it can run on larger grids? Is it a kind of breadth first search problem? (It seems so to me.)

How can I measure the complexity of my solution in its current form?

---

You might want to look into the maths behind this problem. It's not necessary to actually iterate through all routes. (In fact, you'll never make the 1 minute mark like that).

I can post a hint but won't do so unless you ask for it, since I wouldn't want to spoil it for you.

Edit: Yes, the algorithm you're using will never really be optimal since there's no way to reduce the search space of your problem. This means that (as pg1989 stated) you'll have to look into alternative means of solving this problem.

As sverre said looking over here might give a nudge in the right direction: http://en.wikipedia.org/wiki/Binomial_coefficient

A direct solution may be found here (warning, big spoiler):

http://www.joaoff.com/2008/01/20/a-square-grid-path-problem/

---

Your algorithm is exponential, but only because you are re-evaluating get_paths with the same input many times. Adding Memoization to it will make it run in time. Also, you'll need to get rid of the global variable, and use return values instead. See also Dynamic Programming for a similar idea.

---

When solving problems on Project Euler, think about the math behind the problem for a long time before starting to code. This problem can be solved without any code whatsoever.

We're trying to count the number of ways through a grid. If you observe that the number of moves down and right do not change regardless of the path, then you only need to worry about the order in which you move down and right. So in the 2x2 case, the following combinations work:

DDRR 
DRDR
RDRD
RRDD
RDDR
DRRD

Notice that if we pick where we put the R moves, the placement of the D moves is determined. So really we only have to choose, from the 4 movement slots available, which get the R moves. Can you think of a mathematical operation that does this?

---

Probably not the way the project Euler guys wanted this problem to be solved but the answer is just the central binomial coefficient of a 20x20 grid.

Using the formula provided at the wiki article you get:

from math import factorial, pow
grid = 20
print int(factorial(2 * grid) / pow(factorial(grid), 2))

---

The key is not to make your algorithm run faster, as it will (potentially) run in exponential time, no matter how fast each step is.

It is probably better to find another way of computing the answer. Using your (expensive, but correct) solution as a comparison for small values is probably a sanity-preserver during the algorithm optimization effort.

---

This question provides some good insight into optimization. The code is in c# but the algorithms are applicable. Watch out for spoilers, though.

Project Euler #15

---

It can be solved by simple observation of the pattern for small grids, and determining a straightforward formula for larger grids. There are over 100 billion paths for a 20x20 grid and any iterative solution will take too long to compute.

---

Here's my solution:

memo = {(0, 1) : 1, (1, 0) : 1}
def get_pathways(x, y):

    if (x, y) in memo : return memo[(x, y)]

    pathways = 0
    if 0 in (x, y):
        pathways = 1
    else:
        pathways = get_pathways(x-1, y) + get_pathways(x, y-1)


    memo[(x, y)] = pathways
    return pathways

enjoy :)