advent of code, haskell

Advent of Code 2020 day 21

After the complexity of day 20, the solution to day 21 was confusingly simple. I repeatedly tried to solve it, got myself tied in knots, realised what I was doing was simpler than I thought, and tried again. The key, eventually, lay in the data structures.

A Food comprises a set of Ingredients and a set of Allergens. The key data structure is the CandidateIngredients, a map from an allergen to the ingredients that could contain it.

type Ingredient = String
type Allergen = String
data Food = Food 
  { ingredients :: S.Set Ingredient
  , allergens :: S.Set Allergen
  } deriving (Show, Eq)

type CandidateIngredients = M.Map Allergen (S.Set Ingredient)

Parsing the input is simple enough.

foodsP = foodP `sepBy` endOfLine
foodP = Food <$> ingredientsP <* " (contains " <*> allergensP <* ")"

ingredientsP = S.fromList <$> (many1 letter) `sepBy` (many1 space)
allergensP = S.fromList <$> (many1 letter) `sepBy` (string ", ")

Finding candidate ingredients

The first step is to identify the candidate ingredients, the ingredients that could contain each allergen. From the example foods

  • mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
  • trh fvjkl sbzzf mxmxvkd (contains dairy)
  • sqjhc fvjkl (contains soy)
  • sqjhc mxmxvkd sbzzf (contains fish)

I can create one CandidateIngredients map for each food:

  • dairy → {mxmxvkd, kfcds, sqjhc, nhms} ; fish → {mxmxvkd, kfcds,sqjhc, nhms}
  • dairy → {trh, fvjkl, sbzzf, mxmxvkd}
  • soy → {sqjhc, fvjkl}
  • fish → {sqjhc, mxmxvkd, sbzzf}

If I combine the information about the first two foods, I don't gain any more information about which ingredients could contain fish. But I do now know that the ingredient that contains dairy must be in both sets of ingredients for dairy: it must be one of {mxmxvkd, kfcds, sqjhc, nhms} ∩ {trh, fvjkl, sbzzf, mxmxvkd} = {mxmxvkd}. If I combine all four of those CandidateIngredient maps, finding hte intersections of ingredients for each allergen, I end up with a single map showing the possible ingredients for each allergen.

  • dairy → {mxmxvkd} ; fish → {mxmxvkd, sqjhc} ; soy → {fvjkl, sqjhc}

Creating a CandidateIngredients map for a single food is a one-liner, as is combining the maps into the final map.

candidates = M.unionsWith S.intersection $ map allergenMap foods

allergenMap :: Food -> CandidateIngredients
allergenMap food = M.fromList $ S.toList $ S.map (, ingredients food) $ allergens food

It took me a while to realise the solution to this problem was a simple as this!

Solving the tasks

Given the candiates, both tasks become very simple.

For part 1, I remove the unsafe ingredients from each food, count how many are left, and sum the results.

part1 candidates foods = sum $ map countSafe foods
  where possibleAllergens = S.unions $ M.elems candidates
        countSafe food = S.size $ (ingredients food) `S.difference` possibleAllergens

Part 2 is an even simpler constraint satisfaction problem than day 16: allocate one ingredient to each allergen so that each allergen has a distinct ingredient. I just reused that CSP solution:

part2 candidates = intercalate "," $ map snd $ sortOn fst assignments
  where assignments = knownAllergens candidates

knownAllergens :: CandidateIngredients -> [(Allergen, Ingredient)]
knownAllergens candidates = zip allergens assignedIngredients 
  where 
    (allergens, possibleIngredients) = unzip $ M.toList candidates
    assignedIngredients = solveAllergens $ map S.toList possibleIngredients

solveAllergens :: [[Ingredient]] -> [Ingredient]
solveAllergens possibleIngredients = oneCSPSolution $ do
  dvs <- mapM mkDV possibleIngredients
  mapAllPairsM_ (constraint2 (/=)) dvs
  return dvs

Code

You can find the code here or on GitLab.