Geek asks and answers

The trellis algorithm does not end for a 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
        else:
                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 works well for a 2 X 2 grid, it works for several hours for a 20 X 20. grid. How can I optimize the code so that it can work on large grids? Is this some kind of first search problem? (I think so.)

How to measure the complexity of my decision in its current form?

+3
source share
8 answers

, , get_path . Memoization, . , . . .

+3

, , . . ( , 1 ).

, , , .

Edit: , , , , . , ( pg1989) .

, , : http://en.wikipedia.org/wiki/Binomial_coefficient

(, ):

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

+5

Project Euler , . - .

. , , , . , 2x2 :

DDRR 
DRDR
RDRD
RRDD
RDDR
DRRD

, , R-, D-. , 4 , R . , ?

+3

, , () , , .

, . (, ) , , .

+1

, , Euler , - 20x20.

, wiki, :

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

. #, . .

Project Euler # 15

0

It can be solved by simply observing the pattern for small grids and defining a simple formula for large grids. There are over 100 billion paths for a 20x20 grid, and any iterative solution will take too long.

0
source

Here is 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 :)

0
source

More articles:


All Articles