Advent of Code: Day 21: Allergen Assessment

21st of December 2020 |

4 - 5 minutes

Introduction

Todays puzzle was a nice easy one, especially since I solved part two as part of my solution for part one!

For task one we are asked to determine which Ingredients do not contain any allergens and to return how many times they are present. For task two we must determine which ingredients contain which allergens and return an list alphabetically sorted by the allergan name.

Reading in the data

The data was read into arrays of arrays where the first sub array contained the ingredients and the second the allergens.

Python Copy

def read_data(path):
    dataset = []
    with open(path) as f:
        for line in f.readlines():
            tmp = []
            line = line.split("(")
            tmp.append(line[0].strip().split())
            tmp.append(line[1].strip()[9:-1].split(", "))
            dataset.append(tmp)
    return dataset

The Solution

I used a defaultdict to list the allergan and a list of all ingredients that could be responsible. I then use an intersection to find any ingredients that are present in all the foods that contain that allergan. We then use the Hopcroft Karp Matching algorithm to match each allergan to a single ingredient. For part one we just count all ingredients that are not allergens and for part two we sort the allergan list and return it.

Python Copy

def task_one_and_two(dataset):
    allergens = defaultdict(list)
    for ingredients, allergens_in_ingredients in dataset:
        for allergen in allergens_in_ingredients:
            allergens[allergen].append(ingredients)

    for name, possibles in allergens.items():
        suspect_ingredients = set(possibles[0]).intersection(*possibles[1:])
        allergens[name] = suspect_ingredients

    network = []
    for name, ingredients in allergens.items():
        for ingredient in ingredients:
            network.append((name, ingredient))

    allergen_names = allergens.keys()

    network = nx.Graph(network)
    matching = hopcroft_karp_matching(network)

    allergens_part1 = [match[1] for match in matching.items() if match[0] in allergen_names]
    allergens_part2 = [match for match in matching.items() if match[0] in allergen_names]

    all_ingredients = [i for ingredient in dataset for i in ingredient[0]]
    non_allergens = [i for i in all_ingredients if i not in allergens_part1]
    task_2 = ",".join([ingredient[1] for ingredient in sorted(allergens_part2, key=lambda x: x[0])])

    return len(non_allergens), task_2

Links

Leaderboard Code: 353270-1fc6ef28

Github Repository A link to the github repo containing all the days.

main.py A direct download of the main.py script

1.8Kb

Advent of Code: Day 21: Allergen Assessment

Introduction

Task One and Two

Reading in the data

The Solution

Links