Path Sum: Three Ways

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{red}{234} & \color{red}{103} & \color{red}{18}\\
\color{red}{201} & \color{red}{96} & \color{red}{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.

To find the minimal path sum from the left column to the right column in the given matrix, we can use a dynamic programming approach. We’ll start from the first column and calculate the minimal path sum for each cell in the matrix by considering the minimum of the adjacent cells from the previous column.

Here’s one way to solve the problem using Python code:

“`python
import numpy as np

def minimal_path_sum(matrix):
rows, cols = matrix.shape
dp = np.zeros((rows, cols))

# Initialize the first column of dp with the values from the matrix
dp[:, 0] = matrix[:, 0]

# Calculate the minimal path sum for each cell in dp
for j in range(1, cols):
# Calculate the minimal path sum for each cell in column j
for i in range(rows):
# Calculate the minimal path sum for the current cell
dp[i, j] = matrix[i, j] + min(
dp[i, j-1], # Left
dp[(i-1)%rows, j-1], # Up (wrap around for top row)
dp[(i+1)%rows, j-1] # Down (wrap around for bottom row)
)

# Find the minimum path sum in the last column
min_sum = np.min(dp[:, -1])

return min_sum

# Read the matrix from the file
matrix = np.genfromtxt(‘matrix.txt’, delimiter=’,’)

# Call the function to find the minimal path sum
min_path_sum = minimal_path_sum(matrix)

print(“Minimal path sum:”, min_path_sum)
“`

Make sure you have the `numpy` library installed in order to run this code. The code reads the matrix from the given file, calculates the minimal path sum using the `minimal_path_sum` function, and finally prints the result.

Note: The code assumes that the matrix in the file is a comma-separated values (CSV) file with no spaces between the values.

More Answers: