AoC 2024 Day 16

aoc-2024-day-16.js

import { pipe } from "@/lib/utils.js";
import { MinHeap } from "@/lib/heaps.js";

// prettier-ignore
const DIR = [ [1, 0], [0, 1], [-1, 0], [0, -1] ].map(([dy, dx]) => (dy << 16) | (dx << 2));

const parse = input =>
  input.split("\n").map(row => [...row]);

const shortestPath = map => {
  const sy = map.findIndex(row => row.includes("S"));
  const sx = map[sy].indexOf("S");
  const visited = new Map();
  const queue = [[0, [(sy << 16) | (sx << 2) | 1]]];
  const tiles = [];
  let min = Infinity;
  while (queue.length) {
    const [cost, path] = MinHeap.pop(queue);
    const pos = path.at(-1);
    if (
      map[pos >> 16][(pos & 0xffff) >> 2] === "E" &&
      min >= cost
    ) {
      min = cost;
      tiles.push(...path.map(p => p >> 2));
    }
    [-1, 0, 1]
      .map(dh => [
        (4 + dh + (pos & 3)) % 4,
        1 + 1000 * Math.abs(dh),
      ])
      .map(([h, dc]) => [
        (pos & ~0x03) + DIR[h] + h,
        cost + dc,
      ])
      .filter(
        ([p, c]) =>
          map[p >> 16][(p & 0xffff) >> 2] !== "#" &&
          !(visited.get(p) < c) &&
          visited.set(p, c)
      )
      .forEach(([p, c]) =>
        MinHeap.push(queue, [c, [...path, p]])
      );
  }
  return [min, new Set(tiles).size];
};
export const part1 = pipe(parse, shortestPath, v => v[0]);
export const part2 = pipe(parse, shortestPath, v => v[1]);