AoC 2023 Day 17

aoc-2023-day-17.js

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

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

// prettier-ignore
const DIR = [[0, -1], [1, 0], [0, 1], [-1, 0]];
const [E, S] = [1, 2];

const BFS = condition => grid => {
  const visited = new Map();
  const [tx, ty] = [grid[0].length - 1, grid.length - 1];
  const queue = [
    [0, 0, [0, 0], E, 0],
    [0, 0, [0, 0], S, 0],
  ];
  while (queue.length) {
    const [, energy, [cx, cy], ch, cs] = MinHeap.pop(queue);
    if (cx === tx && cy === ty && condition(cs, cs)) {
      return energy;
    }
    DIR.map((d, h) => [d, h, h === ch ? cs + 1 : 1])
      .map(([[dx, dy], ...rest]) => [
        [cx + dx, cy + dy],
        ...rest,
      ])
      .filter(
        ([[x, y], h]) => grid[y]?.[x] && (h + 2) % 4 !== ch
      )
      .filter(([, , steps]) => condition(cs, steps))
      .map(([[x, y], h, steps]) => [
        energy + grid[y][x],
        [x, y],
        h,
        steps,
      ])
      .filter(
        ([e, [x, y], h, steps]) =>
          (visited.get(
            (y << 16) | (x << 8) | (h << 4) | steps
          ) ?? Infinity) > e &&
          visited.set(
            (y << 16) | (x << 8) | (h << 4) | steps,
            e
          )
      )
      .forEach(([e, p, h, steps]) =>
        MinHeap.push(queue, [
          e + (tx - p[0]) + (ty - p[1]),
          e,
          p,
          h,
          steps,
        ])
      );
  }
  return -1;
};

export const part1 = pipe(
  parse,
  BFS((_, steps) => steps < 4)
);

export const part2 = pipe(
  parse,
  BFS(
    (prevSteps, steps) =>
      (steps > prevSteps || prevSteps >= 4) && steps < 11
  )
);

prio queue used:

// From https://stackoverflow.com/a/66511107/4235871
// prettier-ignore
export const MinHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]>h[j+1][0])j++;if(j>=h.length||k<=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k<h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};

👏 👏 👏