advent11/Main.hs

   1 -- Writeup at https://work.njae.me.uk/2021/12/09/advent-of-code-2021-day-9/
   2
   3 import Data.Array.IArray
   4 import Data.Char
   5 import Linear (V2(..), (^+^))
   6
   7 type Coord = V2 Int
   8 type Grid = Array Coord Octopus
   9
  10 data Octopus = Octopus Int Bool
  11   deriving (Ord, Eq, Show)
  12
  13 main :: IO ()
  14 main =
  15   do  text <- readFile "data/advent11.txt"
  16       let grid = mkGrid text
  17       print $ part1 grid
  18       print $ part2 grid
  19
  20 mkGrid :: String -> Grid
  21 mkGrid text = listArray ((V2 0 0), (V2 r c)) $ map mkOct $ concat rows
  22   where rows = lines text
  23         r = length rows - 1
  24         c = (length $ head rows) - 1
  25         mkOct e = Octopus (digitToInt e) False
  26
  27 part1 grid = snd $ (simulate grid) !! 100
  28
  29 part2 grid = length $ takeWhile notSyncronised $ simulate grid
  30   where notSyncronised (g, _) = not $ simultaneous g
  31
  32 simulate :: Grid -> [(Grid, Int)]
  33 simulate grid = iterate step (grid, 0)
  34
  35 step :: (Grid, Int) -> (Grid, Int)
  36 step (grid0, flashCount0) = (grid3, flashCount0 + numFlashers)
  37   where grid1 = increment grid0
  38         triggers = findFlashers grid1
  39         grid2 = flash grid1 triggers
  40         flashers = findFlashers grid2
  41         numFlashers = length flashers
  42         grid3 = resetFlashers grid2 flashers
  43
  44
  45 simultaneous grid = all zeroOct $ elems grid
  46   where zeroOct (Octopus 0 _) = True
  47         zeroOct _ = False
  48
  49 increment :: Grid -> Grid
  50 increment = amap incrementOne
  51
  52 incrementSome grid locations = grid // (zip locations incrementedOcts)
  53   where incrementedOcts = map (incrementOne . (grid !)) locations
  54
  55 incrementOne (Octopus energy flashed) = Octopus (energy + 1) flashed
  56
  57
  58 findFlashers :: Grid -> [Coord]
  59 findFlashers = map fst . filter (overpowered . snd) . assocs
  60   where overpowered (Octopus energy _) = energy > 9
  61
  62
  63 flash grid [] = grid
  64 flash grid (here:agenda)
  65   | flashed == True = flash grid agenda
  66   | energy <= 9 = flash grid agenda
  67   | otherwise = flash grid'' agenda'
  68     -- set this as flashed
  69     -- increment neighbours
  70     -- add negighbours to agenda
  71   where Octopus energy flashed = grid ! here
  72         nbrs = neighbours grid here
  73         octopus' = Octopus (energy + 1) True
  74         agenda' = nbrs ++ agenda
  75         grid' = grid // [(here, octopus')]
  76         grid'' = incrementSome grid' nbrs
  77
  78 resetFlashers :: Grid -> [Coord] -> Grid
  79 resetFlashers grid locations = grid // (zip locations resetOcts)
  80   where resetOcts = repeat (Octopus 0 False)
  81
  82
  83 neighbours :: Grid -> Coord -> [Coord]
  84 neighbours grid here = filter (inRange (bounds grid))
  85   [ here ^+^ (V2 r c)
  86   | r <- [-1, 0, 1]
  87   , c <- [-1, 0, 1]
  88   , (r, c) /= (0, 0)
  89   ]