Project Euler Problem 15 Solved

Lattice paths

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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#!/usr/bin/python
# -*- coding: utf-8 -*-

if __name__ == '__main__':
    (steps, a, b) = (20, 1, 1)

    i = steps * 2
    while i > steps:
        a *= i
        i -= 1
    while steps > 1:
        b *= steps
        steps -= 1

    print a / b

I’m the 86747th person to have solved this problem.