|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 18: Maximum Path Sum I |
|
3
|
|
|
============================================ |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem18 |
|
6
|
|
|
:synopsis: My solution to problem #18. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem18.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top |
|
|
|
|
|
|
15
|
|
|
to bottom is :math:`23`. |
|
16
|
|
|
|
|
17
|
|
|
.. math:: |
|
18
|
|
|
|
|
19
|
|
|
&&&& \\color{red}{3} &&& \\\\ |
|
20
|
|
|
&&& \\color{red}{7} && 4 && \\\\ |
|
21
|
|
|
&& 2 && \\color{red}{4} && 6 & \\\\ |
|
22
|
|
|
& 8 && 5 && \\color{red}{9} && 3 |
|
23
|
|
|
|
|
24
|
|
|
That is, :math:`3 + 7 + 4 + 9 = 23`. |
|
25
|
|
|
|
|
26
|
|
|
Find the maximum total from top to bottom of the triangle below: |
|
27
|
|
|
|
|
28
|
|
|
.. math:: |
|
29
|
|
|
|
|
30
|
|
|
&&&&&&&&&&&&&&& 75 &&&&&&&&&&&&&& \\\\ |
|
31
|
|
|
&&&&&&&&&&&&&& 95 && 64 &&&&&&&&&&&&& \\\\ |
|
32
|
|
|
&&&&&&&&&&&&& 17 && 47 && 82 &&&&&&&&&&&& \\\\ |
|
33
|
|
|
&&&&&&&&&&&& 18 && 35 && 87 && 10 &&&&&&&&&&& \\\\ |
|
34
|
|
|
&&&&&&&&&&& 20 && 04 && 82 && 47 && 65 &&&&&&&&&& \\\\ |
|
35
|
|
|
&&&&&&&&&& 19 && 01 && 23 && 75 && 03 && 34 &&&&&&&&& \\\\ |
|
36
|
|
|
&&&&&&&&& 88 && 02 && 77 && 73 && 07 && 63 && 67 &&&&&&&& \\\\ |
|
37
|
|
|
&&&&&&&& 99 && 65 && 04 && 28 && 06 && 16 && 70 && 92 &&&&&&& \\\\ |
|
38
|
|
|
&&&&&&& 41 && 41 && 26 && 56 && 83 && 40 && 80 && 70 && 33 &&&&&& \\\\ |
|
39
|
|
|
&&&&&& 41 && 48 && 72 && 33 && 47 && 32 && 37 && 16 && 94 && 29 &&&&& \\\\ |
|
40
|
|
|
&&&&& 53 && 71 && 44 && 65 && 25 && 43 && 91 && 52 && 97 && 51 && 14 &&&& \\\\ |
|
41
|
|
|
&&&& 70 && 11 && 33 && 28 && 77 && 73 && 17 && 78 && 39 && 68 && 17 && 57 &&& \\\\ |
|
42
|
|
|
&&& 91 && 71 && 52 && 38 && 17 && 14 && 91 && 43 && 58 && 50 && 27 && 29 && 48 && \\\\ |
|
43
|
|
|
&& 63 && 66 && 04 && 68 && 89 && 53 && 67 && 30 && 73 && 16 && 69 && 87 && 40 && 31 & \\\\ |
|
44
|
|
|
& 04 && 62 && 98 && 27 && 23 && 09 && 70 && 98 && 73 && 93 && 38 && 53 && 60 && 04 && 23 |
|
45
|
|
|
|
|
46
|
|
|
.. note:: as there are only :math:`16384` routes, it is possible to solve this problem by trying every route. However, |
|
|
|
|
|
|
47
|
|
|
:mod:`Problem 67 <solutions.problem67>`, is the same challenge with a triangle containing one-hundred rows; it |
|
|
|
|
|
|
48
|
|
|
cannot be solved by brute force, and requires a clever method! ;o) |
|
49
|
|
|
|
|
50
|
|
|
Solution Discussion |
|
51
|
|
|
################### |
|
52
|
|
|
|
|
53
|
|
|
This problem can be efficiently solved using a dynamically programming algorithm. |
|
54
|
|
|
|
|
55
|
|
|
The algorithm iterates over the rows of the triangle, :math:`t_i`, and builds a list of partial solutions, :math:`p_j`, |
|
|
|
|
|
|
56
|
|
|
that provide the maximum path sum ending at the :math:`(i,j)^{th}` position in the triangle. This is built one row at a |
|
|
|
|
|
|
57
|
|
|
time. |
|
58
|
|
|
|
|
59
|
|
|
Upon reaching the final row, :math:`p_j` contains the maximum path sum from the root of the triangle to |
|
|
|
|
|
|
60
|
|
|
:math:`t_{n - 1,j}` for :math:`j \\in 0, \\dots, n - 1`. The maximum path sum overall is simply then the maximum value |
|
|
|
|
|
|
61
|
|
|
in :math:`p`. |
|
62
|
|
|
|
|
63
|
|
|
As noted in the problem description, a naive brute-force must consider each of the :math:`2^{15} = 32768` distinct |
|
|
|
|
|
|
64
|
|
|
paths. While this would be relatively quick, the algorithm has exponential time complexity in the depth :math:`n` of the |
|
|
|
|
|
|
65
|
|
|
triangle. That is, :math:`O(2^{n-1})` where :math:`n` is the number of rows in the triangle. |
|
66
|
|
|
|
|
67
|
|
|
.. note:: the problem is wrong, there are actually :math:`2^{15}` paths not :math:`2^{14}` through this triangle. |
|
|
|
|
|
|
68
|
|
|
|
|
69
|
|
|
This dynamic programming algorithm has time complexity :math:`O(1 + 2 + ... + n) = O(n^2)`. |
|
70
|
|
|
|
|
71
|
|
|
Solution Implementation |
|
72
|
|
|
####################### |
|
73
|
|
|
|
|
74
|
|
|
.. literalinclude:: ../../solutions/problem18.py |
|
75
|
|
|
:language: python |
|
76
|
|
|
:lines: 79- |
|
77
|
|
|
""" |
|
78
|
|
|
|
|
79
|
|
|
from typing import List |
|
80
|
|
|
|
|
81
|
|
|
|
|
82
|
|
|
def max_path_sum(triangle: List[List[int]]) -> int: |
|
83
|
|
|
""" Compute the maximum path sum through the triangle |
|
84
|
|
|
|
|
85
|
|
|
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 |
|
|
|
|
|
|
86
|
|
|
the next, it may connect to adjacent entries only. |
|
87
|
|
|
|
|
88
|
|
|
:param triangle: :math:`2`-dimensional list of integers (the triangle) |
|
89
|
|
|
:return: the maximum path sum through `triangle` |
|
90
|
|
|
""" |
|
91
|
|
|
|
|
92
|
|
|
# Perform some simple validation on triangle |
|
93
|
|
|
assert isinstance(triangle, list), "triangle must be a triangular 2-dimensional list of integers" |
|
|
|
|
|
|
94
|
|
|
for i, row in enumerate(triangle): |
|
95
|
|
|
assert len(row) == i + 1, "row {} has length {}, it should have {} to be triangular".format(i, len(row), i + 1) |
|
|
|
|
|
|
96
|
|
|
for elt in row: |
|
97
|
|
|
assert isinstance(elt, int), "triangle entries must be integers" |
|
98
|
|
|
|
|
99
|
|
|
# Build up the answer one row at a time using a dynamic programming algorithm |
|
100
|
|
|
n = len(triangle) |
|
|
|
|
|
|
101
|
|
|
partial_sum_to = [0] * n |
|
102
|
|
|
for i in range(n): |
|
103
|
|
|
# After each iteration i, part_sum_to[j] is the maximum path sum ending at triangle[i][j] |
|
104
|
|
|
temp_partial_sum = partial_sum_to.copy() # keep an unmodified version of partial_sum from last iteration |
|
|
|
|
|
|
105
|
|
|
temp_partial_sum[0] = partial_sum_to[0] + triangle[i][0] # only one possible path ends at triangle[i][0] |
|
|
|
|
|
|
106
|
|
|
for j in range(1, i): |
|
107
|
|
|
temp_partial_sum[j] = max(partial_sum_to[j - 1], partial_sum_to[j]) + triangle[i][j] |
|
108
|
|
|
temp_partial_sum[i] = partial_sum_to[i - 1] + triangle[i][i] # only one possible path ends at triangle[i][i] |
|
|
|
|
|
|
109
|
|
|
partial_sum_to = temp_partial_sum |
|
110
|
|
|
|
|
111
|
|
|
return max(partial_sum_to) # find the maximum path sum ending at one of the leaf nodes |
|
112
|
|
|
|
|
113
|
|
|
|
|
114
|
|
|
def solve(): |
|
115
|
|
|
""" Compute the answer to Project Euler's problem #18 """ |
|
116
|
|
|
triangle = [ |
|
117
|
|
|
[75], |
|
|
|
|
|
|
118
|
|
|
[95, 64], |
|
|
|
|
|
|
119
|
|
|
[17, 47, 82], |
|
|
|
|
|
|
120
|
|
|
[18, 35, 87, 10], |
|
|
|
|
|
|
121
|
|
|
[20, 4, 82, 47, 65], |
|
|
|
|
|
|
122
|
|
|
[19, 1, 23, 75, 3, 34], |
|
|
|
|
|
|
123
|
|
|
[88, 2, 77, 73, 7, 63, 67], |
|
|
|
|
|
|
124
|
|
|
[99, 65, 4, 28, 6, 16, 70, 92], |
|
|
|
|
|
|
125
|
|
|
[41, 41, 26, 56, 83, 40, 80, 70, 33], |
|
|
|
|
|
|
126
|
|
|
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29], |
|
|
|
|
|
|
127
|
|
|
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14], |
|
|
|
|
|
|
128
|
|
|
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57], |
|
|
|
|
|
|
129
|
|
|
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48], |
|
|
|
|
|
|
130
|
|
|
[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31], |
|
|
|
|
|
|
131
|
|
|
[ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23] |
|
|
|
|
|
|
132
|
|
|
] |
|
133
|
|
|
return max_path_sum(triangle) |
|
134
|
|
|
|
|
135
|
|
|
|
|
136
|
|
|
expected_answer = 1074 |
|
|
|
|
|
|
137
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.