diff options
Diffstat (limited to '2020')
| -rw-r--r-- | 2020/11.hs | 86 | ||||
| -rw-r--r-- | 2020/11.in | 91 |
2 files changed, 177 insertions, 0 deletions
diff --git a/2020/11.hs b/2020/11.hs new file mode 100644 index 0000000..2d573be --- /dev/null +++ b/2020/11.hs @@ -0,0 +1,86 @@ +{-# LANGUAGE LambdaCase #-} +module Main where + +import Data.List (find, findIndex, intercalate) +import Data.Maybe (catMaybes, fromJust) +import qualified Data.Vector as V +import qualified Data.Vector.Storable as U +import Data.Word (Word8) +import Foreign.Ptr (Ptr, castPtr) +import Foreign.Storable (Storable(..)) + +import Input + + +data Cell = Floor | Seat | Occupied + deriving (Show, Eq, Enum) + +instance Storable Cell where + sizeOf _ = sizeOf (undefined :: Word8) + alignment _ = alignment (undefined :: Word8) + peek p = toEnum . fromIntegral <$> peek (castPtr p :: Ptr Word8) + poke p x = poke (castPtr p :: Ptr Word8) (fromIntegral (fromEnum x)) + +parseCell :: Char -> Cell +parseCell '.' = Floor +parseCell 'L' = Seat +parseCell '#' = Occupied +parseCell _ = error "Cannot parse cell" + +showCell :: Cell -> Char +showCell Floor = '.' +showCell Seat = 'L' +showCell Occupied = '#' + +data Grid = Grid Int Int (U.Vector Cell) + deriving (Show, Eq) + +parseGrid :: [String] -> Grid +parseGrid lns = + let w = length (head lns) + h = length lns + in Grid w h (U.fromListN (w * h) (concatMap (map parseCell) lns)) + +showGrid :: Grid -> String +showGrid (Grid w h v) = + intercalate "\n" [[showCell (v U.! (w * y + x)) | x <- [0..w-1]] + | y <- [0..h-1]] + +numOccupied :: Grid -> Int +numOccupied (Grid _ _ v) = sum (map (fromEnum . (== Occupied)) (U.toList v)) + +evolve :: Grid -> ([Cell] -> Maybe Int) -> Int -> Grid -> Grid +evolve (Grid w h template) nbFunc scareCount = + \(Grid _ _ v) -> + let newCellAt x y = + let neighbours = [v U.! (w * y' + x') | (x', y') <- nbIndicesArr V.! (w * y + x)] + filledNbs = sum (map (fromEnum . (== Occupied)) neighbours) + in case v U.! (w * y + x) of + Floor -> Floor + Seat | filledNbs == 0 -> Occupied + | otherwise -> Seat + Occupied | filledNbs >= scareCount -> Seat + | otherwise -> Occupied + in Grid w h (U.generate (w * h) (\i -> newCellAt (i `rem` w) (i `quot` w))) + where + inBounds (x, y) = 0 <= x && x < w && 0 <= y && y < h + nbIndices x y = catMaybes + [(sight !!) <$> nbFunc [template U.! (w * y' + x') | (x', y') <- sight] + | dy <- [-1..1], dx <- [-1..1] + , dx /= 0 || dy /= 0 + , let sight = takeWhile inBounds [(x+i*dx, y+i*dy) | i <- [1..]]] + nbIndicesArr = V.generate (w * h) (\i -> nbIndices (i `rem` w) (i `quot` w)) + + +equilibriumFor :: Eq a => (a -> a) -> a -> a +equilibriumFor f x = fst (fromJust (find (uncurry (==)) (zip xs (tail xs)))) + where xs = iterate f x + +main :: IO () +main = do + input <- getInput 11 + let initGrid = parseGrid input + evolve1 = evolve initGrid (\case Seat:_ -> Just 0 ; _ -> Nothing) 4 + evolve2 = evolve initGrid (findIndex (== Seat)) 5 + print (numOccupied (equilibriumFor evolve1 initGrid)) + print (numOccupied (equilibriumFor evolve2 initGrid)) diff --git a/2020/11.in b/2020/11.in new file mode 100644 index 0000000..69da577 --- /dev/null +++ b/2020/11.in @@ -0,0 +1,91 @@ +LLLLLLLLLLL.LLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLL.LLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLL.LLLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLL.L.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLL.LLLLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLLLLLLLLLL..LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +.L..LLL...L....LLLL.L..L...............LLLLLL..LL.L.....L.....L.L.L.L.L...LLL.....L.L....LLL.LL.. +LLLLLL.LLLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LL.LLLLL.LLLL.LLLLLLLL.LLLLL.LLLLLLLL.LLLL +LLLLLLLLLLL.LLLLLLLLLLLLLLLLLL.L.LLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLL.L.LLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLLLLLLLL..LLLLLLLLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLL.LLLLLLLLLLLLLL +LLLLLLLLLLL.LLLLL.LLLLLL.LLLL..LLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLL +.LLLLL.LLLL.LLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLL.L.LLLLLLLLLLLL.LLLLLLLLLLL.LLLL.LL.LLLLLLLLLLLLLLLLLLL +L.....L..L...LL.L....LLL.L..L.....LLLL.L.L.L.L...L..LLLLL.L..LL..L..L....L.LLL.L.LL.........L..L. +LLLLLLLLLL.LLLLLL.LLLLLL..LLLL..LLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLL.LL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLLLLLLLLLLLLL.LLLLLLLLLLL..LLLLLLLLLLLLL.LLLLLLLLL.LLLLL.LL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLL +LL.LLL.LLLL.LLLLL.LLLL.L.LLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.L.LLL.L.LLLLLLLLLLL +..L.L.L....L.LL.L....LL.............L.L.LLL...L.L.L......L...L..L.......LL....L...L...L....LL.L.L +LLLLLL..LLL.LLLLLLLLLLLLLLLLLL.LLLLLLL..LLLL.LLLLLLLLL.LLLL.LLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLL.LLLLL.LLL.LLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.L.LLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLL..LLLLLLLLLLLLLLLLLLLLLLLL.LLL..LL.LLLLL.LLLLLLLLLLLLL +L.L.LLLLLLL.LLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL..LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLLLLL.LL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LL.LLLLLLLL.LLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLL.L.LLLLLLL +L.LLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLL.LLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLL.LLLLLLL +...L.L..LL...L.L.L......LL..L.L.L..L..L.LL...L............L...L.....LLL..LL.LLL.LL..L.LLL....LL.. +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLL..LLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLLLLLLLLL..LLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLL.LLLLL.LLLLLLLLL.LLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLLLLLLLLLL..L.LLLLLL.LL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL..LLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLL..LLLLLL.L.LLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLL..LLLLLLLLLLLLL +L.L.L.LL.LL..L...L....L........L.L..L...LLLLLL...L........L..LLLLLLL.LLL...L.L............L.L..L. +LL.LLLLLLLL.LLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLLLLL.L.LLLLL.LLLLLL.LLLLL.LLLLLLLLLL.LL.LLLLLLLLL.LLLLLLLL.LL.LL..LLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLL..LLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.L.LLLLLLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLLLLLLLLLLLLLLL..LLLLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLL.LL.LLLLL +LLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLL.LLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLL.LLLLLLLLLLLLL +.....L..L...LL....LLLLLL.....L..L..L.LL.L.L.LL...L....L.L..L...L..L.L..LL..LLL...L.L.L...L.LLL... +LLLLLLLLLLL.LLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLL.L +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLLL.L.LLLLL.LLLLLLL.LLLLL.L.LLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLL..LLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLL..LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLL..LLLLLLLLLLLLL +L..........L...L.......L.LLLLLL...LL.....L..L.LL....L..L.L...L..L.....LL..L..LL..L.L...L..L.L..L. +.LLLLL..LLL.LLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLL.L.LLLL.LLLLLLLLLLLL.LLLLL.LLL.LLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLLLLLLL.LLLLL.LLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LL.LLLLLLLLLL +LLL.L....L..L..L..L......L...LL.L..L...LLL...L.....L.LL.LLL........LL..L.L.LL.L..L..L..LLLL.LL... +LLLLLL.LLLL.LLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LL.LL.LL.LLL.LLLLLL +LLLLLLLLLLL.LLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLLLLL.LLLLLLL..LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLL..LLLLLLLLLLLL +LLLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLL.LLLLLLLLLLLL.LLLLLLL.LLLLL.LLLL.LLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL +....L....L.....L.....LLLL.......LL.L..L...L.........L.....L......L..L..L.LL.....L..L.L.L.LL...L.L +LLLLLLLLLLL.LLLLL.LLLLLLLLLLLL.LLLLLLL.LL.LL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLL +LLLLLLLLLLL.LLLLLLLLLL.L.LLLLLLLLLLLLL.LLL.LLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLL.LL.LL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLLLLLLLLLL.LL.LLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLLLLLLLL.LLLLLL.LL.LL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +...L.L....L.LL....L..LLLL.....L.L.LLL.....L.L.LL.LL......LLL.L.....L..LL.LL.L...L.L..LLL..LL..... +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLL.LLLL +LLLLLL.LLLL.LLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL.LL..LLLLLLLLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LL.LLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLL.LL.LLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLL +LLLLLLLLLL..LLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLL.LLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LLLL.LLLLLLLLLLLL.LLLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLL +.L...LL.LLL...L.LL.LL..L......LL.....LL..L..............L....L........LLL...L.L..LL...L....L..... +LLLLLL.LLLLLLLLLL..LLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLL.LL.LLLLLL.LLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLL.LL.LLLLLLL.L.LLLLLL.LLLLL.LLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLL.LLLLLL.LLLLLLLLLLLLL..LLLLLLLLLLLLLLLLLLLLLLL.LL.LLLLLLLLLL.LLLLL.LLLLLLLLLLLLL +LLLLLLLLLLL.LLLLLLLLLLLLLLL.LL.LLLLLLLL..LLL.LLLLLLLLL.LLLLLLLLLLL.LLLLLLLLLL.LLLLL.LLLLLLLLLLLLL |