21.2.py

import re
import numpy as np
from math import prod
with open('input/21.txt') as f:
  content = [line.strip() for line in f.readlines()]

foods = {}
allergens = {}
ingredient_names = set()
all_ingredients = []
for x, line in enumerate(content):
  foods[x] = {}
  allergen_index = line.index('(')
  foods[x]['ingredients'] = line[:allergen_index].split()
  ingredient_names.update(set(foods[x]['ingredients']))
  all_ingredients.extend(foods[x]['ingredients'])
  foods[x]['allergens'] = line[allergen_index+len('contains ')+1:-1].split(', ')

# build up our allergens with possible values
for i, food in foods.items():
  for allergen in food['allergens']:
    if allergen not in allergens:
      allergens[allergen] = set(food['ingredients'])
    else:
      allergens[allergen] = allergens[allergen].intersection(set(food['ingredients']))

# sort them by length of possibilities, should begin with a 1:1 match
sorted_allergens = [(k, allergens[k]) for k in sorted(allergens, key=lambda a: len(allergens[a]))]
while any(len(v) > 1 for v in allergens.values()):
  for allergen, ingredients in sorted_allergens:
    # allergen, ingredient = [(i, next(iter(v))) for i, v in allergens.items() if len(v) == 1][0]
    if len(ingredients) == 1:
      ingredient = next(iter(ingredients))
      # remove ingredient from other allergens
      for a in allergens.keys():
        if a == allergen:
          continue
        try:
          allergens[a].remove(ingredient)
        except:
          continue

# find the safe ingredients
for i, food in foods.items():
  for allergen, ingredients in allergens.items():
    ingredient = next(iter(ingredients))
    if ingredient in all_ingredients:
      all_ingredients = list(filter(lambda a: a != ingredient, all_ingredients))

# get a simpler dictionary of allergen:ingredient
new = {str(key): next(iter(value)) for key, value in allergens.items()}
# sort keys alphabetically
sorted_ingredients = sorted(allergens.keys(), key=lambda x:x.lower())
# get equivalent ingredient names (foreign)
values = []
for key in sorted_ingredients:
  values.append(new[key])
print(','.join(values))