# Increasing readability of maximum path sum algorithm

I had written a solution for Project Euler problem 18 in Python 3. It is good in its efficiency but the problem is the readability and I think reuse.

The algorithm used is that at every iteration the maximum for all numbers in a row is calculated starting from the top and going down to find the largest path.

#This function is in "files" and used in the solution
def get_lines(path, file_name):
with open(path + os.sep + file_name) as f:
for line in f:
yield line.rstrip('\n')

def prob_018():
matrix = [[int(i) for i in line.split(' ')]
for line in files.get_lines(RESOURCES, "018.txt")]
for row_num in range(1, len(matrix)):
pre = matrix[row_num - 1]
cur = matrix[row_num]

for el_num in range(len(cur)):
total = cur[el_num]
if el_num == 0:
total += pre[el_num]
elif el_num == len(cur) - 1:
total += pre[el_num - 1]
else:
total += pre[el_num - 1] if pre[el_num - 1] > pre[el_num] \
else pre[el_num]

matrix[row_num][el_num] = total
return max(matrix[len(matrix) - 1])


The purpose of your program was unclear to me before reading the problem description. I could understand the logic flow, but I had no idea what answer it was seeking.

• The name matrix implies a rectangle. While triangle or pyramid are more descriptive, I'd go with rows for readability and a comment about the shape they form. The special handling of the first and last values of cur was confusing when assuming each row was the same size.

• Since this same code will be reused in problem 67 and to improve testability, rename the function and move the specifics of problem 18 to its own method.

These two simple changes yield the following:

def prob_018():

return [[int(i) for i in line.split(' ')]
for line in files.get_lines(RESOURCES, file)]

def maximum_path(rows): ...


The main algorithm has three steps:

1. Iterate over each pair of rows.
2. Calculate the better path to each cell in the lower row from the two cells above it.
3. Return the maximum value from the last row.

One thing that makes this difficult is that you're modifying the rows along the way. This makes extracting functions harder since they have side-effects. Instead, leave the original values untouched and build up an accumulator to hold the best path sums. Extracting this to a new accumulate_steps function yields a very readable outer algorithm:

def maximum_path(rows):
paths = None
for row in rows:
paths = accumulate_steps(paths, row)
return max(paths) if paths else None


This introduces a common trick to simplify high-level logic: moving special-case checks into extracted methods. Writing accumulate_steps to accept None for paths also allows maximum_path to handle the empty list and single-row corner cases.

With that out of the way we can focus on combining the current best paths (accumulator) with the next row to form the new best paths. Rewriting your original code to build a new row is sufficient:

def accumulate_steps(paths, row):
if paths is None:
return row
el_num in range(len(row)):
total = row[el_num]
if el_num == 0:
total += paths[el_num]
elif el_num == len(row) - 1:
total += paths[el_num - 1]
else:
total += paths[el_num - 1] if paths[el_num - 1] > paths[el_num] \
else paths[el_num]
row[el_num] = total


but I found it easier to move the first/last element handling out of the loop. Also, negative list indexes reduce the calls to len which cleans up the logic a bit. My first refactoring built a new list in-place with similar procedural code:

def accumulate_steps(paths, row):
if paths is None:
return row
sums =  * len(row)
sums = paths + row
sums[-1] = paths[-1] + row[-1]
for i in range(1, len(row) - 1):
sums[i] = row[i] + max(paths[i - 1], paths[i])


While it works, converting this to a list comprehension and adding on the first and last cells using + seems more Pythonic to me:

def accumulate_steps(paths, row):
if paths is None:
return row
return ([paths + row]
+ [row[i] + max(paths[i - 1], paths[i]) for i in range(1, len(row) - 1)]
+ [paths[-1] + row[-1]])


Putting it Together

def prob_018():

return [[int(i) for i in line.split(' ')]
for line in files.get_lines(RESOURCES, file)]

def maximum_path(rows):
paths = None
for row in rows:
paths = accumulate_steps(paths, row)
return max(paths)

def accumulate_steps(paths, row):
if paths is None:
return row
return ([paths + row]
+ [row[i] + max(paths[i - 1], paths[i]) for i in range(1, len(row) - 1)]
+ [paths[-1] + row[-1]])

• Point 4 of problem 67 I had done after posting this question. Good point about the name. But how do you go about extracting the functions from a big block that someone(me) wrote earlier? I can understand read_rows but what about the others? Any pointers on that? – Aseem Bansal Mar 30 '14 at 17:40
• @AseemBansal I've broken it down into steps to show my thinking. – David Harkness Mar 30 '14 at 18:56