<jupyter_start><jupyter_text>Day 21 - set operations* https://adventofcode.com/2020/day/21We are asked to figure out what ingredients are allergens. We can solve this using [set operations](https://docs.python.org/3/library/stdtypes.htmlset-types-set-frozenset); for any allergen name, intersect all the sets of ingredients for the foods where the allergen appears.We also need to count the ingredients that are not allergens. A `Counter` can take care of that.<jupyter_code>from collections import Counter
from dataclasses import dataclass
from typing import Set

@dataclass
class Food:
    ingredients: Set
    allergens: Set
    
    def __str__(self):
        return (
            f"{' '.join(sorted(self.ingredients))} "
            f"(contains {', '.join(self.allergens)})"
        )
    
    @classmethod
    def from_line(cls, line):
        ingr, _, allergens = line.partition(" (contains ")
        return cls(frozenset(ingr.split()), frozenset(allergens.rstrip(")").split(", ")))


def identify_allergens(foods):
    candidates = {}
    ingredients = Counter()
    for f in foods:
        ingredients.update(f.ingredients)
        for allergen in f.allergens:
            candidates.setdefault(allergen, f.ingredients)
            candidates[allergen] &= f.ingredients
    
    allergens = {}
    while candidates:
        allergen, (ingr,) = min(candidates.items(), key=lambda ac: len(ac[1]))
        allergens[allergen] = ingr
        del ingredients[ingr]
        del candidates[allergen]
        candidates = {a: ic - {ingr} for a, ic in candidates.items()}
    return allergens, sum(ingredients.values())


test_foods = [Food.from_line(line) for line in """\
mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)
""".splitlines()]

assert identify_allergens(test_foods)[1] == 5
import aocd
foods = [Food.from_line(l) for l in aocd.get_data(day=21, year=2020).splitlines()]
allergens, ingr_count = identify_allergens(foods)
print("Part 1:", ingr_count)<jupyter_output>Part 1: 2324<jupyter_text>Part 2I inadvertently did most of the work for part 2 in part 1 already: sorting out what allergen goes with what ingredient, simply using the same techniques as we used for the train ticket data on [day 16](./Day%2016.ipynb).<jupyter_code>canonical = [allergens[n] for n in sorted(allergens)]
print("Part 2:", ",".join(canonical))<jupyter_output>Part 2: bxjvzk,hqgqj,sp,spl,hsksz,qzzzf,fmpgn,tpnnkc
{'fraction_non_alphanumeric': 0.11292897047086992, 'fraction_numerical': 0.013966480446927373, 'mean_word_length': 3.925343811394892, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '84662', 'license': 'MIT', 'n_tokens_mistral': 859, 'n_tokens_neox': 823, 'n_words': 232, 'path': '2020/Day 21.ipynb', 'repo_name': 'AwesomeGitHubRepos/adventofcode', 'size': '2506'}