aoc-2020-day-21.hs

p2.hs

{-# LANGUAGE OverloadedStrings #-}

module Main where

import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import qualified Data.Set as S
import qualified Data.Map.Strict as M
import Data.List (sortOn)

parseLine item =
  let
    [ingredients, allergens] = T.splitOn " (contains " item
  in
    (
      T.splitOn " " ingredients,
      T.splitOn ", " $ T.init allergens
    )

possibleAllergens = foldr determineByAllergens M.empty
  where
    determineByAllergens (ingredients, allergens) g = foldr (determineForFoods ingredients) g allergens

    determineForFoods ingredients allergen g | M.member allergen g =
      M.adjust (S.intersection (S.fromList ingredients)) allergen g

    determineForFoods ingredients allergen g =
      M.insert allergen (S.fromList ingredients) g

reduce possible =
  if reduced' == possible
  then reduced'
  else reduce reduced'

  where
    reduced' = M.map (\vs -> if length vs == 1 then vs else vs S.\\ singles) possible

    singles = S.unions $ M.elems $ M.filter ((== 1) . length) possible

canon = T.intercalate "," . concatMap (S.toList . snd) .  sortOn fst . M.toList

main = do
  food <- T.splitOn "\n" . T.strip <$> TIO.readFile "./d21.txt"
  print $ canon $ reduce $ possibleAllergens $ fmap parseLine food