Project Euler Problem 82 Solution: Path Sum: Three Ways

Project Euler Problem 82 Statement

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the $5$ by $5$ matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to $994$.

$$ \begin{pmatrix} 131 & 673 & \color{darkred}{234} & \color{darkred}{103} & \color{darkred}{18}\\ \color{darkred}{201} & \color{darkred}{96} & \color{darkred}{342} & 965 & 150\\ 630 & 803 & 746 & 422 & 111\\ 537 & 699 & 497 & 121 & 956\\ 805 & 732 & 524 & 37 & 331 \end{pmatrix} $$

Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an $80$ by $80$ matrix.

Solution

This is another dynamic programming solution (DP) similar to the one we used to solve Project Euler Problem 81. The process is simple to follow and I'll outline it here:

Initialize the last column: Start with the last column as the "current" minimum path sums.
Iterate through columns in reverse: Start from the second-last column and move to the first column.
Update path sums for the rightward move: Add the current column's value to the path sums.
Update for upward and downward movements: Sweep the min_path[] array up and down to account for possible movement in those directions.
Return the minimum value: The result is the smallest path sum for the leftmost column.

Let's take a deep dive into the process.

Initialize a 3 × 3 matrix and set `min_path[]` as the last column:

m = [
    [131, 673, 234],
    [201,  96, 342],
    [630, 803, 746]
]
n = 3  # the matrix is a square so both dimensions are the same
min_path = [234, 342, 746]  #initially the minimum path sums is last column

Iteration (column = 1):

Update min_path[] for moving right:

min_path[0] += m[0][1]  # 234 + 673 = 907
min_path = [907, 342, 746]

Move downward:

min_path[1] = min(342, 907) + 96  # min(342, 907) + 96 = 438
min_path[2] = min(746, 438) + 803  # min(746, 438) + 803 = 1241
min_path = [907, 438, 1241]

Move upward:

min_path[1] = min(438, 1241) + 96  # min(438, 1241) + 96 = 438
min_path[0] = min(907, 438) + 673  # min(907, 438) + 673 = 1111
min_path = [1111, 438, 1241]

Last iteration (column = 0):

Update min_path[] for moving right:

min_path[0] += m[0][0]  # 1111 + 131 = 1242
min_path = [1242, 438, 1241]

Move downward:

min_path[1] = min(438, 1242) + 201  # min(438, 1242) + 201 = 639
min_path[2] = min(1241, 639) + 630  # min(1241, 639) + 630 = 1269
min_path = [1242, 639, 1269]

Move upward:

min_path[1] = min(639, 1269) + 201  # min(639, 1269) + 201 = 639
min_path[0] = min(1242, 639) + 131  # min(1242, 639) + 131 = 770
min_path = [770, 639, 1269]

Result:

print(min(min_path))  # 639 (This is the minimal path sum for the given example.)

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 82

HackerRank Project Euler 82 the matrix size is increased to 1000 × 1000.

Python Source Code

M = [list(map(int, input().split())) for _ in range(int(input()))]
n = len(M)

min_path = [r[-1] for r in M]
for col in range(len(M[0])-2, -1, -1):
    min_path[0]+= M[0][col]
    for row in range(1, n): 
        min_path[row] = min(min_path[row], min_path[row-1]) + M[row][col]
    for row in range(n-2, -1, -1): 
        min_path[row] = min(min_path[row], min_path[row+1] + M[row][col])

print(min(min_path))