January 4, 2021

Advent of Code 2020 day 21

Confusing in its simplicity

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 
    (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


You can find the code here or on GitLab.