Discussion on: Advent of Code 2020 Solution Megathread - Day 21: Allergen Assessment

View post

YEsterday was not fun Haskell, I did get it done, but it is horrible. Mostly my solution, some people on Reddit did it with mutable arrays, however, the whole point of doing AoC with Haskell, was to spend sometime programming in a purely functional language, for fun, away from my normal language of choice Rust and C++ if I have too. But in truth I think yesterday would have been a lot easier and more fun in Rust, at least for me :-)

Anyway today was a lot easier and got it done pretty quickly.

split :: String -> Char -> String -> [String]
split [] _ ss | null ss = []
              | otherwise = [ss]
split (x:xs) c ss | c == x = ss : split xs c ""
                  | otherwise = split xs c (ss ++ [x])

parse :: [String] -> [(S.Set String, S.Set String)]
parse = map parse'
    where
        parse' xs = let [fs, as] = split xs '(' ""
                        fs'      = split fs ' ' ""
                        (a:as')  = map (takeWhile (/=')') . dropWhile (==' ')) (split as ',' "")
                    in (S.fromList fs', S.fromList $ drop 9 a:as')

generate foods = valid <$> 
                 M.fromListWith (++) (do (is, as) <- foods
                                         a       <- S.toList as
                                         return (a, [is]))
    where                               
        valid is = S.filter (\g -> all (g `S.member`) is) $ S.unions is

task1 foods = length $ filter (`S.notMember` allValids) $ concatMap (S.toList . fst) foods
 where
  isValid ing = any (\a -> ing `S.member` (generate foods M.! a))
  allValids = S.unions $ map (\(ings, a) -> S.filter (`isValid` a) ings) foods

task2 = intercalate "," . map (S.elemAt 0 . snd) . M.toAscList . go . generate
   where
    -- Just like day 16 find foods which contain a particular allergen and repeat
    -- though a process of elimination
    go :: M.Map String (S.Set String) -> M.Map String (S.Set String)
    go v
      | all (\s -> S.size s == 1) (M.elems v) = v
      | otherwise = let found = S.unions $ M.elems $ M.filter (\s -> S.size s == 1) v
                    in go $ M.map (\s -> if S.size s == 1 then s else s S.\\ found) v

main = do
    is <- readFile "day21_input" <&> lines <&> parse
    print (task1 is)
    print (task2 is)