Project Euler # 15 "Lattice Path" in Python

Problem 15 "Lattice Path"

If you start from the upper left of the 2 × 2 square, there are 6 routes that go to the lower right without turning back.

p_15.gif

Then, how many routes are there in the 20 × 20 square?

Python


# n = 2
n = 20

route_nums = {}

seq = range(1, n+2)

def compute_route_num(i, j):
  if(i == 1 or j == 1):
    return 1
  else:
    return route_nums[(i-1, j)] + route_nums[(i, j-1)]

for i in seq:
  for j in seq:
    route = compute_route_num(i, j)
    route_nums[(i, j)] = route

result = route_nums[(n+1, n+1)]
result

print result
print result == 137846528820

result


137846528820
True

Recommended Posts

Project Euler # 15 "Lattice Path" in Python
Project Euler15 "Lattice Path"
Functional programming in Python Project Euler 1
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Functional programming in Python Project Euler 2
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Project Euler # 8 "Maximum Product in Number String" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 12 "High Divisibility Triangular Number" in Python
Naturally sort Path in Python
Project Euler 37
Project Euler 47
Project Euler 31
File / folder path manipulation in Python
Project Euler 4
Project Euler 38
Project Euler 26
Project Euler 8
Project Euler 22
Project Euler 19
Project Euler 50
Get the desktop path in Python
Calculate free-space path loss in Python
Project Euler 33
Get the script path in Python
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Create Python project documentation in Sphinx
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Get the desktop path in Python
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
Do a non-recursive Euler Tour in Python
Quadtree in Python --2