advent2020-day21.py

from collections import namedtuple, defaultdict

from pprint import pprint

#filename = 'small_input.txt'
filename = 'input.txt'


Recipe = namedtuple('Recipe', 'ingr allerg')
recipes = []

with open(filename) as f:
    for line in f:
        # mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
        allergs = set()
        if ' (contains ' in line:
            ingr, allerg = line.strip().strip(')').split(' (contains ')
            ingr = set(ingr.strip().split())
            allerg = set(allerg.split(', '))
        else:
            ingr = set(line.strip().split())
        recipes.append(Recipe(ingr, allerg))


allergens = defaultdict(list)
ingredients = defaultdict(int)
not_possible_ingr = set()
for i, recipe in enumerate(recipes):
    for al in recipe.allerg:
        allergens[al].append(i)
    for ingr in recipe.ingr:
        ingredients[ingr] += 1
    not_possible_ingr |= recipe.ingr


allergen_ingr = {}   # allerg -> possible ingr set


for allerg in allergens:
    possible = set(recipes[allergens[allerg][0]].ingr) if allergens[allerg] else set()
    for recipe in allergens[allerg]:
        possible &= recipes[recipe].ingr
    allergen_ingr[allerg] = possible
    not_possible_ingr -= possible

change = True
while change == True:
    change = False
    for allerg in allergen_ingr:
        if len(allergen_ingr[allerg]) == 1:
            ingr = next(iter(allergen_ingr[allerg]))
            for other_allerg in allergen_ingr:
                if allerg == other_allerg or ingr not in allergen_ingr[other_allerg]:
                    continue
                allergen_ingr[other_allerg] -= allergen_ingr[allerg]
                change = True

pprint(allergen_ingr)

# Part I
print(sum(ingredients[ingr] for ingr in not_possible_ingr))
# Part II
print(','.join(list(list(i)[0] for a, i in sorted(allergen_ingr.items(),key=lambda x: x[0]))))