Advent of Code 2021 - Day 23

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 23 - Amphipod

Find the problem description HERE.

The Input - Swipe Left

This time around, I’ve skipped parsing the input from the text file, in large part because I ended up re-factoring my solution (and the input data type) several times in an attempt to reduce run times. So, instead of text parsing, I present the data structure(s) I have settled on.

#= Data Structures -------------------------------------------------------------
| These are the data structures used to represent the problem space
=#

# The different kinds of Amphipod
abstract type Amphipod end
struct Amber <: Amphipod end
struct Bronze <: Amphipod end
struct Copper <: Amphipod end
struct Desert <: Amphipod end

const MaybeAmphipod = Union{Nothing,Amphipod}

# A space in the burrow where an Amphipod can be
abstract type Location end
struct Hallway <: Location
    idx::Int64
    occupant::MaybeAmphipod
end
Hallway(idx) = Hallway(idx, nothing)

struct Room{T} <: Location
    amphitype::Type{T}
    idx::Int64
    occupant::MaybeAmphipod
end
Room(T, idx) = Room(T, idx, nothing)

# The burrow is represented by a statically sized Tuple of `Location`s
struct Burrow{N}
    locations::NTuple{N, Location}
end
Burrow(L...) = Burrow(L)

Base.getindex(burrow::Burrow, idx::Int64) = burrow.locations[idx]
Base.isempty(location::Location) = isnothing(location.occupant)
Base.length(burrow::Burrow) = length(burrow.locations)
matches(room::Room) = room.occupant isa room.amphitype

The actual inputs are just constructed in the script as constants like so:

#= Test input burrow state
| #############
| #...........#
| ###B#C#B#D###
| #A#D#C#A#
| #########
=#
const TESTBURROW = Burrow(
    Hallway(1),
    Hallway(2), Hallway(3),
    Room(Amber, 1, Bronze()), Room(Amber, 2, Amber()),
    Hallway(4), Hallway(5),
    Room(Bronze, 1, Copper()), Room(Bronze, 2, Desert()),
    Hallway(6), Hallway(7),
    Room(Copper, 1, Bronze()), Room(Copper, 2, Copper()),
    Hallway(8), Hallway(9),
    Room(Desert, 1, Desert()), Room(Desert, 2, Amber()),
    Hallway(10), Hallway(11)
)

I could have gone back after finally settling on a data type and written code to parse it from the input file, but I don’t wanna!

Solution - One Code to Rule Them All

Since we’re changing things up, and the code I’ll be presenting is the result of several re-factors, I’ll share the final, generalized code that solves both parts. Today’s puzzle has us rearranging amphipods in their burrow, in a very Tower of Hanoi or Rush Hour sort of fashion. Initially, I thought an A* algorithm would be my best bet, but after much fiddling, I couldn’t settle on a heuristic that would actually help on both parts. There were some versions that really helped the test input caused the real input to not converge on a solution (or to take longer to find a solution), and many versions that caused both the test and real inputs to result in answers close to the correct solution, but not quite there. So, no heuristic! And the performance is bad (~10s for both parts on my machine), but I can live with that. Here’s the generalized solving code:

# Shared code between modules Part1 and Part2 ==================================
# Part1 and Part2 are split into modules to help with namespacing 

using DataStructures: BinaryMinHeap

#= Movement Rules --------------------------------------------------------------
| Use the puzzle rules to determine whether or not an amphipod can move from
| one space to another with the following functions...
=#

# Get the index of the hallway space that leads into a `Room`.
doorway(room::Room) = DOORWAYS[typeof(room)]

# Iterate over all the rooms of the same type following the `Room` in `RoomIter`
# Note that every Tuple is already an iterator over its contents, but because
# We're implementing `iterate()` for a _more specific_ type of Tuple, this 
# method will be preferred for iterating over `RoomIter` Tuples.
const RoomIter = Tuple{Room,Burrow}
function Base.iterate(iter::RoomIter, idx::Int = 0)
    (room, burrow) = iter
    doorwayidx = doorway(room)
    roomidx = idx > 0 ? idx : doorwayidx + room.idx + 1
    nextroom = burrow[roomidx]
    nextroom isa typeof(room) || return nothing
    return (nextroom, roomidx + 1)
end

# It is illegal to move from one hallway space to another hallway space
canmove(::Hallway, ::Hallway, ::Burrow) = false

# An amphipod will only leave their room if they do not match the room OR
# they are between the hallway and another amphipod who does not match the room
function canmove(room::Room, ::Hallway, burrow::Burrow) 
    # Can leave the room if the amphipod doesn't match the room type.
    matches(room) || return true

    # Can move from the first space in the room to the hallway if...
    # - the amphipod type does not match the room type (already checked)
    # - an amphipod in a later space does not match the room type
    for nextroom in (room, burrow)
        matches(nextroom) || return true
    end

    # If all the following room spaces are filled with the right kind of
    # amphipod (or `room` is the last space in the Room), then stay put
    return false
end

# There are multiple rules associated with moving from a hallway space into 
# a room...
function canmove(hallway::Hallway, room::Room, burrow::Burrow)
    # Can't move into any of the room spaces if the amphipod type doesn't
    # match the type of room.
    hallway.occupant isa room.amphitype || return false

    # Can move from the hallway into the first `Room` space if...
    # - the amphipod type matches the room type (already checked)
    # - all the later spaces are occupied by an amphipod of the
    # appropriate type
    for nextroom in (room, burrow)
        matches(nextroom) || return false
    end

    # If all the following room spaces are filled with the right kind of
    # amphipod (or `room` is the last space in the Room), then `amphipod` 
    # can move into the room space
    return true
end

# Rules for moving from one room space to another room space
function canmove(room1::Room, room2::Room, burrow::Burrow)
    # Can't move from one space to another in the same room
    typeof(room1) == typeof(room2) && return false

    # In order to move from one room to another, the amphipod must *not* match
    # the room it is in and it *must* match the room it is moving to
    room1.occupant isa room1.amphitype && return false
    room1.occupant isa room2.amphitype || return false

    # Can't move into a room space if any of the following spaces are empty
    # or occupied by the wrong kind of amphipod
    for nextroom in (room2, burrow)
        matches(nextroom) || return false
    end

    return true
end

#= Swapping --------------------------------------------------------------------
| The following functions enable swapping the occupants at two locations in the
| burrow. Since the `Burrow` is immutable, this involves creating a new `Burrow`
| by iteration, while making the change. It would be easier to just use a 
| mutable `Burrow`, but I'm hoping that the immutable struct can be passed on
| the stack instead of the heap.
=#

# Given a room and a possible Amphipod, return a version of that room occupied
# by the possible amphipod
replace(R::Room{Amber}, MA::MaybeAmphipod) = Room(Amber, R.idx, MA)
replace(R::Room{Bronze}, MA::MaybeAmphipod) = Room(Bronze, R.idx, MA)
replace(R::Room{Copper}, MA::MaybeAmphipod) = Room(Copper, R.idx, MA)
replace(R::Room{Desert}, MA::MaybeAmphipod) = Room(Desert, R.idx, MA)
replace(H::Hallway, MA::MaybeAmphipod) = Hallway(H.idx, MA)

# Iterator for swapping the possible amphipod in one location with the 
# possible amphipod in another location
struct BurrowSwap{N}
    locations::NTuple{N,Location}
    swap1::Pair{Int64,MaybeAmphipod}
    swap2::Pair{Int64,MaybeAmphipod}
end

# Needed to make the iterator work
Base.eltype(::BurrowSwap) = Location
Base.length(iter::BurrowSwap) = length(iter.locations)

# Iterator implementation. This is mostly used to produce a new `Burrow` where
# the occupants of two locations are swapped.. Just returns the other locations
# as they are, in order. The locations to be swapped are replaced with a copy
# containing the intended occupant.
function Base.iterate(iter::BurrowSwap, state = 1)
    (swap1, swap2, locations) = (iter.swap1, iter.swap2, iter.locations)
    state > length(locations) && return nothing

    (idx1, idx2) = (swap1.first, swap2.first)
    location = locations[state]
    state == idx1 && return (replace(location, swap1.second), state + 1)
    state == idx2 && return (replace(location, swap2.second), state + 1)
    return (location, state + 1)
end

# Convenience function to conduct the swap, producing a new Burrow with the
# occupants in the locations indicated by `idx1` and `idx2` swapped.
function swap(burrow::Burrow, idx1::Int64, idx2::Int64)
    (occupant1, occupant2) = (burrow[idx1].occupant, burrow[idx2].occupant)
    constructor = BurrowSwap{length(burrow.locations)}
    swapper = constructor(burrow.locations, idx1 => occupant2, idx2 => occupant1)
    return Burrow(Tuple(l for l in swapper))
end

#= Generating States -----------------------------------------------------------
| This section defines functionality for determining the next possible `Burrow`
| states
=#

# A `Move` is a Tuple of movement cost and ending index
const Move = NTuple{2,Int64}
const COST = Dict(Amber() => 1, Bronze() => 10, Copper() => 100, Desert() => 1000)

# For a given burrow and location (indicated by `idx`), return the `Move`s that
# can be reached by the amphipod in the indicated location.
function nextmoves(burrow::Burrow, idx::Int64)
    amphipod = burrow[idx].occupant
    isnothing(amphipod) && return []

    # Starting at the indicated location, perform a breadth-first search for
    # all the spaces that can be reached from the given location. 
    movecost = COST[amphipod]
    queue = Vector{Move}([(0, idx)])
    visited = Set{Int64}()
    moves = Set{Move}()

    while !isempty(queue)
        (cost, current) = pop!(queue)

        for neighbor in NEIGHBORS[current]
            neighbor ∈ visited && continue
            isempty(burrow[neighbor]) || continue

            nextcost = cost + movecost
            pushfirst!(queue, (nextcost, neighbor))

            # Don't keep any moves that would stop in a doorway.
            neighbor ∈ values(DOORWAYS) && continue
            canmove(burrow[idx], burrow[neighbor], burrow) || continue
            push!(moves, (nextcost, neighbor))
        end
        push!(visited, current)
    end
    return moves
end

# Starting with a given `Burrow`, try moving all the `Amphipod`s and return 
# all the new `Burrow`s (new states) that can be produced by moving the
# amphipods. We'll keep up with the `Burrow` states, the cost to get there,
# and the estimated distance from the desired `Burrow` state. We'll sort
# the `MetaBurrow`s by accrued movement cost in our algorithm.
const MetaBurrow = Tuple{Int,Burrow} # (cost, burrow)
Base.isless(lhs::MetaBurrow, rhs::MetaBurrow) = lhs[1] < rhs[1]

function nextburrows(burrow::Burrow)
    burrows = Set{MetaBurrow}()

    for idx in 1:length(burrow)
        moves = nextmoves(burrow, idx)
        for (movecost, nextidx) in moves
            nextburrow = swap(burrow, idx, nextidx)
            push!(burrows, (movecost, nextburrow))
        end
    end
    return burrows
end

# Check all the `Room` spaces. If all of them hold a matching amphipod, then
# we've found the ideal `Burrow` state
function isdone(burrow::Burrow)
    for location in burrow.locations
        location isa Hallway && continue
        matches(location) || return false
    end
    return true
end

#= Solve the puzzle ------------------------------------------------------------
| Solve using a "best-first" search strategy, where all the states that can
| be reached from current state are added to a BinaryMinHeap, and the state
| with the lowest cost is taken as the next state to check. Repeat until the
| final state is found. The distance heuristic is useful for skipping
| neighbors to check, reducing the total search space.
=#

function solve(initial)
    heap = BinaryMinHeap([(0, initial)])
    seen = Set{Burrow}()

    while !isempty(heap) 
        (cost, current) = pop!(heap)
        current ∈ seen && continue
        isdone(current) && return cost
        push!(seen, current)

        for (burrowcost, nextburrow) in nextburrows(current)
            nextcost = cost + burrowcost
            push!(heap, (nextcost, nextburrow))
        end

    end
    error("Could not solve this input!")
end

That is, in fact, quite a bit of code that doesn’t include all the failed heuristic code I tried to write. Hoo boy!

Part One - Holes

So, as we know, we’ve got a smaller Burrow size for part one. The actual code that solves part one (mostly constant definitions, at this point) is below:

# Constants --------------------------------------------------------------------

#= Test input burrow state
| #############
| #...........#
| ###B#C#B#D###
| #A#D#C#A#
| #########
=#
const TESTBURROW = Burrow(
    Hallway(1),
    Hallway(2), Hallway(3),
    Room(Amber, 1, Bronze()), Room(Amber, 2, Amber()),
    Hallway(4), Hallway(5),
    Room(Bronze, 1, Copper()), Room(Bronze, 2, Desert()),
    Hallway(6), Hallway(7),
    Room(Copper, 1, Bronze()), Room(Copper, 2, Copper()),
    Hallway(8), Hallway(9),
    Room(Desert, 1, Desert()), Room(Desert, 2, Amber()),
    Hallway(10), Hallway(11)
)

#= Real input burrow state
| #############
| #...........#
| ###B#C#B#D###
| #A#D#C#A#
| #########
=#
const REALBURROW = Burrow(
    Hallway(1),
    Hallway(2), Hallway(3),
    Room(Amber, 1, Desert()), Room(Amber, 2, Bronze()),
    Hallway(4), Hallway(5),
    Room(Bronze, 1, Bronze()), Room(Bronze, 2, Desert()),
    Hallway(6), Hallway(7),
    Room(Copper, 1, Amber()), Room(Copper, 2, Amber()),
    Hallway(8), Hallway(9),
    Room(Desert, 1, Copper()), Room(Desert, 2, Copper()),
    Hallway(10), Hallway(11)
)

# Each index in `NEIGHBORS` contains a vector of the indices that can be reached
# from a given index in `Burrow.locations`, given the standard configuration
# produced by `Burrow()`. This is a bit brittle, since this constant will need
# to change if the `Burrow.locations` order changes.
const NEIGHBORS = [
    [2], 
    [1, 3], [2, 4, 6], [3, 5], [4],
    [3, 7], [6, 8, 10], [7, 9], [8],
    [7, 11], [10, 12, 14], [11, 13], [12],
    [11, 15], [14, 16, 18], [15, 17], [16],
    [15, 19], [18]
]

# We'll use the doorway indices to keep track of where the `Room`s are 
# in the `Burrow`
const DOORWAYS = Dict(
    Room{Amber} => 3, Room{Bronze} => 7,
    Room{Copper} => 11, Room{Desert} => 15
)

# Solve Part One ---------------------------------------------------------------

part1(test = false) = test ? solve(TESTBURROW) : solve(REALBURROW)

I’ve also defined the relationships (graph) between the various spaces an amphipod can be and a listing of doorway indices per room type as constants, since these change between puzzle parts.

Part Two - Dig Deep

Same deal as part one, except there are twice as many amphipods and the rooms are twice as deep! Again, we’ll define our inputs and some Burrow metadata as constants and solve.

#= Hardcoded Inputs ------------------------------------------------------------
| It was convenient for this puzzle to simply create the objects in code.
=#

#= Test input burrow state
| #############
| #...........#
| ###B#C#B#D###
| #D#C#B#A#
| #D#B#A#C#
| #A#D#C#A#
| #########
=#
const TESTBURROW = Burrow(
    Hallway(1),
    Hallway(2), Hallway(3),
    Room(Amber, 1, Bronze()), Room(Amber, 2, Desert()),
    Room(Amber, 3, Desert()), Room(Amber, 4, Amber()),
    Hallway(4), Hallway(5),
    Room(Bronze, 1, Copper()), Room(Bronze, 2, Copper()),
    Room(Bronze, 3, Bronze()), Room(Bronze, 4, Desert()),
    Hallway(6), Hallway(7),
    Room(Copper, 1, Bronze()), Room(Copper, 2, Bronze()),
    Room(Copper, 3, Amber()), Room(Copper, 4, Copper()),
    Hallway(8), Hallway(9),
    Room(Desert, 1, Desert()), Room(Desert, 2, Amber()),
    Room(Desert, 3, Copper()), Room(Desert, 4, Amber()),
    Hallway(10), Hallway(11)
)

#= Real input burrow state
| #############
| #...........#
| ###D#B#A#C###
| #D#C#B#A#
| #D#B#A#C#
| #B#D#A#C#
| #########
=#
const REALBURROW = Burrow(
    Hallway(1),
    Hallway(2), Hallway(3),
    Room(Amber, 1, Desert()), Room(Amber, 2, Desert()),
    Room(Amber, 3, Desert()), Room(Amber, 4, Bronze()),
    Hallway(4), Hallway(5),
    Room(Bronze, 1, Bronze()), Room(Bronze, 2, Copper()),
    Room(Bronze, 3, Bronze()), Room(Bronze, 4, Desert()),
    Hallway(6), Hallway(7),
    Room(Copper, 1, Amber()), Room(Copper, 2, Bronze()),
    Room(Copper, 3, Amber()), Room(Copper, 4, Amber()),
    Hallway(8), Hallway(9),
    Room(Desert, 1, Copper()), Room(Desert, 2, Amber()),
    Room(Desert, 3, Copper()), Room(Desert, 4, Copper()),
    Hallway(10), Hallway(11)
)

# Each index in `NEIGHBORS` contains a vector of the indices that can be reached
# from a given index in `Burrow.locations`, given the standard configuration
# produced by `Burrow()`. This is a bit brittle, since this constant will need
# to change if the `Burrow.locations` order changes.
const NEIGHBORS = [
    [2], [1, 3], [2, 4, 8], 
    [3, 5], [4, 6], [5, 7],
    [6], [3, 9], [8, 10, 14],
    [9, 11], [10, 12], [11, 13],
    [12], [9, 15], [14, 16, 20],
    [15, 17], [16, 18], [17, 19],
    [18], [15, 21], [20, 22, 26],
    [21, 23], [22, 24], [23, 25],
    [24], [21, 27], [26]
]

# We'll use the doorway indices to keep track of where the `Room`s are 
# in the `Burrow`
const DOORWAYS = Dict(
    Room{Amber} => 3, Room{Bronze} => 9,
    Room{Copper} => 15, Room{Desert} => 21
)

# Solve Part Two ---------------------------------------------------------------

part2(test = false) = test ? solve(TESTBURROW) : solve(REALBURROW)

Wrap Up

So, I’m a bit salty about today’s solution. I’m absolutely certain there is a way to apply an A* heuristic to narrow the search space for this problem, but after several days of off and on poking at this problem, I’ve come up empty-handed. In fact, the best results came from tweaking numbers in the heuristic to try to hone in on the right answer, which felt like guesswork and overfitting, AKA not a systematic or logical approach. This was one of the big reasons I ended up stripping out all the heuristic code and moving on. It’s entirely possible that I somehow overcomplicated the whole endeavor. Ah well. The upshot is that I spent a considerable amount of time reasoning through various permutations of this problem in Julia, so lots of practice! Which, at the end of the day, is the whole point of doing AoC this year. And, I’m almost done!

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!