allergen assessment

approach

each food line is parsed with a regex into its ingredient list and allergen list. the foods are grouped by allergen, and for each allergen the candidate ingredients are the intersection of every food that lists it: the ingredient carrying it has to appear in all of them.

simplify then resolves the candidates with a min-heap keyed on how many candidates each allergen has. while the smallest set has exactly one ingredient, it pops it, fixes that pairing, removes the ingredient from every other set and re-heapifies. part 1 counts the appearances of ingredients that never got an allergen. part 2 sorts the resolved ingredients by their allergen name and joins them with commas.

the trick

intersect per allergen, then keep peeling off the allergen with a single candidate and removing it from the rest.

    while h and h[0][0] == 1:
        c, s, a = heappop(h)
        ing = s.pop()
        simp[ing] = a
        for i in range(len(h)):
            c, s, a = h[i]
            h[i] = (c - (ing in s), s - {ing}, a)
        heapify(h)