Added solution for part 1 of day 21

askrepps · askrepps · commit aa503dea6c7b · 2021-11-26T09:41:29.000-05:00
diff --git a/advent2020/day21.py b/advent2020/day21.py
@@ -0,0 +1,101 @@
+# MIT License
+#
+# Copyright (c) 2021 Andrew Krepps
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to deal
+# in the Software without restriction, including without limitation the rights
+# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall be included in all
+# copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+
+
+from . import util
+
+
+def parse_input(lines):
+    foods = []
+    for line in lines:
+        overall_parts = line.split(" (contains ")
+        ingredients = set(token.strip() for token in overall_parts[0].split())
+        allergens = set(token.strip() for token in overall_parts[1].replace(')', '').split(", "))
+        foods.append((ingredients, allergens))
+    return foods
+
+
+def get_all_ingredients(foods):
+    return set(ingredient for food in foods for ingredient in food[0])
+
+
+def get_all_allergens(foods):
+    return set(allergen for food in foods for allergen in food[1])
+
+
+def get_ingredient_appearances_by_allergen(foods, all_allergens):
+    ingredients_by_allergen = {allergen: set() for allergen in all_allergens}
+    for ingredients, allergens in foods:
+        for allergen in allergens:
+            for ingredient in ingredients:
+                ingredients_by_allergen[allergen].add(ingredient)
+    return ingredients_by_allergen
+
+
+def get_allergens_by_ingredient(foods, all_ingredients, all_allergens):
+    my_ingredients = set(all_ingredients)
+    my_allergens = set(all_allergens)
+    ingredient_allergens = {ingredient: None for ingredient in my_ingredients}
+    searching = True
+    while searching:
+        searching = False
+        for allergen in my_allergens:
+            possible_ingredients = set(my_ingredients)
+            for food_ingredients, food_allergens in foods:
+                if allergen in food_allergens:
+                    possible_ingredients.intersection_update(food_ingredients)
+            if len(possible_ingredients) == 1:
+                ingredient = possible_ingredients.pop()
+                ingredient_allergens[ingredient] = allergen
+                my_ingredients.remove(ingredient)
+                my_allergens.remove(allergen)
+                searching = True
+                break
+    return ingredient_allergens
+
+
+def count_ingredient_appearances(foods, ingredients):
+    count = 0
+    for food_ingredients, _ in foods:
+        for food_ingredient in food_ingredients:
+            if food_ingredient in ingredients:
+                count += 1
+    return count
+
+
+def get_part1_answer(lines):
+    foods = parse_input(lines)
+    all_ingredients = get_all_ingredients(foods)
+    all_allergens = get_all_allergens(foods)
+    allergens_by_ingredient = get_allergens_by_ingredient(foods, all_ingredients, all_allergens)
+    safe_ingredients = [ingredient for ingredient, allergen in allergens_by_ingredient.items() if allergen is None]
+    return count_ingredient_appearances(foods, safe_ingredients)
+
+
+def get_part2_answer(lines):
+    return None
+
+
+def run():
+    lines = util.get_input_file_lines("day21.txt")
+    print(f"The answer to part 1 is {get_part1_answer(lines)}")
+    print(f"The answer to part 2 is {get_part2_answer(lines)}")
diff --git a/main.py b/main.py
@@ -43,6 +43,7 @@
 from advent2020 import day18
 from advent2020 import day19
 from advent2020 import day20
+from advent2020 import day21
 
 
 day_runners = [
@@ -65,7 +66,8 @@
     lambda: day17.run(),
     lambda: day18.run(),
     lambda: day19.run(),
-    lambda: day20.run()
+    lambda: day20.run(),
+    lambda: day21.run()
 ]
 
 
diff --git a/test/test_day21.py b/test/test_day21.py
@@ -0,0 +1,43 @@
+# MIT License
+#
+# Copyright (c) 2021 Andrew Krepps
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to deal
+# in the Software without restriction, including without limitation the rights
+# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall be included in all
+# copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+
+
+import unittest
+
+from advent2020.day21 import get_part1_answer
+from advent2020.day21 import get_part2_answer
+from advent2020.util import get_input_data_lines
+
+
+data = """
+mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
+trh fvjkl sbzzf mxmxvkd (contains dairy)
+sqjhc fvjkl (contains soy)
+sqjhc mxmxvkd sbzzf (contains fish)
+"""
+
+
+class Day21Test(unittest.TestCase):
+    def test_day21(self):
+        lines = get_input_data_lines(data)
+        self.assertEqual(get_part1_answer(lines), 5)
+        self.assertEqual(get_part2_answer(lines), None)
