Advent of Code 2021 day 9

    The hardest part of this puzzle was deciding on the best data structure and library for the grid.

    Data types, the grid, and the Ix data class

    Haskell has a surfeit of array types. There's the standard Array library, the Vector library that can be misused to provide multi-dimensional arrays, and more complex libraries like Repa, Massiv, and Dense. There's even the Grid library for representing grids, but that only holds locations, not data. The problem with Repa, Massiv, and Dense is that the have very complex types to account for controlling how and when evaluation takes place, complicated indexing schemes, and similar. That was all overkill for this problem, even if it would have been fun to learn about.

    In the end, I settled on the basic Array library, but using the V2 data type from Linear for the coordinates.

    type Coord = V2 Int
    type Grid = Array Coord Int
    type Basin = S.Set Coord

    Making the grid from the input was fairly simple.

    mkGrid :: String -> Grid
    mkGrid text = listArray ((V2 0 0), (V2 r c)) $ map digitToInt $ concat rows
      where rows = lines text
            r = length rows - 1
            c = (length $ head rows) - 1

    Finding neighbours was made much simpler by a little investigation into the Ix data class, and the use of bounds and inRange functions to tell that a possible location is within the array.

    neighbours :: Grid -> Coord -> [Coord]
    neighbours grid here = filter (inRange (bounds grid))  
      [ here ^+^ delta 
      | delta <- [V2 -1 0, V2 1 0, V2 0 -1, V2 0 1]

    Part 1

    From that, finding the the lowest points is examining each location in the grid and checking that all its neighbours are higher.

    part1 :: Grid -> Int
    part1 grid = sum $ map (riskLevel grid) $ lowPoints grid
    riskLevel :: Grid -> Coord -> Int
    riskLevel grid here = grid ! here + 1
    lowPoints :: Grid -> [Coord]
    lowPoints grid = filter (isLow grid) $ indices grid
    isLow :: Grid -> Coord -> Bool
    isLow grid here = all (> this) nbrs
      where nbrs = map (grid ! ) $ neighbours grid here
            this = grid ! here

    Part 2

    This is a by-now standard flood fill / breadth-first search algorithm. Starting from a lowest point, it adds all higher points to the boundary / agenda (if they're not already in the basin), adds the current point to the basin, and repeats. There's a bit of fiddling around with not adding positions at height 9, and I don't think it would work at tracking across plateaus of height below 9. But it gives the right answer.

    part2 :: Grid -> Int
    part2 grid = product $ take 3 ordSizes
      where lows = lowPoints grid
            sizes = map (basinSize grid) lows
            ordSizes = reverse $ sort sizes
    higherNeighbours :: Grid -> Coord -> [Coord]
    higherNeighbours grid here = filter isHigher $ neighbours grid here
      where this = grid ! here
            isHigher there = (grid ! there) > this
    basinSize :: Grid -> Coord -> Int
    basinSize grid basinSeed = S.size $ breadthFirstSearch grid (S.singleton basinSeed) S.empty
    breadthFirstSearch :: Grid -> Basin -> Basin -> Basin
    breadthFirstSearch grid agenda basin
      | S.null agenda = basin
      | otherwise = breadthFirstSearch grid agenda' basin'
      where here = S.findMin agenda
            candidates = (S.fromList $ higherNeighbours grid here) \\ basin
            basin' = if (grid ! here) == 9 
                     then basin
                     else S.insert here basin
            agenda' = S.union candidates $ S.delete here agenda


    You can get the code from my locally-hosed Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.