Module aoc::year2021::day23

Amphipod

Our high level approach is an A* search over all possible burrow states. Three techniques are used to speed things up.

Firstly a good choice of heuristic is crucial. The heuristic used has the following characteristics:

• Exactly correct for optimal moves.
• Cheap to update on each subsequent move.

Secondly pruning states to reduce the search space is very beneficial. Two approaches are used:

• A cache of previously seen states. If amphipods are in the same position but with a higher cost then the current state will never be optimal and can be pruned.
• Detecting deadlocked states where an amphipod in the hallway prevents any possible solution. Exploring any further is a waste of time.

Thirdly low level bit manipulation is used to represent the burrow state size compactly in only 16 bytes for faster copying and hashing.

Structs

• Burrow 🔒
  Combine hallway and four rooms into a complete burrow representation in only 8 + 4 * 2 = 16 bytes.
• Hallway 🔒
  Pack the state of the hallway into a usize. Each hallway position is represented by a nibble with the pod type (plus additionally empty or room entrance markers) for a total of 44 bits.
• Room 🔒
  Pack the room state into only 2 bytes.

Constants

• A 🔒
  The values of A, B, C and D are used heavily to calculate room indices.
• B 🔒
• C 🔒
• COST 🔒
• D 🔒
• EMPTY 🔒
• ROOM 🔒

Functions

• best_possible 🔒
  Heuristic of the lowest possible energy to organize the burrow. Assumes that amphipods can move through the hallway unblocked.
• condense 🔒
  Starting from a burrow of a specific kind, searches the hallway and other rooms from either left or right direction, returning all amphipods of that kind to the burrow. Stops searching immediately if blocked.
• deadlock_left 🔒
  Checks for a situation where an A amphipod can block other amphipods in the leftmost burrow.
• deadlock_right 🔒
  Mirror image situation to deadlock_left where a D amphipod could block others.
• deadlock_room 🔒
  Detects situation where amphipods in the hallway need to move past each other but mutually block any further progress.
• expand 🔒
  Searches the hallway in either the right or left direction, pushing a new state to the priority queue if it’s possible to place an amphipod there.
• organize 🔒
  A* search over all possible burrow states until we find the lowest cost to organize.
• parse
  Subtracts the ASCII value of A from each character of the input so that amphipod values match the constants defined above.
• part1
  Part one is a special case of the full burrow where two amphipods of each type are already in the correct position in each room.
• part2
  Part two adds the middle amphipods as specified in the problem statement.