# 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

def solve():
""" Compute the answer to Project Euler's problem #15 """
target = 20


solutions.problem15.search(length, moves=None, solutions=None)
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 int the number of search paths through a $$length \times length$$ grid
solutions.problem15.solve()