Project Euler Problem 81

Solution

Answer: 427337

1. Mathematical analysis

We are given an $80\times 80$ matrix and must find the minimum path sum from the top-left corner to the bottom-right corner, moving only right or down.

This is a classic dynamic programming problem.

Key observation

At any cell $(i,j)$, the path could only have arrived from:

the cell above: $(i-1,j)$
the cell to the left: $(i,j-1)$

Since movement is restricted to right and down, there are no cycles and every optimal path to $(i,j)$ must contain optimal subpaths.

Let:

$$dp[i][j]$$

be the minimal path sum to reach cell $(i,j)$.

Then:

$$dp[i][j] = \text{matrix}[i][j] + \min(dp[i-1][j],,dp[i][j-1])$$

This recurrence follows from the principle of optimality:

If the best path reaches $(i,j)$, then the path immediately before $(i,j)$ must itself be optimal.

Boundary conditions

For the first row:

Only rightward movement is possible:

$$dp[0][j] = dp[0][j-1] + \text{matrix}[0][j]$$

For the first column:

Only downward movement is possible:

$$dp[i][0] = dp[i-1][0] + \text{matrix}[i][0]$$

Starting point:

$$dp[0][0] = \text{matrix}[0][0]$$

Small example verification

For the $5\times5$ example:

$$\begin{pmatrix} 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 \end{pmatrix}$$

Dynamic programming builds the minimum totals row by row:

$$\begin{pmatrix} 131 & 804 & 1038 & 1141 & 1159\ 332 & 428 & 770 & 1735 & 1309\ 962 & 1231 & 1516 & 1938 & 1420\ 1499 & 1930 & 2013 & 2059 & 2376\ 2304 & 2662 & 2537 & 2096 & 2427 \end{pmatrix}$$

The bottom-right value is:

$$2427$$

which matches the problem statement.

2. Python implementation

def minimal_path_sum(filename):
    # Read the matrix from file
    with open(filename, "r") as f:
        matrix = [
            list(map(int, line.strip().split(",")))
            for line in f
        ]

    n = len(matrix)
    m = len(matrix[0])

    # DP table
    dp = [[0] * m for _ in range(n)]

    # Starting cell
    dp[0][0] = matrix[0][0]

    # Fill first row
    for j in range(1, m):
        dp[0][j] = dp[0][j - 1] + matrix[0][j]

    # Fill first column
    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + matrix[i][0]

    # Fill remaining cells
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = matrix[i][j] + min(
                dp[i - 1][j],   # from above
                dp[i][j - 1]    # from left
            )

    return dp[-1][-1]

answer = minimal_path_sum("matrix.txt")
print(answer)

3. Code walkthrough

Reading the matrix

matrix = [
    list(map(int, line.strip().split(",")))
    for line in f
]

Each line of the file contains comma-separated integers.

We convert every row into a list of integers, producing an $80\times80$ matrix.

Creating the DP table

dp = [[0] * m for _ in range(n)]

dp[i][j] stores the minimal path sum to cell $(i,j)$.

Initial cell

dp[0][0] = matrix[0][0]

The path begins at the top-left corner.

First row

for j in range(1, m):
    dp[0][j] = dp[0][j - 1] + matrix[0][j]

Since we can only move right, each value accumulates from the left.

First column

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

Since we can only move down, each value accumulates from above.

Remaining cells

dp[i][j] = matrix[i][j] + min(
    dp[i - 1][j],
    dp[i][j - 1]
)

Choose the cheaper predecessor (above or left).

This runs in:

$$O(nm)$$

For an $80\times80$ grid:

$$80^2 = 6400$$

operations — extremely fast.

4. Final verification

The recurrence is mathematically correct by optimal substructure.
The sample matrix reproduces the stated result $2427$.
The algorithm is deterministic and exhaustive under the movement constraints (right/down only).
Applying it to the official $80\times80$ matrix yields:

Answer: 427337