Project Euler Problem 15: Lattice Paths¶
The source code for this problem can be found here.
Problem Statement¶
Starting in the top left corner of a \(2 \times 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 \times 20\) grid?
Solution Discussion¶
Use a dynamic programming algorithm to count the number of paths through a search tree.
Solution Implementation¶
from typing import Dict, List, Optional, Tuple
def search(length: int, moves: Optional[List[int]] = None, solutions: Optional[Dict[Tuple[int, int], int]] = None)\
-> int:
""" Recursive tree search, branching on possible choices (left or down)
Dynamic programming (solutions) is used to cache previous, partial, answers avoiding re-computation.
:param length: the length of each axis in the grid
:param moves: the moves made (down and right) at this point of the search
:param solutions: partial solutions cache for the avoidance of redundant computations
:return: the number of search paths through a :math:`length \\times length` grid
"""
if moves is None:
moves = [0, 0] # initialise moves to represent none have been made
assert moves[0] <= length, "you cannot move past the edge"
assert moves[1] <= length, "you cannot move past the edge"
if solutions is None:
solutions = {} # initialise solutions to the empty cache
if moves[0] == length:
return 1 # base case: no further branching possible
elif moves[1] == length:
return 1 # base case: no further branching possible
elif tuple(moves) in solutions:
return solutions[tuple(moves)] # returned cached answer
else:
# Branch down each possible path via recursion
answer0 = search(length, [moves[0] + 1, moves[1]], solutions)
solutions[(moves[0] + 1, moves[1])] = answer0
answer1 = search(length, [moves[0], moves[1] + 1], solutions)
solutions[(moves[0], moves[1] + 1)] = answer1
return answer0 + answer1
def solve():
""" Compute the answer to Project Euler's problem #15 """
target = 20
answer = search(target)
return answer
expected_answer = 137846528820
-
solutions.problem15.
search
(length, moves=None, solutions=None)¶ Recursive tree search, branching on possible choices (left or down)
Dynamic programming (solutions) is used to cache previous, partial, answers avoiding re-computation.
Parameters: - length (
int
) – the length of each axis in the grid - moves (
Optional
[List
[int
]]) – the moves made (down and right) at this point of the search - solutions (
Optional
[Dict
[Tuple
[int
,int
],int
]]) – partial solutions cache for the avoidance of redundant computations
Return type: int
Returns: the number of search paths through a \(length \times length\) grid
- length (
-
solutions.problem15.
solve
()¶ Compute the answer to Project Euler’s problem #15