Discussion on: Advent of Code 2020 Solution Megathread - Day 11: Seating System

View post

Bit late today as I had to do yesterday first, due to teaching commitments and just to tired to sit down at 10pm to work on it yesterday :-)

Anyway, my first solution, which I won't post here, was very (very) slow, using just lists. So after see looking at comments reddit replaced lists with Map, with the key being the 2D index, it worked out pretty well. Of course, it would have been a lost faster in Rust or C++, just to two arrays, one for the current step, and one for the next, updating in place, and simply switching each step. However I'm trying to do as many of these using Haskell, as most of my other days use Rust and C++ and it's been fun returning to Haskell after quite a while. I feel I've learnt a lot just over these last few days, which always sees like a good outcome. Enough chat, my solution:

data Seat = E | O | F
    deriving (Show, Eq)

type Seats = Map (Int,Int) Seat  

getNeighbours :: ((Int,Int) -> (Int, Int) -> Bool) -> (Int,Int) -> [(Int, Int)]
getNeighbours f idx = filter (f idx) [(-1,-1), (-1,0), (-1,1), (0,-1),
                                        (0,1), (1,-1), (1,0), (1,1)]

--rules :: Seats -> Seat -> Seat
rules :: Int -> [(Int,Int)] -> Seat -> Seat
rules _ _ F                     = F
rules _ ns E | null ns          = O
rules g ns O | null (drop g ns) = O
rules _ _ _                     = E

parse :: [String] -> Seats
parse seats = let idxs = [((i,j), f s) | (i, row) <- zip [0..] seats, 
                                         (j, s) <- zip [0..] row ]
              in M.fromList idxs
    where 
        f '.' = F
        f 'L' = E
        f '#' = O

doTask :: (Seats -> (Int, Int) -> (Int, Int) -> Bool) -> Int -> Seats -> Int
doTask f g seats = let seats' = M.mapWithKey (rules g . getNeighbours (f seats)) seats
            in if seats == seats' 
                then M.size $ M.filter (== O) seats
                else doTask f g seats'

main = do seats <- readFile "day11_input" <&> lines <&> parse
          print (doTask task1N 3 seats)
          print (doTask task2N 4 seats)
    where
        task1N seats (i,j) (di,dj) = Just O == seats !? (i+di, j+dj)

        task2N seats (i, j) (di, dj) = case seats !? (i+di, j+dj) of
            Just F -> task2N seats (i+di, j+dj) (di, dj)
            Just O -> True
            _      -> False