use std::collections::{BTreeMap, HashMap, HashSet};

const INPUT: &str = include_str!("../../data/day21");

struct FoodDescription<'a> {
    ingredients: HashSet<&'a str>,
    allergens: HashSet<&'a str>,
}

impl<'a> FoodDescription<'a> {
    fn parse(line: &'a str) -> Self {
        let pos = line.find(" (contains ").unwrap();
        let ingredients = &line[..pos];
        let allergens = line[pos..].strip_prefix(" (contains ").unwrap().strip_suffix(")").unwrap();
        FoodDescription {
            ingredients: ingredients.split_whitespace().collect(),
            allergens: allergens.split(", ").collect(),
        }
    }
}

fn main() {
    let fds = INPUT.lines().map(FoodDescription::parse).collect::<Vec<_>>();
    let allergens: HashSet<&str> = fds.iter().map(|fd| fd.allergens.iter().cloned()).flatten().collect();
    let mut allergen_map_poss: HashMap<&str, HashSet<&str>> = allergens.iter().map(|&a| {
        let mut is = fds.iter()
        .filter(|fd| fd.allergens.contains(a))
        .map(|fd| &fd.ingredients);
        let first_ingr: HashSet<&str> = is.next().unwrap().clone();
        let poss = is.fold(first_ingr, |memo, ingr| {
            memo.intersection(ingr).cloned().collect::<HashSet<_>>()
        });
        (a, poss)
    }).collect();
    let mut allergen_map: BTreeMap<&str, &str> = BTreeMap::new();
    while !allergen_map_poss.is_empty() {
        let (next_allg, next_ingr) = allergen_map_poss.iter().filter_map(|(&a, is)| {
            if is.len() == 1 {
                Some((a, *is.iter().next().unwrap()))
            } else {
                None
            }
        }).next().unwrap();
        allergen_map.insert(next_allg, next_ingr);
        allergen_map_poss.remove(next_allg);
        for ingr in allergen_map_poss.values_mut() {
            ingr.remove(next_ingr);
        }
    }
    println!("Allergens contained by ingredients: {:?}", allergen_map);
    let all_ingredients: HashSet<&str> = allergen_map.values().cloned().collect();
    println!(
        "Ingredients not allergens used {} times",
        fds.iter().map(|fd| fd.ingredients.difference(&all_ingredients).count()).sum::<usize>(),
    );
    println!("Dangerous ingredients: {}", allergen_map.values().cloned().collect::<Vec<_>>().join(","));
}