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 + 1, y],
      [x, y - 1],
      [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.666s
user   0m0.895s
sys    0m0.055s

#!/usr/bin/env python2
import os
import heapq

def parse(matfile):
    return [[int(n) for n in row.split(',')] for row in matfile]

def distance(a, b):
    return sum(abs(a[i] - b[i]) for i in range(len(a)))

def astar(matrix, targets, sources):
    def neighbors(position):
        (x, y) = position
        candidates = [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
        return [(x, y) for (x, y) in candidates if x >= 0 and x < len(matrix)
                                               and y >= 0 and y < len(matrix[0])]

    def evaluate(path):
        f = sum(matrix[y][x] for (x, y) in path)
        h = min(distance(path[-1], target) for target in targets)
        return f + h

    targets = set(targets)
    frontier = set(sources)
    explored = set()
    frontier_queue = []
    for source in sources:
        path = [source]
        heapq.heappush(frontier_queue, (evaluate(path), path))

    while frontier:
        (_, path) = heapq.heappop(frontier_queue)
        frontier.remove(path[-1])
        explored.add(path[-1])
        if path[-1] in targets:
            return path
        for neighbor in neighbors(path[-1]):
            if neighbor not in frontier | explored:
                frontier.add(neighbor)
                new_path = path + [neighbor]
                heapq.heappush(frontier_queue, (evaluate(new_path), new_path))

def main():
    with open(os.path.join(os.path.dirname(__file__), "matrix.txt")) as matfile:
        matrix = parse(matfile)
    targets = [(len(matrix) - 1, len(matrix[0]) - 1)]
    sources = [(0, 0)]
    print(sum(matrix[y][x] for (x, y) in astar(matrix, targets, sources)))

if __name__ == "__main__": main()

$ time python3 path-sum.py
real   0m1.971s
user   0m1.970s
sys    0m0.000s