nekedome / project-euler

solutions/problem18.py

"""
Project Euler Problem 18: Maximum Path Sum I
============================================

.. module:: solutions.problem18
   :synopsis: My solution to problem #18.

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

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

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top
to bottom is :math:`23`.

.. math::

    &&&& \\color{red}{3} &&& \\\\
    &&& \\color{red}{7} && 4 && \\\\
    && 2 && \\color{red}{4} && 6 & \\\\
    & 8 && 5 && \\color{red}{9} && 3

That is, :math:`3 + 7 + 4 + 9 = 23`.

Find the maximum total from top to bottom of the triangle below:

.. math::

    &&&&&&&&&&&&&&& 75 &&&&&&&&&&&&&& \\\\
    &&&&&&&&&&&&&& 95 && 64 &&&&&&&&&&&&& \\\\
    &&&&&&&&&&&&& 17 && 47 && 82 &&&&&&&&&&&& \\\\
    &&&&&&&&&&&& 18 && 35 && 87 && 10 &&&&&&&&&&& \\\\
    &&&&&&&&&&& 20 && 04 && 82 && 47 && 65 &&&&&&&&&& \\\\
    &&&&&&&&&& 19 && 01 && 23 && 75 && 03 && 34 &&&&&&&&& \\\\
    &&&&&&&&& 88 && 02 && 77 && 73 && 07 && 63 && 67 &&&&&&&& \\\\
    &&&&&&&& 99 && 65 && 04 && 28 && 06 && 16 && 70 && 92 &&&&&&& \\\\
    &&&&&&& 41 && 41 && 26 && 56 && 83 && 40 && 80 && 70 && 33 &&&&&& \\\\
    &&&&&& 41 && 48 && 72 && 33 && 47 && 32 && 37 && 16 && 94 && 29 &&&&& \\\\
    &&&&& 53 && 71 && 44 && 65 && 25 && 43 && 91 && 52 && 97 && 51 && 14 &&&& \\\\
    &&&& 70 && 11 && 33 && 28 && 77 && 73 && 17 && 78 && 39 && 68 && 17 && 57 &&& \\\\
    &&& 91 && 71 && 52 && 38 && 17 && 14 && 91 && 43 && 58 && 50 && 27 && 29 && 48 && \\\\
    && 63 && 66 && 04 && 68 && 89 && 53 && 67 && 30 && 73 && 16 && 69 && 87 && 40 && 31 & \\\\
    & 04 && 62 && 98 && 27 && 23 && 09 && 70 && 98 && 73 && 93 && 38 && 53 && 60 && 04 && 23

.. note:: as there are only :math:`16384` routes, it is possible to solve this problem by trying every route. However,
          :mod:`Problem 67 <solutions.problem67>`, is the same challenge with a triangle containing one-hundred rows; it
          cannot be solved by brute force, and requires a clever method! ;o)

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

This problem can be efficiently solved using a dynamically programming algorithm.

The algorithm iterates over the rows of the triangle, :math:`t_i`, and builds a list of partial solutions, :math:`p_j`,
that provide the maximum path sum ending at the :math:`(i,j)^{th}` position in the triangle. This is built one row at a
time.

Upon reaching the final row, :math:`p_j` contains the maximum path sum from the root of the triangle to
:math:`t_{n - 1,j}` for :math:`j \\in 0, \\dots, n - 1`. The maximum path sum overall is simply then the maximum value
in :math:`p`.

As noted in the problem description, a naive brute-force must consider each of the :math:`2^{15} = 32768` distinct
paths. While this would be relatively quick, the algorithm has exponential time complexity in the depth :math:`n` of the
triangle. That is, :math:`O(2^{n-1})` where :math:`n` is the number of rows in the triangle.

.. note:: the problem is wrong, there are actually :math:`2^{15}` paths not :math:`2^{14}` through this triangle.

This dynamic programming algorithm has time complexity :math:`O(1 + 2 + ... + n) = O(n^2)`.

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

.. literalinclude:: ../../solutions/problem18.py
   :language: python
   :lines: 79-
"""

from typing import List


def max_path_sum(triangle: List[List[int]]) -> int:
    """ Compute the maximum path sum through the triangle

    A path moves from the triangle root to a leaf node, with one entry from each row. As the path moves from one row to
    the next, it may connect to adjacent entries only.

    :param triangle: :math:`2`-dimensional list of integers (the triangle)
    :return: the maximum path sum through `triangle`
    """

    # Perform some simple validation on triangle
    assert isinstance(triangle, list), "triangle must be a triangular 2-dimensional list of integers"
    for i, row in enumerate(triangle):
        assert len(row) == i + 1, "row {} has length {}, it should have {} to be triangular".format(i, len(row), i + 1)
        for elt in row:
            assert isinstance(elt, int), "triangle entries must be integers"

    # Build up the answer one row at a time using a dynamic programming algorithm
    n = len(triangle)

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    partial_sum_to = [0] * n
    for i in range(n):
        # After each iteration i, part_sum_to[j] is the maximum path sum ending at triangle[i][j]
        temp_partial_sum = partial_sum_to.copy()  # keep an unmodified version of partial_sum from last iteration
        temp_partial_sum[0] = partial_sum_to[0] + triangle[i][0]  # only one possible path ends at triangle[i][0]
        for j in range(1, i):
            temp_partial_sum[j] = max(partial_sum_to[j - 1], partial_sum_to[j]) + triangle[i][j]
        temp_partial_sum[i] = partial_sum_to[i - 1] + triangle[i][i]  # only one possible path ends at triangle[i][i]
        partial_sum_to = temp_partial_sum

    return max(partial_sum_to)  # find the maximum path sum ending at one of the leaf nodes


def solve():
    """ Compute the answer to Project Euler's problem #18 """
    triangle = [
                                    [75],
                                  [95, 64],
                                [17, 47, 82],
                              [18, 35, 87, 10],
                            [20,  4, 82, 47, 65],
                          [19,  1, 23, 75,  3, 34],
                        [88,  2, 77, 73,  7, 63, 67],
                      [99, 65,  4, 28,  6, 16, 70, 92],
                    [41, 41, 26, 56, 83, 40, 80, 70, 33],
                  [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
                [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
              [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
            [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
          [63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
        [ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23]
    ]
    return max_path_sum(triangle)


expected_answer = 1074

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