#81 Path sum: two ways

In the 5 by 5 matrix above, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

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

Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt, a 31K text file containing an 80 by 80 matrix.

---

The final destination is the bottom right.

\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}

I have two choices to reach 331. One is from 37 (moving right) and another from 956 (moving down). There is only one choice to reach the goal from those numbers. Why don't I take into account the last number in advance then? In this way, I can regard 37 as 368 and 956 as 1287. Now I can tell, from 121, that taking down-path leads to minimal summation.

 

What I have to do is repeat this process to the top left.

import numpy as np
import matplotlib.pyplot as plt

with open("p081_matrix.txt", "r") as f:
    matrix = np.array([x.strip("\n").split(",") for x in f.readlines()]).astype(
        np.int64
    )

fig, ax = plt.subplots(figsize=(8, 8))
cmap = "viridis"

ax.pcolor(matrix, cmap=cmap)
ax.set_xticks(np.arange(4.5, 80, 5))
ax.set_xticklabels(np.arange(5, 81, 5))
ax.set_yticks(np.arange(4.5, 80, 5))
ax.set_yticklabels(np.arange(5, 81, 5))
ax.tick_params(axis="y", which="major", pad=8)
ax.xaxis.tick_top()
ax.tick_params(length=0)

plt.gca().invert_yaxis()
plt.show()

Visualized matrix. The brighter is the bigger.

l = len(matrix) - 1
for i in range(l):
    matrix[l][l - i - 1] += matrix[l][l - i]
    matrix[l - i - 1][l] += matrix[l - i][l]
for i in range(l):
    for j in range(l):
        matrix[l - i - 1][l - j - 1] += min(
            matrix[l - i][l - j - 1], matrix[l - i - 1][l - j]
        )
        
print(matrix[0][0])

 

The answer is 427337.