day 21

today's one was so much nicer! and the code ran super quickly (at least from a human point of view).

each line this time has a list of ingredients (separated by spaces) followed by the allergens as '(contains x, y, z)'. i started off with the usual input_list and started off with an empty list line_infos and two empty sets: ingredients and allergens.

# input
with open('21.txt', 'r') as file:
    input = file.read()
# turn the input into a list
input_list = list(input.split('\n'))
# get list of line infos
line_infos = []
# and *unique* ingredients and allergens
ingredients = set([])
allergens = set([])

we then fill in line_infos with dicts that have a list of ingredients and a list of allergens, with a lot of uses of .split(), and add any new ingredients/allergens to their respective sets:

while len(input_list) > 0:
    line_info = {}
    line = input_list.pop(0)
    # 'zjgxg nsvfk jpvfc qtc (contains soy, sesame)'
    tmp = line.replace(')','').split(' (contains ')
    # ['zjgxg nsvfk jpvfc qtc', 'soy, sesame']
    line_info['ingredients'] = tmp[0].split(' ')
    # ['zjgxg', 'nsvfk', 'jpvfc', 'qtc']
    line_info['allergens'] = tmp[1].split(', ')
    # ['soy', 'sesame']
    line_infos.append(line_info)
    # now add on any new ingredients/allergens
    ingredients = ingredients.union(set(line_info['ingredients']))
    allergens = allergens.union(set(line_info['allergens']))

 i decided to take on this matching problem (only had to go one-to-one, as each ingredient has at most one allergen and each allergen is present in exactly one ingredient) with a dict whose keys are allergens and whose values are lists of ingredients possibly containing that allergen, and vice versa. for each allergen, the only ingredients that can contain it appear in every list containing this allergen, so we take the intersection of all ingredient lists with this allergen:

allergen_dict = {}
for allergen in allergens:
    allergen_dict[allergen] = ingredients
    # go through each line
    for line_info in line_infos:
        # if this allergen is in this list
        if allergen in line_info['allergens']:
            # add in any new ingredients
            allergen_dict[allergen] = allergen_dict[allergen].intersection(line_info['ingredients'])

similarly, for each ingredient, the only allergens it can contain appear with every list that the ingredient is in:

ingredient_dict = {}
for ingredient in ingredients:
    ingredient_dict[ingredient] = allergens
    # go through each line
    for line_info in line_infos:
        # if this allergen is in this list
        if ingredient in line_info['ingredients']:
            # take intersection
            ingredient_dict[ingredient] = ingredient_dict[ingredient].intersection(line_info['allergens'])

now it's time to start matching! luckily, we can take a naïve approach, as our allergen_dict starts off with an allergen that can only be in one ingredient, and if we remove this allergen from all other ingredients and the ingredient from all other allergens, we get the same again.

ia_pairs starts off as an empty list, to contain tuples (i,a) where ingredient i contains allergen a. while this list has fewer elements than the set of allergens, we go through each allergen. if this allergen hasn't already been matched to an ingredient, we look at the potential set of ingredients that it could be in. if this set only has one ingredient, we can pair these up in ia_pairs, and remove i and a from consideration by removing them from the lists in each dict.

ia_pairs = []
while len(ia_pairs) < len(allergens):
    for a in allergens:
        # if it has not been paired
        if not a in [ia[1] for ia in ia_pairs]:
            # see if this allergen has only one ingredient
            a_ingredients = allergen_dict[a]
            if len(a_ingredients) == 1:
                # add ia pair
                i = list(a_ingredients)[0]
                ia_pairs.append((i, a))
                # remove i from other allergen lists
                for b in [b for b in allergens if not b == a]:
                    if i in allergen_dict[b]:
                        b_ingredients = allergen_dict[b]
                        b_ingredients.remove(i)
                        allergen_dict[b] = b_ingredients
                # remove a from other ingredient lists
                for j in [j for j in ingredients if not j == i]:
                    if a in ingredient_dict[j]:
                        j_allergens = ingredient_dict[j]
                        j_allergens.remove(a)
                        ingredient_dict[j] = j_allergens

part a requires a count of how many times all of the safe ingredients combined appear in the input list. we can do this by taking the list safe_i, containing all ingredients i such that there is no a with (i,a) in ia_pairs, going through each line, and adding on the length of the ingredients list in that line when you include only ingredients in safe_i:

# fill out safe ingredients
safe_i = [i for i in ingredients if not i in [ia[0] for ia in ia_pairs]]
# get part a answer
part_a = 0
for line_info in line_infos:
    # add number of times any safe ingredient appears in this line
    part_a += len([i for i in line_info['ingredients'] if i in safe_i])
print('part a:',part_a)

part b requires a comma-separated list of the unsafe ingredients, ordered alphabetically by their corresponding allergen, so i just turned the set of allergens into a list, sorted it, added the corresponding ingredients into a list in that order, and then joined this list with commas:

# get allergens listed alphabetically
allergens_ordered = sorted(list(allergens))
# put the ingredients in this order
ingredients_ordered = []
for a in allergens_ordered:
    ingredients_ordered += [ia[0] for ia in ia_pairs if ia[1] == a]
# join
part_b = ','.join(ingredients_ordered)
print('part b:',part_b)