| 1234567891011121314151617181920212223242526272829303132333435363738394041 |
- #!/usr/bin/env python3
- import sys
- def parse(f):
- for line in f:
- ingredients, allergens = line[:-2].split(' (contains ')
- yield ingredients.split(), allergens.split(', ')
- def allergen_candidates(foods):
- candidates = {}
- known = set()
- for ingredients, allergens in foods:
- unknown = set(ingredients) - known
- for a in allergens:
- cand = candidates.get(a, None)
- if not cand:
- cand = candidates[a] = set(unknown)
- elif len(cand) > 1:
- cand &= unknown
- if len(cand) == 1:
- known |= cand
- unknown -= cand
- return candidates
- def count_safe(foods, candidates):
- maybe_unsafe = set.union(*candidates.values())
- return sum(len(set(ing) - maybe_unsafe) for ing, _ in foods)
- def translate_allergens(foods, candidates):
- unsafe = {}
- while candidates:
- found = {c.pop(): a for a, c in candidates.items() if len(c) == 1}
- unsafe.update(found)
- known = set(found)
- candidates = {a: c - known for a, c in candidates.items() if c}
- return sorted(unsafe, key=unsafe.__getitem__)
- foods = list(parse(sys.stdin))
- candidates = allergen_candidates(foods)
- print(count_safe(foods, candidates))
- print(','.join(translate_allergens(foods, candidates)))
|
