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.

../_images/p015.gif

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

solutions.problem15.solve()

Compute the answer to Project Euler’s problem #15