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 $ (, 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.

    Neil Smith

    Read more posts by this author.