nekedome / project-euler

solutions/problem15.py

"""
Project Euler Problem 15: Lattice Paths
=======================================

.. module:: solutions.problem15
   :synopsis: My solution to problem #15.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem15.py>`_.

Problem Statement
#################

Starting in the top left corner of a :math:`2 \\times 2` grid, and only being able to move to the right and down, there

This line is too long as per the coding-style (119/100).

are exactly :math:`6` routes to the bottom right corner.

.. image:: ../images/p015.gif
   :align: center

How many such routes are there through a :math:`20 \\times 20` grid?

Solution Discussion
###################

Use a dynamic programming algorithm to count the number of paths through a search tree.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem15.py
   :language: python
   :lines: 35-
"""

from typing import Dict, List, Optional, Tuple


def search(length: int, moves: Optional[List[int]] = None, solutions: Optional[Dict[Tuple[int, int], int]] = None)\

This line is too long as per the coding-style (115/100).

        -> int:
    """ Recursive tree search, branching on possible choices (left or down)

    Dynamic programming (solutions) is used to cache previous, partial, answers avoiding re-computation.

This line is too long as per the coding-style (104/100).

    :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:

Unnecessary "else" after "return"

        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

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).