advent-code-2021-day-15.js

const input = `
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
`;

function run() {
  let matrix = input
    .split("\n")
    .filter(Boolean)
    .map((r) => r.split("").map(Number));

  let [h, w] = [matrix.length, matrix[0].length];

  let osize = h;

  h = h * 5;
  w = w * 5;

  function getNum(index) {
    let x = index % w;
    let y = Math.floor(index / w);

    let origin = matrix[y % osize][x % osize];
    let multiplier = Math.floor(y / osize) + Math.floor(x / osize);

    return ((origin + multiplier - 1) % 9) + 1;
  }

  // Dijkstra
  function lowestPath() {
    const costMap = new Map();
    let curr = 0;
    let pQueue = [];
    let visited = new Set();
    visited.add(curr);
    costMap.set(curr, 0);

    function cost(index) {
      return costMap.has(index) ? costMap.get(index) : Number.MAX_SAFE_INTEGER;
    }

    while (visited.size < h * w) {
      let [x, y] = [curr % w, Math.floor(curr / w)];
      let neighbors = [
        [x - 1, y],
        [x + 1, y],
        [x, y - 1],
        [x, y + 1],
      ];

      for (let [nx, ny] of neighbors) {
        if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
        let nindex = ny * w + nx;
        let c = cost(curr) + getNum(nindex);
        if (c < cost(nindex)) {
          costMap.set(nindex, c);
          pQueue.push([nindex, c]);
          pQueue.sort((a, b) => a[1] - b[1]);
        }
      }

      curr = pQueue.shift()[0];
      if (!curr) {
        break;
      }
      visited.add(curr);
    }

    return costMap.get(h * w - 1);
  }

  console.log(lowestPath());
}

run();