Minimum path sum in a triangle (Project Euler 18 and 67) with Python

As problem 67 is harder, I'll go with that one:

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 23.

             3
7 4
2 4 6
8 5 9 3


That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

I solved this using dynamic programming. Here's my code:

def max_triangle_sum(triangle, height):
if height == 1:
return triangle[0][0]

dp = [[-1] * row_index for row_index in range(1, height + 1)]

dp[0][0] = triangle[0][0]

for i in range(1, height):
dp[i][0] = dp[i-1][0] + triangle[i][0]
dp[i][i] = dp[i-1][i-1] + triangle[i][-1]

for j in range(1, i):
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

return max(dp[-1])

if __name__ == '__main__':
height = None

while True:
try:
height = int(input('Please enter height of the triangle: '))

if height <= 0:
raise Exception('Height cannot be negative or 0')

break

except Exception as e:
print(f'Error occurred: {e}')
print()

triangle = []

for row_index in range(1, height + 1):
while True:
try:
row = list(map(int, input(f'Please enter {row_index} space seperated integer(s): ').split()))

if len(row) != row_index:
raise Exception(f'Exactly {row_index} numbers required')

if any(number < 0 for number in row):
raise Exception(f'Numbers cannot be negative')

triangle.append(row)

break

except Exception as e:
print(f'Error occurred: {e}')
print()

print('The maximum triangle sum is: ')
print(max_triangle_sum(triangle, height))


This runs quite fast, considering it would actually take 20 billion years (If your computer can compute 10^12 operations in 1 second) to solve using brute force. But still, it doesn't look that good

How do I improve this code?

• Possibly helpful: Project Euler # 67 Maximum path sum II (Bottom up) in Python. Nov 25, 2019 at 14:53
• @MartinR Yes, very much. Thank you!
– Sriv
Nov 25, 2019 at 14:54
• I managed to solve this problem in reasonable time with a Djikstra algorithm. Nov 26, 2019 at 13:40
• Yes, I know about Dijkstra's algorithm! Amazing idea! Can you please share you solution?
– Sriv
Nov 26, 2019 at 13:43
• @Srivaths I'll be happy to share it as soon as I can. It is on a computer that's currently being repaired... Nov 26, 2019 at 13:45

Minor Cleanup

Contrary to @Graipher's opinion, I find your max_triangle_sum implementation is reasonably clear. Although, I'm not sure I'd refer to it as dynamic programming; it is simply computing top-down the maximum sums for each row.

dp = [[-1] * row_index for row_index in range(1, height + 1)]


What does row_index mean? It doesn't convey any meaning other than the index number of the row. [-1] * row_index is ... mysterious. row_length conveys meaning: it is length of the row, and [-1] * row_length tells the reader you have a row of -1 values of a certain length.

What is the -1 mean? Where is it used? This statement creates a triangular data structure, with -1 at each cell, but only to allocate the structure. The actual -1 value is not used; it is unconditionally overwritten in the following code. If you have a mistake in the following code, it might use this -1 value, and quietly produce erroneous results. If you used None instead of -1, if you ever accidentally used the value in a cell before it has been assigned, Python would raise an exception.

dp = [[None] * row_length for row_length in range(1, height + 1)]


Avoid negative indexing.

   dp[i][i] = dp[i-1][i-1] + triangle[i][-1]


Here, triangle[i][-1] is referring to the last cell on the ith row. But the cells on the ith row from from 0 to i, so triangle[i][-1] simply means triangle[i][i]. You are already assigning to dp[i][i], so this gives the statement a nice symmetry:

   dp[i][i] = dp[i-1][i-1] + triangle[i][i]


You don't really need to pass height to max_triangle_sum: it can easily be computed as:

   height = len(triangle)


Space

Because you are allocating dp to hold the values of sum of the paths to each cell of each row of the triangle, your solution takes $$\O(N^2)\$$ space to find the solution.

Consider these statements:

    dp[i][0] = dp[i-1][0] + triangle[i][0]
dp[i][i] = dp[i-1][i-1] + triangle[i][-1]
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]


dp[i][...] only depends upon values in d[i - 1][...]. This means you only need the previous dp row to compute the next dp row; you don't need the whole dp triangle structure, just two rows:

    curr = [triangle[0][0]]

for i in range(1, height):

prev = curr
curr = [None] * (i + 1)

curr[0] = prev[0] + triangle[i][0]
curr[i] = prev[i - 1] + triangle[i][i]

for j in range(1, i):
curr[j] = max(prev[j - 1], prev[j]) + triangle[i][j]


As a bonus, this should be faster, since less indexing is being performed.

We've still got triangle[i] being indexed constantly. We can eliminate that by iterating over the rows of triangle directly. We'll use enumerate() so we keep the row index:

    for i, row in enumerate(triangle[1:], 1):

prev = curr
curr = [None] * (i + 1)

curr[0] = prev[0] + row[0]
curr[i] = prev[i - 1] + row[i]

for j in range(1, i):
curr[j] = max(prev[j - 1], prev[j]) + row[j]


That's a little cleaner, and a little faster.

Now the ugliest part having to handle the first and last value separately. The problem is there is no value before the first element, and no value after the last element to compute the max() on. But why isn't there? Or more to the point, why can't there be? If you padded the previous row with duplicated first and last values, you'd turn those special cases into the regular case of a value in the middle of the row:

    for i, row in enumerate(triangle[1:], 1):

prev = [curr[0]] + curr + [curr[-1]]     # Duplicate first & last values
curr = [None] * (i + 1)

for j in range(0, i + 1):
curr[j] = max(prev[j], prev[j + 1]) + row[j]


Note: I've had to change prev[j-1] and prev[j] to prev[j] and prev[j + 1] to account for the changed indices, due to the duplicated value at the start.

Now, we are filling in all the values of curr in a simple for loop. This screams list comprehension. No need to allocate the curr list ahead of time anymore.

    for i, row in enumerate(triangle[1:], 1):

prev = [curr[0]] + curr + [curr[-1]]     # Duplicate first & last values
curr = [max(prev[j], prev[j + 1]) + row[j] for j in range(0, i + 1) ]


But we're still doing a lot of indexing. We've got prev[j], and row[j] which are normalish indexes, and we've got prev[j + 1] which could be considered adjusted_prev[j] if we assigned adjusted_prev the values of prev[1:]. Then, with all the values being retrieved by a simple [j] index, we can let Python do the indexing for us but turning the indexing into iteration. Finally, since Python knows the number of values in the lists, we no longer need the i index:

    for row in triangle[1:]:

prev = [curr[0]] + curr + [curr[-1]]     # Duplicate first & last values
curr = [max(a, b) + x for a, b, x in zip(prev[:-1], prev[1:], row) ]


Since prev[:-1] gives us all the values of the curr with the first value duplicated, and prev[1:] gives us all the values of curr with the last value duplicated, we don't even need prev:

def max_triangle_sum(triangle):

curr = [triangle[0][0]]

for row in triangle[1:]:
curr = [max(a, b) + x for a, b, x in zip([curr[0]] + curr, curr + [curr[-1]], row)]

return max(curr)


The space requirement (ignoring triangle) is now $$\O(N)\$$, since only the previous row needs to be held in memory while the current row is being computed.

If it is guaranteed that the triangle only contains positive numbers, and since max(0, x) == x whenever x is positive, then instead of duplicating the first and last values, we could append and prepend a zero to each end. This will allow us to remove the first row as a special case:

def max_triangle_sum(triangle):

curr = []
zero = [0]

for row in triangle:
curr = [max(a, b) + x for a, b, x in zip(zero + curr, curr + zero, row)]

return max(curr)


Now, triangle doesn't even need to be held in memory. Instead, an iterable object could be passed in, which could read the triangle in line by line on demand, further ensuring an $$\O(N)\$$ memory solution.

See other answers for great feedback on input sanitization, and reading the triangle data from a file.

General

Since the problem gives the triangle as a text file, your program should probably be able to read that file. It would be quite a lot of work to input them manually, and when using the file like in python triangle.py < triangle.txt a first row with the number of lines needs to be added. This reading function can be quite simple:

def read_triangle(file_name):
with open(file_name) as f:
return [list(map(int, line.split())) for line in f]


Algorithm

As for the actual algorithm, I'm not quite sure what yours does. Which means that it is not very readable :). Not having any documentation, like a docstring does not help either.

The easiest algorithm for this is a bottom up approach that reduces each line into the maximum sum reachable from the line above it.

def reduce_rows(row, row_below):
"""Reduces two consecutive rows to the maximum reachable sum from the top row."""
return [max(row_below[i], row_below[i+1]) + row[i] for i in range(len(row))]

def max_sum(triangle):
"""Find the maximum sum reachable in the triangle."""
row_below = triangle.pop()
for row in reversed(triangle):
row_below = reduce_rows(row, row_below)
# print(row_below)
return row_below[0]

if __name__ == "__main__":
print(max_sum(triangle))


Style

It's a good thing that you are already using a if __name__ == "__main__": guard. You also seem to be mostly following Python's official style-guide, PEP8. The only thing you could improve on that part is to reduce the number of blank lines. While some help the readability, parts that are logically connected should be in one block:

height = None
while True:
try:
height = int(input('Please enter height of the triangle: '))
if height <= 0:
raise Exception('Height cannot be negative or 0')
break
except Exception as e:
print(f'Error occurred: {e}\n')

triangle = []
for row_index in range(1, height + 1):
while True:
try:
row = list(map(int, input(f'Please enter {row_index} space seperated integer(s): ').split()))
if len(row) != row_index:
raise Exception(f'Exactly {row_index} numbers required')
elif any(number < 0 for number in row):
raise Exception(f'Numbers cannot be negative')
else:
triangle.append(row)
break
except Exception as e:
print(f'Error occurred: {e}\n')


I also put the separate exceptions and the happy path into an if..elif..else structure. This is not really needed (the other cases are never reachable if an exception is raised), but IMO it helps with readability. It also make it easier if at some point you decide that those should just print a message directly, instead of raising an exception that is immediately caught only to be printed. You could make those print statements directly, which would allow you to be more specific about the exception you expect. This makes it so that all other exceptions stop the program (as they should):

while True:
try:
height = int(input('Please enter height of the triangle: '))
except ValueError as e:
print(f'Error occurred: {e}\n')
if height > 0:
break
else:
print('Error occurred:  Height cannot be negative or 0')

triangle = []
for row_index in range(1, height + 1):
while True:
try:
row = list(map(int, input(f'Please enter {row_index} space separated integer(s): ').split()))
except ValueError as e:
print(f'Error occurred: {e}\n')
if len(row) != row_index:
print(f'Error occurred:  Exactly {row_index} numbers required')
elif any(number < 0 for number in row):
print(f'Error occurred:  Numbers cannot be negative')
else:
triangle.append(row)
break


Better user input

This is actually a good place to implement a function asking for user input and validating it. We need type validation and input validation here, so this should suffice:

def ask_user(message, type_=str, validate=None, non_valid_msg=""):
while True:
try:
user_input = type_(input(message))
except ValueError as e:
print(f"Expected {type_}")
continue
if validate is not None:
if validate(user_input):
return user_input
else:
print(non_valid_msg)
else:
return user_input


Which makes your code a lot easier:

def list_of_int(s):
return list(map(int, s.split()))

if __name__ == "__main__":
height = ask_user("Please enter height of the triangle: ", int,
lambda h: h > 0, "Height must be positive")
triangle = [ask_user(f"Please enter {n} space separated integer(s): ", list_of_int,
lambda l: len(l) == n, f"Exactly {n} numbers required")
for n in range(1, height + 1)]
...


Don't raise generic exceptions

Avoid raising a generic Exception. To catch it, you'll have to catch all other more specific exceptions that subclass it.

Instead of raising Exception directly when the user inputs a bad height, consider raising a RuntimeError, or in a larger codebase, a custom subclass. Then, explicitly list all of the exceptions you expect to be raised in your except clause, e.g. TyperError and RuntimeError.

Local variable names

The name dp isn't terribly informative as to what the list contains. Consider refactoring to something more descriptive.

Using globals in time-senstive code

Project Euler problems tend to require some fairly intensive computations. It may be advisable to try extract as much performance as possible inside of critical portions of you code, such as within nested loops.

In your solution, all of the variables used after if __name__ == '__main__' are in fact global variables, which are slower than local variables. For a mild performance boost, consider refactoring all of this code into a main function, which you may then call after the __main__ guard:

def main():
height = None
...
print('The maximum triangle sum is: ')
print(max_triangle_sum(triangle, height))

if __name__ == '__main__':
main()


Dummy values

You initially assign height = None, but there is no branch where height keeps that value. Therefore, it isn't necessary to initialize height at this time, since it is guaranteed to be given a value by the branches that follow.

Some organization encourage initializing variables early on with dummy values so that developers can immediately see what variables will be in play in the code that follows. Others discourage this practice, since it can give developers a false sense of what values a variable is expected to take on (e.g. will height be None later?). Whether you choice to initialize variables early with dummy values largely comes down to stylistic preferences.

Documentation

You don't have any comments or docstrings in your code. These forms of documentation are extremely helpful for people who must read your code, which include both other developers as well you when you return to your code after working on another project for two months. Some basic conventions for writing docstrings are laid out in PEP 257.