AoC 2021 D23: Amphipod

| Problem statement | Source code | Tags: Dijkstra

While this problem doesn't look graph-y on the surface, essentially we have a state space and a set of transitions between states with associated costs, so we can use Dijkstra's to find the minimum-cost path from the initial state to the goal state.

The first tricky part might be parsing the input. I represented the state as { rooms: number[][], hallway: (number | undefined)[] }, where rooms[i] is the stack of amphipods in room i (rooms[i][0] is the one closest to the hallway), and hallway[j] is the amphipod (or undefined if empty) at hallway position j. Amphipods are represented as numbers 0-3.

I already have template code from day 15, which translates directly:

function move(
  startRooms: number[][],
  startHallway: (number | undefined)[],
  roomSize: number,
) {
  const costs = new Map<string, number>();
  costs.set(serialize(startRooms, startHallway), 0);
  const pq = new MinPriorityQueue<State>();
  pq.enqueue({ rooms: startRooms, hallway: startHallway }, 0);

  while (!pq.isEmpty()) {
    const {
      priority: energy,
      element: { rooms, hallway },
    } = pq.dequeue() as PriorityQueueItem<State>;

    // Every room is good
    if (
      rooms.every(
        (room, i) => room.length === roomSize && room.every((pod) => pod === i),
      )
    ) {
      return energy;
    }

    for (const { rooms: newRooms, hallway: newHallway, cost } of nextStates(
      rooms,
      hallway,
      roomSize,
    )) {
      const newEnergy = energy + cost;
      const serialized = serialize(newRooms, newHallway);
      if (!costs.has(serialized) || newEnergy < costs.get(serialized)!) {
        costs.set(serialized, newEnergy);
        pq.enqueue({ rooms: newRooms, hallway: newHallway }, newEnergy);
      }
    }
  }
  throw new Error("No solution found");
}

The rest is a matter of implementing the transition function, nextStates(). There are two types of moves: moving an amphipod from a room to the hallway, and moving an amphipod from the hallway to a room.

To move an amphipod from a room to the hallway, we iterate through the rooms. If the room is empty or already good (i.e., contains only amphipods of the correct type), we skip it. Otherwise, we take the top amphipod, and enumerate all hallway positions it can move to (i.e., all positions to the left and right until we hit a wall or another amphipod, and skip positions right outside rooms). The distance is the horizontal distance plus the vertical distance to get out of the room.

for (let i = 0; i < rooms.length; i++) {
  const room = rooms[i];

  // Empty or already good
  if (
    room.length === 0 ||
    (room.length === roomSize && room.every((p) => p === i))
  )
    continue;

  const toMove = room[0];
  const startingX = 2 + i * 2;
  // Cost to enter the hallway
  const baseCost = (roomSize + 1 - room.length) * 10 ** toMove;
  let leftMost = startingX - 1;
  while (leftMost >= 0 && hallway[leftMost] === undefined) leftMost--;

  for (
    let j = leftMost + 1;
    j < hallway.length && hallway[j] === undefined;
    j++
  ) {
    // Directly in front of a room
    if ([2, 4, 6, 8].includes(j)) continue;

    const newRooms = [...rooms];
    newRooms[i] = room.slice(1);
    const newHallway = [...hallway];
    newHallway[j] = toMove;
    yield {
      rooms: newRooms,
      hallway: newHallway,
      cost: Math.abs(startingX - j) * 10 ** toMove + baseCost,
    };
  }
}

To move an amphipod from the hallway to a room, we iterate through pods in the hallway. If the pod cannot move to the target room because its path is blocked or the room contains incorrect amphipods, we skip it. Otherwise, we compute the distance and create the new state.

for (let i = 0; i < hallway.length; i++) {
  const pod = hallway[i];
  if (pod === undefined) continue;
  const targetX = 2 + pod * 2;
  // Blocked
  if (
    (targetX < i && hallway.slice(targetX, i).some((p) => p !== undefined)) ||
    (targetX > i &&
      hallway.slice(i + 1, targetX + 1).some((p) => p !== undefined))
  )
    continue;

  const room = rooms[pod];
  if (room.some((p) => p !== pod)) continue;

  const newRooms = [...rooms];
  newRooms[pod] = [pod, ...room];
  const newHallway = [...hallway];
  newHallway[i] = undefined;
  yield {
    rooms: newRooms,
    hallway: newHallway,
    cost: (Math.abs(i - targetX) + (roomSize - room.length)) * 10 ** pod,
  };
}

Part 2 just requires changing the initial rooms to insert the extra amphipods.

← Previous Back to AoC Index Next →