Day 15 saw the return of both Intcode and an Advent of Code stalwart, search.
The basic shape of the code followed day 13's task: encapsulate an Intcode program in a structure that contains its input and output, and run that program to generate the maze. I then explore that maze until the repair droid finds the goal.
How should I explore the maze? As it's generated by a machine, there's no guarantee that the maze will be finite. And as I have no idea where the goal may be, it has to be an exhaustive search.
Depth-first search seems to have the closest affinity with the problem: send a little droid scurrying around the ship, looking for the goal. If it encounters a dead end, backtrack and try an alternative route. However, that approach will fail given an infinite space to search. The droid could set off down the wrong path, and if it's infinite, it will never return and hence never find the goal.
Breadth-first search is therefore the approach to take, exploring the space in an expanding wave until something finds the goal. If I always expand the shortest path first, the first path to the goal will be the shortest one.
I picked up one neat trick from the solutions megathread that exploits the immutable nature of data in Haskell. As the droid explores the space, I keep track of where it's been and how many steps were needed to get there. I can also record the full status of the droid that reached that spot, meaning there are many copies of the droid lying around. If I want to explore further from a particular spot, I can pick up the droid at that place and use it for the exploration.
Representing the maze
The next thing its to decide on the data structures to use in the problem.
The droid is similar to the ant from day 11: it contains the machine's state, and the input and output.
data Droid = Droid
{ _machine :: Machine
, _executionState :: ExecutionState
, _currentInput :: [Integer]
, _machineOutput :: [Integer]
} deriving (Eq)
The maze is represented as a Map going from a position to a Cell. A Cell is either a Wall, an Unknown space, or an Empty space. If it's Empty, I record the droid that got there, the distance from the start, and whether this is the goal location.
data Cell = Empty { _droid :: Droid
, _fromStart :: Integer
, _isGoal :: Bool
}
| Wall
| Unknown
deriving (Show, Eq)
type Hull = M.Map Position Cell
Finally, I included some ancillary data types and some functions to convert between the magic numbers and these more readable values.
type Position = (Integer, Integer) -- x, y
type Boundary = [Position]
data Direction = North | East | South | West deriving (Show, Eq, Ord)
data ReturnValue = Static | Moved | Goal deriving (Show, Eq, Ord)
commandOf :: Direction -> Integer
commandOf North = 1
commandOf South = 2
commandOf West = 3
commandOf East = 4
returnValue 0 = Static
returnValue 1 = Moved
returnValue 2 = Goal
Search
The search algorithm revolves around two data structures: the hull, that records what's been found so far; and the boundary, the interesting locations that need exploring.
The boundary is a list of positions (i.e. locations). Each position in the boundary is a location we know about, but one we want to explore from. The basic algorithm is to take the first position in the boundary and explore in all directions from that position. Each exploration in a direction will update the hull and find new positions to explore. These new positions will be added to the end of the boundary.
That gives the two functions searchHullStep and searchHullDirection.
searchHullStep :: (Hull, Boundary) -> (Hull, Boundary)
searchHullStep (hull, []) = (hull, [])
searchHullStep (hull, (here:boundary)) = foldl' (searchHullDirection here) (hull, boundary) directions
where directions = [North, East, South, West] :: [Direction]
searchHullDirection :: Position -> (Hull, Boundary) -> Direction -> (Hull, Boundary)
searchHullDirection here (hull, boundary) direction
| there `M.member` hull = (hull, boundary)
| found == Static = (M.insert there Wall hull, boundary)
| otherwise = (M.insert there newCell hull, boundary ++ [there])
where there = step here direction
droid = _droid $ hull!here
distance = _fromStart $ hull!here
(droid', found) = runDroid droid direction
newCell = Empty { _droid = droid'
, _fromStart = distance + 1
, _isGoal = (found == Goal)
}
searchHullStep just folds up the searches in each direction, but returns the same hull if the boundary is empty.
searchHullDirection does the work, depending on what it finds at the location being explored (called there).
- If it's already in the hull, the function does nothing and just returns the unchanged hull/boundary pair.
- If it's found to be a wall, it's added to the hull and the boundary is left unchanged.
- If it's a new vacant space, that space is filled with the appropriate information, and the new space is added to the boundary.
Searching the hull is just a case of repeatedly doing the search steps, until the goal is found, then returning that hull.
searchHull :: (Hull, Boundary) -> Hull
searchHull hullBoundary = fst $ head $ dropWhile goalNotFound $ iterate searchHullStep hullBoundary
And the solution extracts the cell containing the goal and finds how far away it is.
part1 mem = _fromStart $ snd $ M.findMin $ M.filter (containsGoal) hull
where hull = searchHull $ initialHullBoundary mem
Part 2
It turns out the space is finite after all!
I solved this part in two stages. The first stage was to generate a complete map of the space, reusing much of the previous code.
completeHull :: (Hull, Boundary) -> Hull
completeHull hullBoundary = fst $ head $ dropWhile incomplete $ iterate searchHullStep hullBoundary
The second stage was to do another breadth-first search of the space, in much the same way as I explored it initially. However, the data requirements here are a bit simpler. I can use a Set of already-oxygenated spaces (the closed set), and track the maximum time taken to fill any space.
fillTime :: Hull -> (S.Set Position) -> [(Position, Integer)] -> Integer -> Integer
fillTime _ _ [] t = t
fillTime hull closed ((here, t):boundary) maxt
| hull!here == Wall = fillTime hull closed boundary maxt
| S.member here closed = fillTime hull closed boundary maxt
| otherwise = fillTime hull closed' (boundary ++ neighbours) (max maxt t)
where closed' = S.insert here closed
neighbours = map (\d -> (step here d, t + 1)) directions
directions = [North, East, South, West] :: [Direction]
Code
You can get the code, here or on Github.