Project Euler Problem 015

Statement

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

p_015.gif

How many routes are there through a 20×20 grid?

Solution

Here we have to apply dynamic programming to solve it. That means solve the problem in smaller steps.
For this situation you have to imagine a matrix of points(each corner) as we are not able to backtrack,
all the point in the top row are only accessible through one route, the one that goes straight. The same
happens with the column on the left.
For the interior points, the number of routes is determined by the sum of the number of routes we have
until the corner above the point and the one on its left.

For a 2×2 grid we would build a matrix of 3×3(remember it's the corners we need) and initialize it this way:

1, 1, 1
1, 0, 0
1, 0, 0

and then we start processing rows from top to bottom:

1, 1, 1
1, 2, 3
1, 0, 0


1, 1, 1
1, 2, 3
1, 3, 6

Now we just have to check the bottom right cell for the content and we have the answer.

if __name__ == '__main__':
    #Building the matrix
    sqre = [[]]
    for i in range(21):
        sqre[0].append(1)
    for i in range(1,21):
        row = [1]
        for i in range(1,21):
            row.append(0)
        sqre.append(row)
    #Processing the routes
    for i in range(1,21):
        for j in range(1, 21):
            sqre[i][j] = sqre[i-1][j] + sqre[i][j-1]
    print("The result is:", sqre[20][20])

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License