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

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

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,

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

          :mod:`Problem 67 <solutions.problem67>`, is the same challenge with a triangle containing one-hundred rows; it

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

          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`,

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

that provide the maximum path sum ending at the :math:`(i,j)^{th}` position in the triangle. This is built one row at a

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

time.

Upon reaching the final row, :math:`p_j` contains the maximum path sum from the root of the triangle to

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

:math:`t_{n - 1,j}` for :math:`j \\in 0, \\dots, n - 1`. The maximum path sum overall is simply then the maximum value

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

in :math:`p`.

As noted in the problem description, a naive brute-force must consider each of the :math:`2^{15} = 32768` distinct

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

paths. While this would be relatively quick, the algorithm has exponential time complexity in the depth :math:`n` of the

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

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 line is too long as per the coding-style (113/100).

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

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

    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"

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

    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)

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

        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

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

        temp_partial_sum[0] = partial_sum_to[0] + triangle[i][0]  # only one possible path ends at triangle[i][0]

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

        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]

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

        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],

Wrong hanging indentation (remove 28 spaces).

                                  [95, 64],

Wrong hanging indentation (remove 26 spaces).

                                [17, 47, 82],

Wrong hanging indentation (remove 24 spaces).

                              [18, 35, 87, 10],

Wrong hanging indentation (remove 22 spaces).

                            [20,  4, 82, 47, 65],

Wrong hanging indentation (remove 20 spaces).

Exactly one space required after comma

                          [19,  1, 23, 75,  3, 34],

Wrong hanging indentation (remove 18 spaces).

Exactly one space required after comma

                        [88,  2, 77, 73,  7, 63, 67],

Wrong hanging indentation (remove 16 spaces).

Exactly one space required after comma

                      [99, 65,  4, 28,  6, 16, 70, 92],

Wrong hanging indentation (remove 14 spaces).

Exactly one space required after comma

                    [41, 41, 26, 56, 83, 40, 80, 70, 33],

Wrong hanging indentation (remove 12 spaces).

                  [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],

Wrong hanging indentation (remove 10 spaces).

                [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],

Wrong hanging indentation (remove 8 spaces).

              [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],

Wrong hanging indentation (remove 6 spaces).

            [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],

Wrong hanging indentation (remove 4 spaces).

          [63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],

Wrong hanging indentation (remove 2 spaces).

Exactly one space required after comma

        [ 4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23]

No space allowed after bracket

Exactly one space required after comma

    ]
    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_]*)|(__.*__))$).