Module advent_of_code_2021::day_23 [−][src]
Expand description
This is my solution for Advent of Code - Day 23 - Amphipod
This one I really struggled with. Almost entirely due to me misreading the puzzle description, and missing the restrictions on Amphipod movement that vastly restrict the graph of moves. It took eventually despairing, looking up others’ solutions, seeing a bunch of things that seemed weird, and going back to work out why. By this point I’d rewritten my state representation as an integer of upto 23 3-bit sections from which I could unpack the state, so that I could more efficiently store the states in a Binary Heap. I was able to shoe-horn in the restrictions to my existing code, but that journey has left it pretty unreadable. I have left it as is, and will try to make it clearer what is going on with some comments. It is worth noting that my initial, less restricted solution still worked for part one, though it did take about 6 minutes to complete.
Burrow is the previously mentioned state-as-integer, which contains the state, and the length for ease of
determining how many leading 0’s are significant. Burrow::from is used for creating burrows from a string in
tests. Burrow::fmt turns the integer into a string of letters so debugging is possible. Burrow::get_at does
some bit-manipulation to get the Amphipod type, if any, at that position. Burrow::set_at uses more bit tricks to
mutate the state of one of the positions and Burrow::swap uses these to swap the state between two positions, used
to move Amphipods. State wraps a Burrow with a cost to enable using Dijkstra’s algorithm to solve the puzzle
with a graph search. crate::day_15 has a cleaner implementation of this. Note Burrow::cmp is manually
implemented to reverse the ordering, so that Rust’s default BinaryHeap, which is a max-heap, works as the
required min-heap instead
parse_letter turns an ., A, B, C, or D into a number 0-4 to represent the possible state for each
cell. parse_input parses the ascii diagram of the burrow, mostly by ignoring every thing that isn’t A, B,
C, or D. build_goal builds the burrow representing the expected final state of the burrow for a given depth
of side-tunnels. build_states returns a list of possible states, and the cost to move there from the given
state. This is where the worst of the mess is, as it relies on a lot of number manipulation tricks to turn the flat
15/23 cell list of cells into something that represents the more complex burrow structure. find_shortest_path is
just implementing Dijkstra’s Algorithm and is very similar to crate::day_15’s version, but with a different
adjacency/cost implementation. Finally expand_burrow handles turning the input for part one into the input for
part two.
Structs
Represents a burrow as an integer that can be used as a list of 3-bit sections. 0-6 are the 7 cells in the hallway
where a Amphipod can stop, the cells adjacent to each side tunnel are not represented here, and instead handled by
build_states accounting for them when calculating costs. The remaining cells represent the side-tunnels, reading
like a book. You can walk down a tunnel by staring at indices 7, 8, 9 or 10, and increasing by 4 each step. It is
possible to represent a burrow of up to depth 8 in the u128 used.
Wrapper for a Burrow state with the cost to reach that state. Implements Ord in reverse order so that we can use
Rust’s built in max-BinaryHeap as a min-heap.
Constants
The cost to move each type of Amphipod in order A-D
Functions
Return a burrow that represents the target state for a given depth.
This handles building the possible next states respecting the limits on Amphipod movement returning a list of the possible states and the cost for each.
Add in the two extra lines that were hidden behind the fold for part two.
Use Dijkstra’s algorithm to represent the puzzle as a graph of states, and find the shortest path (i.e. lowest total move energy) for the Amphipods to all reach their desired tunnel.
Parse the ascii-art diagram into the internal representation.
Turn a letter in the ascii-art into the number we use to represent it internally
The entry point for running the solutions with the ‘real’ puzzle input.