Module 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.