I recently finished up Problem 18 (and shortly thereafter, Problem 67). This was a fairly interesting problem, because I like graph theory even if I'm bad at it, and I immediately thought graph theory when I read this problem.
I started creating Vertex and Edge classes, but quickly decided that was too heavyweight for such a small problem. Instead, I chose to use a list of lists where the left-hand child of a node is stored in the next row on the same column and the right-hand child is stored in the next row and the next column.
This made representing and using the data fairly straightforward, but I kept running into the problem of doing an exhaustive search. I knew this was suboptimal (and completely unsuited for the related Problem 67), but I was so locked into thinking of the triangle from the top-down I made things over-complicated.
Eventually, I decided I needed to reset my thinking and Googled for hints. Once I started thinking of the problem from the bottom up (since the graph, after all, is not directed), the solution became clear. Since I didn't need the actual path, I modified the existing data structure to minimize memory requirements.
def find_max_sum(triangle):
"""
Find the maximum sum for a path from the top to the bottom of ``triangle``.
>>> test = [[3,], \
[7, 5], \
[2, 4, 6], \
[8, 5, 9, 3]]
>>> find_max_sum(test)
23
"""
while len(triangle) > 1:
_reduce_triangle(triangle)
return triangle[0][0]
def _reduce_triangle(to_reduce):
"""
Reduce ``to_reduce`` in place by rolling up the maximum path info one row.
Don't return anything to emphasize the in-place nature of this function.
>>> test = [[3,], \
[7, 5], \
[2, 4, 6], \
[8, 5, 9, 3]]
>>> _reduce_triangle(test)
>>> test
[[3], [7, 5], [10, 13, 15]]
>>> _reduce_triangle(test)
>>> test
[[3], [20, 20]]
>>> _reduce_triangle(test)
>>> test
[[23]]
"""
last_row = to_reduce[-1]
for index in xrange(len(to_reduce) - 1):
to_reduce[-2][index] += max(last_row[index:index + 2])
del to_reduce[-1]
def main():
"""
Solve `Problem 18`_ of Project Euler.
.. _Problem 18: http://projecteuler.net/index.php?section=problems&id=18
"""
actual = [[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]]
print find_max_sum(actual)
if __name__ == '__main__':
main()
Starting with this, the solution for Problem 67 is trivial: just write some code to parse the triangle out of a text file instead of coding it directly into the source code:
def find_max_sum(triangle):
"""
Find the maximum sum for a path from the top to the bottom of ``triangle``.
>>> test = [[3,], \
[7, 5], \
[2, 4, 6], \
[8, 5, 9, 3]]
>>> find_max_sum(test)
23
"""
while len(triangle) > 1:
_reduce_triangle(triangle)
return triangle[0][0]
def _reduce_triangle(to_reduce):
"""
Reduce ``to_reduce`` in place by rolling up the maximum path info one row.
Don't return anything to emphasize the in-place nature of this function.
>>> test = [[3,], \
[7, 5], \
[2, 4, 6], \
[8, 5, 9, 3]]
>>> _reduce_triangle(test)
>>> test
[[3], [7, 5], [10, 13, 15]]
>>> _reduce_triangle(test)
>>> test
[[3], [20, 20]]
>>> _reduce_triangle(test)
>>> test
[[23]]
"""
last_row = to_reduce[-1]
for index in xrange(len(to_reduce) - 1):
to_reduce[-2][index] += max(last_row[index:index + 2])
del to_reduce[-1]
def _parse_triangle_from_file(data_file):
"""
Parse out the triangle data from ``data_file``.
>>> _parse_triangle_from_file('test_triangle.txt')
[[3], [7, 5], [10, 13, 15]]
"""
triangle = []
with open(data_file, 'r') as triangle_file:
for line in triangle_file:
triangle.append([int(x) for x in line.split()])
return triangle
def main():
"""
Solve `Problem 67`_ of Project Euler.
.. _Problem 67: http://projecteuler.net/index.php?section=problems&id=67
"""
print find_max_sum(_parse_triangle_from_file('triangle.txt'))
if __name__ == '__main__':
main()
