Day 21: Allergen Assessment

public override string SolvePart1()
{
	var safeFoods = new HashSet<string>();
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input21))
	{
		string line;
		var allergyDb = new Dictionary<string, HashSet<string>>();
		while ((line = fs.ReadLine()) != null)
		{
			var foods = line.Substring(0, line.IndexOf('(')).Split(' ');
			safeFoods.UnionWith(foods);

			var allergens = line[(line.IndexOf('(') + 10)..^1].Split(',').Select(s => s.Trim()).ToList();

			foreach (var allergen in allergens)
			{
				if (allergyDb.ContainsKey(allergen))
				{
					allergyDb[allergen].IntersectWith(foods);
				}
				else
				{
					allergyDb.Add(allergen, foods.ToHashSet());
				}
			}
		}
		foreach (var dangerous in allergyDb.Values)
		{
			safeFoods.ExceptWith(dangerous);
		}
	}

	var count = 0;
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input21))
	{
		string line;
		while ((line = fs.ReadLine()) != null)
		{
			var foods = line.Substring(0, line.IndexOf('(')).Split(' ');
			count += foods.Count(f => safeFoods.Contains(f));
		}
	}

	return $"{count} safe foods in the list";
}

public override string SolvePart2()
{
	var safeFoods = new HashSet<string>();
	var allergyDb = new Dictionary<string, HashSet<string>>();
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input21))
	{
		string line;
		while ((line = fs.ReadLine()) != null)
		{
			var foods = line.Substring(0, line.IndexOf('(') - 1).Split(' ');
			safeFoods.UnionWith(foods);

			var allergens = line[(line.IndexOf('(') + 10)..^1].Split(',').Select(s => s.Trim()).ToList();

			foreach (var allergen in allergens)
			{
				if (allergyDb.ContainsKey(allergen))
				{
					allergyDb[allergen].IntersectWith(foods);
				}
				else
				{
					allergyDb.Add(allergen, foods.ToHashSet());
				}
			}
		}
		foreach (var dangerous in allergyDb.Values)
		{
			safeFoods.ExceptWith(dangerous);
		}
	}

	var finalList = new List<(string, string)>();
	while (allergyDb.Count > 0)
	{
		var known = allergyDb.First(kv => kv.Value.Count == 1);
		finalList.Add((known.Key, known.Value.Single()));
		allergyDb.Remove(known.Key);
		foreach(var other in allergyDb.Values)
		{
			other.Remove(known.Value.Single());
		}
	}

	finalList.Sort(CompareStringTuplesByFirst);

	var dangerousList = finalList.Select(kv => kv.Item2).Aggregate((s1, s2) => s1 + "," + s2);


	return dangerousList;
}

private static int CompareStringTuplesByFirst((string, string) first, (string, string) second)
{
	return first.Item1.CompareTo(second.Item1);
}

I swear, the word "exactly" got added to the puzzle description (in "Each allergen is found in exactly one ingredient") when I refreshed the page. I was staring at the example and couldn't figure out a damn thing to do with it, but then I refreshed and re-read and it became clear. I basically started trying to solve (what I was guessing) was Part 2, and then hand to argue myself into the fact that all the ingredients not in the possible-allergens list must be impossible. I'm still not 100% convinced, but I couldn't find a counterexample by hand, at least.

Part 2 was just going through the possibles, finding a unique solution, and subtracting it off from all the others. I almost feel like this step is worth generalizing at this point.

import re

with open("input.txt") as input_file:
    foods = [{"names":  re.findall(r'(.+) \(', food)[0].split(" "), "allergens": re.findall(r'\(contains (.+)\)', food)[0].split(", ")}
             for food in input_file.read().split("\n")]


def get_allergens(foods):
    allergens = []
    for food in foods:
        for allergen in food["allergens"]:
            if not allergen in allergens:
                allergens.append(allergen)
    return allergens


def get_names(foods):
    names = []
    for food in foods:
        for name in food["names"]:
            if not name in names:
                names.append(name)
    return names


def possibilities(foods):

    allergens = get_allergens(foods)
    names = get_names(foods)

    # for it to be possible for an allergen to be present in a food,
    # the food has to appear in each listing that has the allergen
    possibilities = {}
    for name in names:
        for allergen in allergens:
            possibilities[name] = []
            for allergen in allergens:
                present = True
                for food_test in foods:
                    if allergen in food_test["allergens"] and not name in food_test["names"]:
                        present = False
                        break
                if present and not allergen in possibilities[name]:
                    possibilities[name].append(allergen)

    count = 0
    for name in possibilities:
        if not possibilities[name]:
            for food in foods:
                if name in food["names"]:
                    count += 1
    print("Appearances of foods with no allergens in lists:", count)
    return possibilities


def identify_dangerous(possibilities):
    dangerous = dict(
        filter(lambda name: not name[1] == [], possibilities.items()))
    identified = []
    last_identified_count = -1
    while last_identified_count < len(identified):
        last_identified_count = len(identified)
        for name in dangerous:
            if len(dangerous[name]) > 1:
                for allergen in identified:
                    if allergen in dangerous[name]:
                        dangerous[name].remove(allergen)
            if len(dangerous[name]) == 1:
                identified_allergen = dangerous[name][0]
                if not identified_allergen in identified:
                    identified.append(dangerous[name][0])
    dangerous = dict(sorted(dangerous.items(), key=lambda food: food[1]))

    print("Canonical dangerous ingredient list:")
    print(",".join(dangerous.keys()))
    return dangerous


possibilities = possibilities(foods)
identify_dangerous(possibilities)

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

fn day21(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    let mut allergen_possibilities: HashMap<String,Vec<String>> = HashMap::new(); 

    // Build map of allergens and possible ingredients for each
    for line in &input {
        let line = line.replace("(","").replace(")","").replace(",","");
        let parts = line.split("contains").collect::<Vec<_>>();
        let ingredients = parts[0].split_ascii_whitespace().collect::<Vec<_>>();
        let allergens   = parts[1].split_ascii_whitespace().collect::<Vec<_>>();
        for allergen in &allergens {
            let current = allergen_possibilities.entry(allergen.to_string()).or_insert(Vec::new());
            for ingr in &ingredients {
                current.push(ingr.to_string());
            }
        }
    }

    // Deduplicate ingredients
    let keys = allergen_possibilities.clone();
    let keys = keys.keys();
    for key in keys {
        if let Some(x) = allergen_possibilities.get_mut(key) {
            x.sort();
            x.dedup();
        }
    }

    // Reprocess input to eliminate possibilities from map
    for line in &input {
        let line = line.replace("(","").replace(")","").replace(",","");
        let parts = line.split("contains").collect::<Vec<_>>();
        let ingredients = parts[0].split_ascii_whitespace().collect::<Vec<_>>();
        let allergens = parts[1].split_ascii_whitespace().collect::<Vec<_>>();

        for allergen in &allergens {
            if let Some(current) = allergen_possibilities.get_mut(&allergen.to_string()) {
                // Select ingredients to remove
                let mut remove: Vec<String> = Vec::new();
                for ingr in current.iter() {
                    if &ingredients.iter().filter(|i| i.to_string() == *ingr).count() < &1 {
                        remove.push(ingr.to_string());
                    }
                }
                for rem in remove {
                    let ix = current.iter().position(|x| *x == rem).unwrap();
                    current.remove(ix);
                }
            }
        }
    }

    // List of allergens and possible ingredients
    for (allergen,ingrds) in &allergen_possibilities {
        println!("{}: {:?}", allergen, ingrds);
    }

    // Get unique ingredients from allergen map
    let mut possible_allergens: Vec<String> = Vec::new();
    for (_,ingrds) in allergen_possibilities.iter() {
        for ingr in ingrds {
            possible_allergens.push(ingr.to_string());
        }
    }
    possible_allergens.sort();
    possible_allergens.dedup();

    println!("Allergens: {:?}", possible_allergens);

    // Count instances of non-allergen ingredients
    let mut part1 = 0;
    for line in &input {
        let line = line.replace("(","").replace(")","").replace(",","");
        let parts = line.split("contains").collect::<Vec<_>>();
        let ingredients = parts[0].split_ascii_whitespace().collect::<Vec<_>>();
        for ingr in ingredients {
            if possible_allergens.iter().position(|x| x == ingr).is_none() {
                part1 += 1;
            }
        }
    }
    println!("Part 1: {}", part1); // 2203

    // Part 2
    let num_allergens = possible_allergens.len();
    let allergies = allergen_possibilities.clone();
    let allergies = allergies.keys().collect::<Vec<_>>();
    let mut actuals: HashMap<String,String> = HashMap::new();
    while actuals.len() != num_allergens {
        'allergen_lp: for allergen in allergies.iter() {
            let mut j: String = String::new();
            if let Some(x) = allergen_possibilities.get(allergen.clone()) {
                if x.len() != 1 { continue 'allergen_lp; }
                j = x.iter().next().unwrap().to_string();
                actuals.insert(allergen.to_string(),j.clone());
            }
            for other_allergen in allergies.iter() {
                if other_allergen == allergen { continue; }
                if let Some(x) = allergen_possibilities.get_mut(other_allergen.clone()) {
                    if let Some(ix) = x.iter().position(|a| a == &j) {
                        x.remove(ix);
                    }

                }
            }
        }
    }

    println!("Finals:");
    for (k,v) in &actuals {
        println!("{}: {}", k,v);
    }
    println!();

    let sorted = actuals.clone();
    let mut sorted = sorted.keys().collect::<Vec<_>>();
    sorted.sort();

    let mut part2 = String::new();
    for (i,item) in sorted.iter().enumerate() {
        part2.push_str(&actuals.get(item.clone()).unwrap());
        if i != sorted.len() - 1 { part2.push_str(",");}
    }
    println!("Part 2: {}", part2); // fqfm,kxjttzg,ldm,mnzbc,zjmdst,ndvrq,fkjmz,kjkrm

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day21(&filename).unwrap();
}

To solve this one, I realized you could use set operations to determine which ingredients mapped to which allergens. For instance, anytime you get a listing for say "dairy", you perform the intersection of the current set of possible incredients with the new set. This way, you only get the ingredients in common with the two ingredient lists. At the end of processing all the input, you will then have a table where for each allergen, you will have a set of possible ingredients that map to them.

My main hangups on this were as follows:

1. I started by counting each ingredient instead of just using sets. I realized after viewing the table of counts I created that I could just store the items that appear multiple times and work for there.

2. My first solution actually (unknowingly) tried to solve Part 2 by figuring out the exact mapping of dangerous ingredient to allergen and this lead me down the wrong path as I got the wrong answer for Part 1. Because the website said my answer was too low, I figured I was pruning too much.

3. Once I focused only on solving Part 1, I ran into an infuriating possible Python bug or quirk. For some reason, performing a &= b produced different results from a = a & b. I made a WTF note in my code to mark where this ocurred. This cost me about an hour as I couldn't figure out why my result was too high (wasn't eliminating enough).

import pprint
import collections
import itertools
import re
import sys

# Functions

def process_ingredients_list(stream=sys.stdin):
    all_ingredients = collections.defaultdict(int)
    all_allergens   = {}

    for ingredients, allergens in re.findall(r'(.*)\(contains (.*)\)', stream.read()):
        ingredients = set(ingredients.split())
        allergens   = allergens.split(', ')
        
        for ingredient in ingredients:
            all_ingredients[ingredient] += 1

        for allergen in allergens:
            if allergen in all_allergens:
                # WTF: all_allergens[allergen] &= ingredients produces different results???
                all_allergens[allergen] = all_allergens[allergen] & ingredients
            else:
                all_allergens[allergen] = ingredients

    return all_ingredients, all_allergens

def determine_safe_ingredients(ingredients, allergens):
    return [
        ingredient for ingredient in ingredients if all(ingredient not in bad_ingredients for allergen, bad_ingredients in allergens.items())
    ]

# Main Execution

def main():
    ingredients, allergens = process_ingredients_list()
    safe_ingredients       = determine_safe_ingredients(ingredients, allergens)
    safe_ingredients_count = sum(ingredients[ingredient] for ingredient in safe_ingredients)

    print(safe_ingredients_count)

if __name__ == '__main__':
    main()

Once I got Part 1 successfully completed, then Part 2 was straightforward since I had mistakenly done most of the logic while working on Part 1. The idea is to look for any allergen mappings with only one possible candidate. If you have such a mapping, then that is the dangerous ingredient/allergen combo. Take that ingredient, and remove it as a candidate from all the other allergens and repeat this process until there are no more mappings with only one possible candidate.

--- day21-A.py	2020-12-21 03:16:47.063609335 -0500
+++ day21-B.py	2020-12-21 03:16:24.103569068 -0500
@@ -28,19 +28,31 @@
 
     return all_ingredients, all_allergens
 
-def determine_safe_ingredients(ingredients, allergens):
-    return [
-        ingredient for ingredient in ingredients if all(ingredient not in bad_ingredients for allergen, bad_ingredients in allergens.items())
-    ]
+def determine_dangerous_ingredients(ingredients, allergens):
+    dangerous_ingredients = {}
+
+    while any(len(bad_ingredients) == 1 for bad_ingredients in allergens.values()):
+        for allergen, bad_ingredients in allergens.items():
+            if len(bad_ingredients) != 1:
+                continue
+
+            bad_ingredient = list(bad_ingredients)[0]
+            dangerous_ingredients[bad_ingredient] = allergen
+
+            for other_allergen in allergens:
+                allergens[other_allergen] = allergens[other_allergen] - bad_ingredients
+
+    return dangerous_ingredients
 
 # Main Execution
 
 def main():
     ingredients, allergens = process_ingredients_list()
-    safe_ingredients       = determine_safe_ingredients(ingredients, allergens)
-    safe_ingredients_count = sum(ingredients[ingredient] for ingredient in safe_ingredients)
+    dangerous_ingredients  = determine_dangerous_ingredients(ingredients, allergens)
+    canonical_list         = ','.join(sorted(dangerous_ingredients, key=dangerous_ingredients.get))
+
+    print(canonical_list)
 
-    print(safe_ingredients_count)
 
 if __name__ == '__main__':
     main()