Project Euler15 "Lattice Path"

problem

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. image Then, how many routes are there in the 20 × 20 square? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015

Answer policy 1

The number of combinations is also required, but I want to try another algorithm because it is a big deal. The number of distances from a square to the goal is equal to the sum of the number of distances from each of the two squares in the direction of travel adjacent to the square to the goal. → There is no choice but to come back! pe15.png

Code 1

def f(L,a,b):
  if not L[a][b]:
    if a == len(L)-1 or b == len(L)-1:
      L[a][b] = 1
    else:
      L[a][b] = f(L,a+1,b) + f(L,a,b+1)
  return L[a][b]

def main():
  #(x,y) = (2,2)
  (x,y) = (20,20)
  L = [[0 for i in range(0,y+1)] for j in range(i,x+1)]
  ans = f(L,0,0)
  #print ans

Answer policy 2

When I searched the web, I found a way to find the number of distances from the starting point, not the number of distances to the goal, with a for statement. I actually tried it, but the for statement was much faster. After a little consideration, this method seems to be more efficient as an algorithm. pe15_2.png

Since it's a big deal, I tried to find only half of it in consideration of symmetry. image

Code 2

def g(L,a,b):
  if a == 0:
    return 1
  elif a == b:
    return L[a-1][b]*2
  else:
    return L[a-1][b]+L[a][b-1]
  
def main2():
  seq = range(21)
  L = [[0 for i in seq] for j in seq]
  
  for a in seq:
    for b in seq[a:]:
      L[a][b] = g(L,a,b)
  #print L[20][20]

Recommended Posts

Project Euler15 "Lattice Path"
Project Euler # 15 "Lattice Path" in Python
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
[Project Euler] problem1
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?
Functional programming in Python Project Euler 1
Project Euler 10 "Sum of Prime Numbers"
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 4 Attempt to speed up
Project Euler 11 "Maximum product in grid"
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler 9 Retention of calculation results
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
I wrote Project Euler 1 in one liner.
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