Project Euler Problem 82

Solution

Answer: 260324

1. Mathematical analysis

We are given an $80\times 80$ matrix and want the minimum path sum from any cell in the left column to any cell in the right column, moving only:

right
up
down

This is harder than Problem 81 because vertical motion is now allowed in both directions.

Step 1: Reformulate as a shortest-path problem

Think of each matrix entry as a node with a cost equal to its value.

A move from one cell to another is allowed if it is:

right,
up,
or down.

We want the minimum-cost path beginning anywhere in column $0$ and ending anywhere in the last column.

A brute-force search over paths is hopeless because the number of possibilities explodes.

Step 2: Dynamic programming by columns

The key insight is:

Since movement is never left, the path progresses monotonically from left to right.

Suppose we already know the minimum cost to reach every cell in column $c-1$. We want the minimum cost for column $c$.

Let:

$$dp[r]$$

denote the minimum cost to reach row $r$ of the current column.

If only right moves were allowed:

$$dp[r] = \text{prev}[r] + M[r][c]$$

But we may also move up/down within the column after entering it.

So for each column:

Initial right move:

$$dp[r] = \text{prev}[r] + M[r][c]$$ 2. Relax downward moves:

If we can come from row $r-1$:

$$dp[r] = \min(dp[r],, dp[r-1] + M[r][c])$$

Relax upward moves:

If we can come from row $r+1$:

$$dp[r] = \min(dp[r],, dp[r+1] + M[r][c])$$

Why does this work?

A minimal path entering a column can wiggle vertically any number of times, but because all costs are positive, an optimal path inside one column is simply a monotone vertical segment (only upward or only downward after entry). Therefore:

one downward sweep,
one upward sweep

is sufficient to propagate all optimal values.

This gives an algorithm of complexity:

$$O(n^2)$$

for an $n\times n$ matrix.

For $n=80$, this is extremely fast.

2. Python implementation

def minimal_path_sum(matrix):
    n = len(matrix)

    # Base case:
    # cost to reach left column is just the cell itself
    dp = [matrix[r][0] for r in range(n)]

    # Process one column at a time
    for c in range(1, n):

        # Step 1: move right into this column
        new_dp = [dp[r] + matrix[r][c] for r in range(n)]

        # Step 2: relax downward paths
        for r in range(1, n):
            new_dp[r] = min(
                new_dp[r],
                new_dp[r - 1] + matrix[r][c]
            )

        # Step 3: relax upward paths
        for r in range(n - 2, -1, -1):
            new_dp[r] = min(
                new_dp[r],
                new_dp[r + 1] + matrix[r][c]
            )

        dp = new_dp

    # End in any row of the rightmost column
    return min(dp)

# Read the matrix file
with open("0082_matrix.txt") as f:
    matrix = [
        list(map(int, line.strip().split(",")))
        for line in f
    ]

answer = minimal_path_sum(matrix)
print(answer)

3. Code walkthrough

Initialization

dp = [matrix[r][0] for r in range(n)]

Since we may start anywhere in the left column, the minimum cost to reach row $r$ of column $0$ is simply the cell’s own value.

Entering a new column

new_dp = [dp[r] + matrix[r][c] for r in range(n)]

This assumes we moved directly right.

Downward relaxation

for r in range(1, n):
    new_dp[r] = min(
        new_dp[r],
        new_dp[r - 1] + matrix[r][c]
    )

We check whether reaching row $r$ from the row above is cheaper.

Upward relaxation

for r in range(n - 2, -1, -1):
    new_dp[r] = min(
        new_dp[r],
        new_dp[r + 1] + matrix[r][c]
    )

We then allow movement upward inside the column.

Final result

return min(dp)

We may finish in any row of the rightmost column, so take the minimum.

Verification on the $5\times5$ example

Running the algorithm on the sample matrix gives:

$$994$$

which matches the problem statement exactly.

4. Final verification

Result is positive, as all matrix entries are positive.
Magnitude is reasonable for an $80\times80$ matrix with values typically in the hundreds.
The dynamic programming method is the standard optimal solution for this constrained shortest-path problem.
The computed Project Euler value is known and consistent.

Answer: 260324