Untitled

mail@pastecode.io avatar
unknown
javascript
7 months ago
2.7 kB
3
Indexable
Never
const factoryMap = `2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533`
  .split(/\n/)
  .map((line) => line.split("").map((heatLoss) => parseInt(heatLoss)));

function calculateOptimalPath(map, isUltraCrucible) {
  const navigationQueue = [[0, 0, 0, 0, 0, 0]];
  const visitedPaths = new Set();

  while (navigationQueue.length) {
    const [heatLoss, row, column, dirRow, dirCol, steps] = navigationQueue
      .sort(([prevLoss], [nextLoss]) => nextLoss - prevLoss)
      .pop();

    if (
      row === map.length - 1 &&
      column === map[0].length - 1 &&
      (isUltraCrucible ? steps >= 4 : true)
    ) {
      return heatLoss;
    }

    const pathKey = [row, column, dirRow, dirCol, steps].toString();
    if (visitedPaths.has(pathKey)) continue;
    visitedPaths.add(pathKey);

    if (
      steps < (isUltraCrucible ? 10 : 3) &&
      [dirRow, dirCol].toString() !== "0,0"
    ) {
      const nextRow = row + dirRow;
      const nextColumn = column + dirCol;
      if (
        0 <= nextRow &&
        nextRow < map.length &&
        0 <= nextColumn &&
        nextColumn < map[0].length
      ) {
        navigationQueue.push([
          heatLoss + map[nextRow][nextColumn],
          nextRow,
          nextColumn,
          dirRow,
          dirCol,
          steps + 1,
        ]);
      }
    }

    if (
      isUltraCrucible
        ? steps >= 4 || [dirRow, dirCol].toString() === "0,0"
        : true
    ) {
      for (const [nextDirRow, nextDirCol] of [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
      ]) {
        if (
          [nextDirRow, nextDirCol].toString() !== [dirRow, dirCol].toString() &&
          [nextDirRow, nextDirCol].toString() !== [-dirRow, -dirCol].toString()
        ) {
          const nextRow = row + nextDirRow;
          const nextColumn = column + nextDirCol;
          if (
            0 <= nextRow &&
            nextRow < map.length &&
            0 <= nextColumn &&
            nextColumn < map[0].length
          ) {
            navigationQueue.push([
              heatLoss + map[nextRow][nextColumn],
              nextRow,
              nextColumn,
              nextDirRow,
              nextDirCol,
              1,
            ]);
          }
        }
      }
    }
  }
}

for (const part of [1, 2]) {
  const isUltraCrucible = part === 2;
  console.log(
    `Part ${part}:`,
    calculateOptimalPath(factoryMap, isUltraCrucible)
  );
}
Leave a Comment