AoC 2022 Day 16

aoc_2022_day16.js

import { pipe, memo } from "../../lib/utils.js";

const RE = /Valve (..) has flow rate=(\d+); tunnels? leads? to valves? (.*)/;

const parse = input =>
  input
    .split("\n")
    .map(line => RE.exec(line))
    .map(([, v, r, vs]) => [v, Number(r), vs.split(", ")])
    .sort(([a], [b]) => a.localeCompare(b))
    .map(([v, r, vs], i, arr) => [
      1n << BigInt(i),
      [
        r,
        vs.map(
          v => 1n << BigInt(arr.findIndex(([o]) => v === o))
        ),
        v,
      ],
    ]);

const shortestPath = graph => {
  const keys = [...graph.keys()];
  const map = new Map(
    keys.flatMap(k =>
      keys.map(l => [k | l, l === k ? 0 : Infinity])
    )
  );
  keys.forEach(u =>
    graph.get(u).forEach(v => map.set(u | v, 1))
  );
  keys.forEach(k =>
    keys.forEach(i =>
      keys.forEach(j =>
        map.set(
          i | j,
          Math.min(
            map.get(i | j),
            map.get(i | k) + map.get(k | j)
          )
        )
      )
    )
  );
  return map;
};

const evaluate = (time, agents = 1) => data => {
  const dist = shortestPath(
    new Map(data.map(([key, data]) => [key, data[1]]))
  );
  const flow = new Map(data.map(([k, [v]]) => [k, v]));
  const keys = data
    .map(([k]) => k)
    .filter(k => flow.get(k));
  const keysPerAgent = Math.trunc(keys.length / agents) - 1;

  const dfs = memo(
    (valve, minutes, open, agent, opened = 0) =>
      keys
        .filter(
          k =>
            !(open & k) && dist.get(valve | k) + 1 < minutes
        )
        .map(k => {
          const minLeft = minutes - dist.get(valve | k) - 1;
          return (
            minLeft * flow.get(k) +
            (minLeft > 2
              ? dfs(k, minLeft, open | k, agent, opened + 1)
              : 0)
          );
        })
        .reduce(
          (max, v) => (max > v ? max : v),
          (agent > 1 &&
            opened >= keysPerAgent &&
            dfs(1n, time, open, agent - 1, 0)) ||
            0
        ),
    {
      serializer: args => args.join(),
    }
  );
  return dfs(1n, time, 0n, agents);
};

export const part1 = pipe(parse, evaluate(30));
export const part2 = pipe(parse, evaluate(26, 2));