Question

In the 5 by 5 matrix below, 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.

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

JavaScript

const fs = require("fs")

function parseMatrix(matrix) {
  return matrix.toString().trim().split("\n").map((line) => {
    return line.split(",").map((c) => parseInt(c))
  })
}

function bfs(graph, root, target) {
  function neighbors([x, y]) {
    const candidates = [
      [x + 1, y],
      [x, y + 1]
    ]
    return candidates.filter(([x, y]) => {
      return x >= 0 && x < graph[0].length && y >= 0 && y < graph.length
    })
  }

  function evaluate(path) {
    return path.reduce((acc, [x, y]) => acc + graph[y][x], 0)
  }

  const start = [root]
  const frontier = [[evaluate(start), start]]
  const explored = new Set()
  while (frontier.length > 0) {
    let path = null
    let min = Infinity
    let index = -1
    frontier.forEach(([score, candidate], i) => {
      if (score < min) {
        min = score
        path = candidate
        index = i
      }
    })
    frontier.splice(index, 1)
    const node = path[path.length - 1]
    explored.add(node.toString())
    if (node.toString() === target.toString()) {
      return min
    }
    neighbors(node).forEach((neighbor) => {
      if (!explored.has(neighbor.toString())) {
        const newPath = path.slice()
        newPath.push(neighbor)
        frontier.push([evaluate(newPath), newPath])
      }
    })
  }
}

const graph = parseMatrix(fs.readFileSync(__dirname + "/matrix.txt"))
console.log(bfs(graph, [0, 0], [graph[0].length - 1, graph.length - 1]))

$ time node --use-strict path-sum.js
real   0m0.496s
user   0m0.646s
sys    0m0.000s

Python

#!/usr/bin/env python
import os
import sys
from collections import defaultdict

def dijkstra(matrix):
    def neighbors(node):
        (x, y) = node
        n = []
        if x < len(matrix[0]) - 1:
            n.append((x + 1, y))
        if y < len(matrix) - 1:
            n.append((x, y + 1))
        return n

    def value(node):
        (x, y) = node
        return matrix[y][x]
    
    current = (0, 0)
    dest = (len(matrix[0]) - 1, len(matrix) - 1)
    unvisited = set((x, y) for x in range(dest[0] + 1) for y in range(dest[1] + 1))
    nodes = {}
    for node in unvisited: nodes[node] = sys.maxsize
    nodes[current] = value(current)

    while 1:
        for node in [n for n in neighbors(current) if n in unvisited]:
            distance = nodes[current] + value(node)
            if distance < nodes[node]:
                nodes[node] = distance

        unvisited.remove(current)
        if current == dest:
            break
        else:
            current = min((nodes[node], node) for node in unvisited)[1]

    return nodes[dest]

def main():
    matrix = []
    with open(os.path.join(os.path.dirname(__file__), "matrix.txt")) as matfile:
        for row in matfile:
            matrix.append([int(n) for n in row.split(',')])

    print(dijkstra(matrix))

if __name__ == "__main__": main()

$ time python3 minimal_path.py
real   0m4.587s
user   0m4.586s
sys    0m0.000s