AoC 2022 D24: Blizzard Basin

| Problem statement | Source code | Tags: BFS/DFS

Part 1

All it takes is to do a BFS with the current time as part of the state. Also realize that you don't have to actually simulate the blizzards; given the time and a position, you can know if a blizzard is there by going backwards in the direction of the blizzard and checking if there was a blizzard there at time 0.

The canMoveTo function essentially determines the edges for a node (r, c, t) by checking if the position is out of bounds, is a wall, or has a blizzard at time t. If not, we can move there.

canMoveTo :: Map (Int, Int) Char -> Int -> Int -> State -> Bool
canMoveTo board width height (r, c, t) =
  case Map.lookup (r, c) board of
    Just '#' -> False
    Nothing -> False
    _ ->
      let blockingWinds =
            [ ((r, (c - t - 1) `mod` width + 1), '>'),
              (((r - t - 1) `mod` height + 1, c), 'v'),
              ((r, (c + t - 1) `mod` width + 1), '<'),
              (((r + t - 1) `mod` height + 1, c), '^')
            ]
       in all (\(pos, wind) -> Map.lookup pos board /= Just wind) blockingWinds

Writing a BFS for the last time this year.

bfs ::
  Map (Int, Int) Char ->
  Int ->
  Int ->
  (Int, Int, Int) ->
  (Int, Int) ->
  Int
bfs board width height start (er, ec) =
  go (Seq.singleton start) (Set.singleton start)
  where
    go :: Seq State -> Set State -> Int
    go Seq.Empty _ = error "No path found"
    go (s@(r, c, t) Seq.:<| q) seen
      | (r, c) == (er, ec) = t
      | otherwise =
          let next = [n | n <- neighbors s, canMoveTo board width height n, n `Set.notMember` seen]
              seen' = foldr Set.insert seen next
              q' = q Seq.>< Seq.fromList next
           in go q' seen'

The answer is given by bfs board width height (0, 1, 0) (height + 1, width).

Part 2

Just execute the BFS three times: from start to end, then from end to start, and finally from start to end again. Each time, pass the previous end time as the starting time for the next BFS.

let (_, _, t) =
      foldr
        (\(r, c) lastState -> (r, c, bfs board width height lastState (r, c)))
        (0, 1, 0)
        [(height + 1, width), (0, 1), (height + 1, width)]

← Previous Back to AoC Index Next →