Problem 15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

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

Solution 1:

Look at the picture! How many lines do pass through specific box with number inside. The result would be the sum of all boxes and 1 which did not pass through box but upper sides.

Here is the code.

n = 20
li = []
temp = []
for i in range(n):
    temp += [1]
li += [temp]

for j in range(n-1):
    temp = []
    for i in range(n, 0, -1):
        temp += [sum(li[j][:i])]
    temp.reverse()
    li += [temp]

tot = 0
for i in range(n):
    tot += sum(li[i])
print(tot + 1)   

The output is: 137846528820.
This run:~ 0.017461299896240234.