AoC 2022 D12: Hill Climbing Algorithm

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

This is a shortest path problem with equal edge weights, so we can just run BFS. Each node (cell) is connected to its neighbors if the height difference is at most 1.

I parse the input grid into a Map (Int, Int) Int, storing the heights of each cell. This part isn't very interesting so I'll skip it. Anyway, part 1 has a single starting point and part 2 has multiple starting points, but the BFS logic works the same. I just enqueue all starting points at the beginning of the BFS, where the queue keeps track of the cell's coordinates and the distance from the start. The BFS stops when we reach the end cell or the queue is depleted.

bfs :: Map (Int, Int) Int -> (Int, Int) -> [(Int, Int)] -> Int
bfs matrix end starts = runQueue matrix end (Seq.fromList $ map (,0) starts) Set.empty

This is my first time implementing BFS in a functional language. It turned out to be not more complicated than the loop version.

runQueue ::
  Map (Int, Int) Int ->
  (Int, Int) ->
  Seq ((Int, Int), Int) ->
  Set (Int, Int) ->
  Int
runQueue _ _ Seq.Empty _ = error "No path found"
runQueue matrix end ((cur, curDist) Seq.:<| rest) visited =
  if cur == end then curDist else runQueue matrix end queue' visited'
  where
    curHeight = matrix Map.! cur
    neighbors = filter canGo $ map (|+| cur) [(1, 0), (0, 1), (-1, 0), (0, -1)]
    neighborDists = map (,curDist + 1) neighbors
    visited' = Set.union visited $ Set.fromList neighbors
    queue' = rest Seq.>< Seq.fromList neighborDists

    canGo pos = case Map.lookup pos matrix of
      Nothing -> False
      Just neighborHeight -> Set.notMember pos visited && neighborHeight - curHeight <= 1

← Previous Back to AoC Index Next →