Advent of Code 2019 day 20

The day 20 challenge was very similar to the day 18 challenge, and a lot of today's solution is lifted directly from that. There were three tricky parts to this

1. Extracting the portal information from the datafile
2. Using typeclasses to keep most of the code the same
3. Handling which portals were available in part 2

Extracing portals

In day 18, I could walk through the data file character by character, and extract the key and door information by looking at just the one character under consideration. But the portal codes in this example were two characters long plus the adjacent passage space, and often spanned different rows.

buildMazeCell detects possible portals by finding upper-case letters, and makePortal does the work. It looks to see if there's another letter either to the right or below of the found letter. If so, this is the two-character code we're after; if not, we've found the second letter of the portal, and we know it's already been processed. Depending on the direction of the label, I check whether there's a full stop to the right or below, and set the portal's access position accordingly. At this stage, I just use a default value for whether the portal is inside or outside the maze. (charAt returns a default value if it's asked for a character outside the given grid.)

buildMazeCell :: [String] -> Int -> MazeComplex -> Int -> MazeComplex
buildMazeCell rows r mc c
    | char == '.' = mc'
    | isUpper char = mc & portalsE .~ portals'
    | otherwise = mc
    where char = (rows!!r)!!c
          mc' = mc & mazeE %~ (S.insert here)
          here = (r, c)
          portals' = makePortal (mc ^. portalsE) rows char r c


makePortal portals rows hc r c 
    | isUpper rc = if pr == '.'
                   then S.insert (Portal { _label = [hc, rc]
                                         , _position = (r, c + 2)
                                         , _location = Outer 
                                         } ) portals
                   else S.insert (Portal { _label = [hc, rc]
                                         , _position = (r, c - 1)
                                         , _location = Outer 
                                         } ) portals
    | isUpper dc = if pd == '.'
                   then S.insert (Portal { _label = [hc, dc]
                                         , _position = (r + 2, c)
                                         , _location = Outer 
                                         } ) portals
                   else S.insert (Portal { _label = [hc, dc]
                                         , _position = (r - 1, c)
                                         , _location = Outer 
                                         } ) portals
    | otherwise = portals
    where rc = charAt rows r (c + 1)
          dc = charAt rows (r + 1) c
          pd = charAt rows (r + 2) c
          pr = charAt rows r (c + 2)

Contracting the graph

Again, similarly to day 18, I did this with a breadth-first search from each portal position, to find the shortest distance to all other reachable portals. That gives an an Edge that represents a Walk. I also connect the portals with same label, with a Teleport edge. The Set of edges represents the whole maze.

type EdgeConnects = (Portal, Portal)
data EdgeType = Walk | Teleport deriving (Eq, Ord, Show)

data Edge = Edge { _connects :: EdgeConnects
                 , _edgeType :: EdgeType
                 , _distance :: Int
                 } deriving (Eq, Ord, Show)
makeLenses ''Edge   

type Edges = S.Set Edge

Once I'd contracted the graph, I decided to view the structure between portals (using GraphViz, and the list of links in the contracted graph). This structure explains why my search, even without any heuristic, found a solution very quickly: there are essentially no decisions to make at most positions in the contracted graph.

Typeclasses

For part 1, it's enough to keep track of just the current portal. For part 2, I also have to keep track of the maze level. That means I need a different structure for the search state. To keep the code the same, I use a SearchState typeclass and implement different versions of the four functions that refer directly to that state.

class (Eq s, Ord s, Show s) => SearchState s where
    successors :: s -> MazeContext (Q.Seq (s, Edge))
    estimateCost :: s -> MazeContext Int
    emptySearchState :: Portal -> s
    isGoal :: s -> MazeContext Bool

data LevelledSearchState = LevelledSearchState
    { _portalS :: Portal
    , _levelS :: Int
    } deriving (Eq, Ord, Show)
makeLenses ''LevelledSearchState

Because the searchMaze function doesn't take any arguments, the only way to tell Haskell which version of the search to use is by defining the type of the return value.

part1 :: Maze -> Int
part1 maze = maybe 0 _cost result
    where result = runReader searchMaze maze :: Maybe (Agendum Portal)

part2 :: Maze -> Int
part2 maze = maybe 0 _cost result
    where result = runReader searchMaze maze :: Maybe (Agendum LevelledSearchState)

You can look at the code for the different implementations of the four functions.

Fixing available portals

One thing that gave me a few head-scratchy moments was the code to determine which edges in the contracted graph were available at which level.

Using the notation of a terminal portal to refer to the start and finish portals, the conditions on whether an Edge is available are:

• at level 0, you can Walk to a terminal portal
• at levels other than 0, you can't Walk to a terminal portal
• at level 0, you can't Walk to a non-terminal, Outer portal
• at levels other than 0, you can Walk to a non-terminal, Outer portal
• all other edges are always available.

Code

You can look at the code here or on Github.