zerosleeps

Since 2010

Advent of Code 2020 day 21

Wednesday 23 December 2020

Advent of Code 2020 day 21. I’m out-of-sequence as I skipped day 21 to prioritise day 22 yesterday. As is often the case with Advent of Code, the actual coding was fine once I understood the trick the puzzle was trying to get at. In this instance, it took me ages to understand that an ingredient associated with an allergen must be in all the recipes that contain that allergen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from pathlib import Path
import re
import unittest

def get_raw_input():
    return (Path(__file__).parent/'day_21_input.txt').read_text()

class Food():
    def __init__(self, raw_line):
        self.raw_line = raw_line

    def parse_raw_line(self):
        regexp = re.compile(r'^(?P<ingredients>.*) \(contains (?P<contains>.*)\)$')
        return re.match(regexp, self.raw_line)

    @property
    def ingredients(self):
        return self.parse_raw_line()['ingredients'].split()

    @property
    def contains(self):
        return self.parse_raw_line()['contains'].split(', ')

def build_allergens(foods):
    allergens = {}
    for food in foods:
        for contains in food.contains:
            if contains in allergens:
                allergens[contains] &= set(food.ingredients)
            else:
                allergens[contains] = set(food.ingredients)

    while any([len(ingredients) > 1 for ingredients in allergens.values()]):
        # Find allergents with only one possible ingredient, and remove that
        # ingredient from all other allergens
        for allergen, ingredients in allergens.items():
            if len(ingredients) == 1:
                for update_allergen in allergens:
                    if update_allergen != allergen:
                        allergens[update_allergen] -= ingredients

    return allergens

def build_no_allergens(foods, allergens):
    return [
        ingredient
        for food in foods
        for ingredient in food.ingredients
        if ingredient not in [
            allergen_ingredient
            for allergen in allergens.values()
            for allergen_ingredient in allergen
        ]
    ]

def part_one(raw_input):
    foods = [Food(raw_line) for raw_line in raw_input.strip().splitlines()]
    allergens = build_allergens(foods)
    return len(build_no_allergens(foods,allergens))

def part_two(raw_input):
    foods = [Food(raw_line) for raw_line in raw_input.strip().splitlines()]
    allergens = build_allergens(foods)
    return ','.join([allergens[allergen].pop() for allergen in sorted(allergens)])

class TestPartOne(unittest.TestCase):
    def test_part_one_example(self):
        self.assertEqual(part_one("mxmxvkd kfcds sqjhc nhms (contains dairy, fish)\ntrh fvjkl sbzzf mxmxvkd (contains dairy)\nsqjhc fvjkl (contains soy)\nsqjhc mxmxvkd sbzzf (contains fish)"), 5)

class TestPartTwo(unittest.TestCase):
    def test_part_two_example(self):
        self.assertEqual(part_two("mxmxvkd kfcds sqjhc nhms (contains dairy, fish)\ntrh fvjkl sbzzf mxmxvkd (contains dairy)\nsqjhc fvjkl (contains soy)\nsqjhc mxmxvkd sbzzf (contains fish)"), 'mxmxvkd,sqjhc,fvjkl')

if __name__ == '__main__':
    print(f'Part one: {part_one(get_raw_input())}')
    print(f'Part two: {part_two(get_raw_input())}')