volver

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$.

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.

Solución

Implementamos Dijkstra para que el grafo en el que se tengan que encontrar los caminos mas cortos vengan dados por la matriz y los tres caminos posibles (ARRIBA, DERECHA y ABAJO).

Una vez tenemos el algoritmo que calcula los costes de llegar a cada celda de la matriz $80\times 80$, nos quedamos con el valor mínimo de la última columna (nos da igual donde acabar).

Repetimos el proceso seleccionando como nodo inicial todos los elementos de la primera columna, nos quedamos de nuevo con el mínimo para el conjunto de los 80 puntos de partida.

import numpy as np

with open('0082_matrix.txt') as f:
    data = np.array([[int(y) for y in x.split(',')] for x in f.read().strip().split('\n')])

M = np.array([
    [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]
])

def distances(cost_matrix, curr_row=0, curr_col=0):
    distances = np.full_like(cost_matrix, np.inf, dtype=np.float64)
    visited = np.full_like(cost_matrix, False, dtype=np.bool)

    distances[curr_row, curr_col]=cost_matrix[curr_row, curr_col]
    while np.max(distances)==np.inf:
        # buscamos el nodo con el menor coste, en la primera iteracion es el de la casilla inicial
        row, col = np.unravel_index(np.argmin(np.where(visited, np.inf, distances)), visited.shape)

        # accesible edges
        if row>0:
            if distances[row, col] + cost_matrix[row-1, col] < distances[row-1, col]:
                distances[row-1, col] = distances[row, col] + cost_matrix[row-1, col]
        if row<visited.shape[0]-1:
            if distances[row, col] + cost_matrix[row+1, col] < distances[row+1, col]:
                distances[row+1, col] = distances[row, col] + cost_matrix[row+1, col]
        if col<visited.shape[1]-1:
            if distances[row, col] + cost_matrix[row, col+1] < distances[row, col+1]:
                distances[row, col+1] = distances[row, col] + cost_matrix[row, col+1]
            
        visited[row, col] = True

    return distances

# resolvemos

dist = []
for initial_row in range(data.shape[0]):
    res = distances(data, curr_row=initial_row, curr_col=0)
    dist.append(res[:,-1])
print(np.min(dist)) # el resultado del problema

dist = []
for initial_row in range(M.shape[0]):
    res = distances(M, curr_row=initial_row, curr_col=0)
    dist.append(res[:,-1])
print(np.min(dist)) # el resultado del ejemplo, 994.