# Project Euler #82 - path sum: three ways

Here's my solution:

def main():
matrix = [
[131, 673, 234, 103,  18],
[201,  96, 342, 965, 150],
[630, 803, 746, 422, 111],
[537, 699, 497, 121, 956],
[805, 732, 524,  37, 331]
]

size = len(matrix)
best = [matrix[row][0] for row in range(size)]

for col in range(1, size):
column = [matrix[row][col] for row in range(size)]
tmp = column[:]

for i in range(size):
column[i] += best[i] # right

for j in range(0, i): # up
if sum([best[j]]+tmp[j:i+1]) < column[i]:
column[i] = sum([best[j]]+tmp[j:i+1])

for k in range(i, size): # bottom
if sum([best[k]] +tmp[i:k+1]) < column[i]:
column[i] = sum([best[k]] +tmp[i:k+1])

best = column
#print(best)

return min(best)

if __name__ == "__main__":
print(main())


Please advise how it can be improved.

• Here's a interesting read on #82 if you haven't seen it yet – megawac Jan 1 '14 at 23:30
• @megawac This solution uses the same strategy described in the article, except that it's already more eloquent. – 200_success Jan 2 '14 at 9:26

To solve the Project Euler challenge, you'll have to handle a large matrix from a file. Therefore, your function should accept the matrix as a parameter.

You used size to represent both the number of rows and the number of columns. I would use two variables to avoid hard-coding the assumption that the input is a square matrix.

Your dynamic programming algorithm is sound. I would use the min() function to avoid finding the minimum by iteration. Also, setting best all at once instead of mutating the elements of column avoids having to copy column into a temporary variable.

def euler82(matrix):
nrows, ncols = len(matrix), len(matrix[0])
best = [matrix[row][0] for row in range(nrows)]

for col in range(1, ncols):
column = [matrix[row][col] for row in range(nrows)]

best = [
# The cost of each cell, plus...
column[row] +

# the cost of the cheapest approach to it
min([
best[prev_row] + sum(column[prev_row:row:(1 if prev_row <= row else -1)])
for prev_row in range(nrows)
])
for row in range(nrows)
]

#print(best)

return min(best)