From 5906e1d8d0723d8c7e3d97c3a29988723efe2f71 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sun, 12 Dec 2021 10:33:15 +0000 Subject: [PATCH] Done day 11 --- advent-of-code21.cabal | 5 +++ advent11/Main.hs | 89 ++++++++++++++++++++++++++++++++++++++++++ data/advent11.txt | 10 +++++ data/advent11a.txt | 10 +++++ 4 files changed, 114 insertions(+) create mode 100644 advent11/Main.hs create mode 100644 data/advent11.txt create mode 100644 data/advent11a.txt diff --git a/advent-of-code21.cabal b/advent-of-code21.cabal index 626e0ae..12cd8ab 100644 --- a/advent-of-code21.cabal +++ b/advent-of-code21.cabal @@ -134,3 +134,8 @@ executable advent10 import: common-extensions, build-directives main-is: advent10/Main.hs build-depends: containers + +executable advent11 + import: common-extensions, build-directives + main-is: advent11/Main.hs + build-depends: array, containers, linear diff --git a/advent11/Main.hs b/advent11/Main.hs new file mode 100644 index 0000000..a74f4fa --- /dev/null +++ b/advent11/Main.hs @@ -0,0 +1,89 @@ +-- Writeup at https://work.njae.me.uk/2021/12/09/advent-of-code-2021-day-9/ + +import Data.Array.IArray +import Data.Char +import Linear (V2(..), (^+^)) + +type Coord = V2 Int +type Grid = Array Coord Octopus + +data Octopus = Octopus Int Bool + deriving (Ord, Eq, Show) + +main :: IO () +main = + do text <- readFile "data/advent11.txt" + let grid = mkGrid text + print $ part1 grid + print $ part2 grid + +mkGrid :: String -> Grid +mkGrid text = listArray ((V2 0 0), (V2 r c)) $ map mkOct $ concat rows + where rows = lines text + r = length rows - 1 + c = (length $ head rows) - 1 + mkOct e = Octopus (digitToInt e) False + +part1 grid = snd $ (simulate grid) !! 100 + +part2 grid = length $ takeWhile notSyncronised $ simulate grid + where notSyncronised (g, _) = not $ simultaneous g + +simulate :: Grid -> [(Grid, Int)] +simulate grid = iterate step (grid, 0) + +step :: (Grid, Int) -> (Grid, Int) +step (grid0, flashCount0) = (grid3, flashCount0 + numFlashers) + where grid1 = increment grid0 + triggers = findFlashers grid1 + grid2 = flash grid1 triggers + flashers = findFlashers grid2 + numFlashers = length flashers + grid3 = resetFlashers grid2 flashers + + +simultaneous grid = all zeroOct $ elems grid + where zeroOct (Octopus 0 _) = True + zeroOct _ = False + +increment :: Grid -> Grid +increment = amap incrementOne + +incrementSome grid locations = grid // (zip locations incrementedOcts) + where incrementedOcts = map (incrementOne . (grid !)) locations + +incrementOne (Octopus energy flashed) = Octopus (energy + 1) flashed + + +findFlashers :: Grid -> [Coord] +findFlashers = map fst . filter (overpowered . snd) . assocs + where overpowered (Octopus energy _) = energy > 9 + + +flash grid [] = grid +flash grid (here:agenda) + | flashed == True = flash grid agenda + | energy <= 9 = flash grid agenda + | otherwise = flash grid'' agenda' + -- set this as flashed + -- increment neighbours + -- add negighbours to agenda + where Octopus energy flashed = grid ! here + nbrs = neighbours grid here + octopus' = Octopus (energy + 1) True + agenda' = nbrs ++ agenda + grid' = grid // [(here, octopus')] + grid'' = incrementSome grid' nbrs + +resetFlashers :: Grid -> [Coord] -> Grid +resetFlashers grid locations = grid // (zip locations resetOcts) + where resetOcts = repeat (Octopus 0 False) + + +neighbours :: Grid -> Coord -> [Coord] +neighbours grid here = filter (inRange (bounds grid)) + [ here ^+^ (V2 r c) + | r <- [-1, 0, 1] + , c <- [-1, 0, 1] + , (r, c) /= (0, 0) + ] diff --git a/data/advent11.txt b/data/advent11.txt new file mode 100644 index 0000000..89cabdc --- /dev/null +++ b/data/advent11.txt @@ -0,0 +1,10 @@ +3265255276 +1537412665 +7335746422 +6426325658 +3854434364 +8717377486 +4522286326 +6337772845 +8824387665 +6351586484 \ No newline at end of file diff --git a/data/advent11a.txt b/data/advent11a.txt new file mode 100644 index 0000000..a3819c9 --- /dev/null +++ b/data/advent11a.txt @@ -0,0 +1,10 @@ +5483143223 +2745854711 +5264556173 +6141336146 +6357385478 +4167524645 +2176841721 +6882881134 +4846848554 +5283751526 \ No newline at end of file -- 2.34.1