AoC 2022 D14: Regolith Reservoir

Haskell | Problem statement | Source code | Tags: Physics

← Previous Back to AoC Index Next →

Part 1

I build the literal grid as a Map (Int, Int) Char (exactly same representation as the problem statement). Then I drop sand. Each time, I check if the sand can move down, then down-left, then down-right. If it can't move (same position after moving down), I add it to the grid. It also stops when the sand falls to maxY, to prevent the sand actually falling indefinitely into the abyss.

dropSand :: Int -> Map (Int, Int) Char -> (Map (Int, Int) Char, (Int, Int))
dropSand maxY grid = (Map.insert finalPos 'o' grid, finalPos)
  where
    finalPos = untilSame moveDown sandSource
    moveDown p
      | snd p == maxY = p
      | not $ Map.member down grid = down
      | not $ Map.member downLeft grid = downLeft
      | not $ Map.member downRight grid = downRight
      | otherwise = p
      where
        down = p |+| (0, 1)
        downLeft = p |+| (-1, 1)
        downRight = p |+| (1, 1)

untilSame :: (Eq a) => (a -> a) -> a -> a
untilSame f x
  | x == x' = x
  | otherwise = untilSame f x'
  where
    x' = f x
hs

Now I can drop an indefinite number of sands using iterate. Thanks to laziness, I don't even have to define a stopping condition here. It returns an infinite list of the positions of the dropped sands, and I can just take as many as I need.

dropSands :: Int -> Map (Int, Int) Char -> [(Int, Int)]
dropSands maxY grid = map snd $ iterate (\(m, _) -> dropSand maxY m) $ dropSand maxY grid
hs

In part 1, I need the number of sands before a sand falls into the abyss, i.e., its y position reaches ymax (which is the bottommost line).

let ymax = maximum $ map snd $ concat lines
print $ countWhile (\(_, y) -> y < ymax) (dropSands ymax grid)
hs

Part 2

Same thing, but this time maxY is ymax + 1 (one cell above the floor). And I count until the position reaches the source.

let ymax = maximum $ map snd $ concat lines
print $ 1 + countWhile (/= sandSource) (dropSands (ymax + 1) grid)
hs

I add 1 to the count because the sand that reaches the source should still be counted.

← Previous Back to AoC Index Next →