use std::collections::{HashMap, HashSet};
use std::error::Error;
use std::fs::File;
use std::io::{self, BufRead};
use std::vec::Vec;

#[macro_use]
extern crate lazy_static;
extern crate regex;
use regex::Regex;

fn parse_line(line: &str) -> (HashSet<String>, Vec<String>) {
    lazy_static! {
        static ref LINE_RE: Regex = Regex::new(r"^(.*) \(contains (.*)\)").unwrap();
    }
    if let Some(cap) = LINE_RE.captures_iter(&line).nth(0) {
        let ingredients: HashSet<String> =
            cap[1].trim().split(" ").map(|s| s.to_string()).collect();
        let alergens: Vec<String> = cap[2].split(",").map(|s| s.trim().to_string()).collect();
        return (ingredients, alergens);
    } else {
        panic!("Unable to parse line: {}", line);
    };
}

fn main() -> Result<(), Box<dyn Error>> {
    let file = File::open("inputs/day21.txt")?;
    let lines = io::BufReader::new(file).lines().map(|l| l.unwrap());

    let products: Vec<(HashSet<String>, Vec<String>)> = lines.map(|l| parse_line(&l)).collect();
    println!("Products: {:?}", products);

    let mut alergen_canidates: HashMap<String, HashSet<String>> = HashMap::new();
    let mut all_ingreds: HashSet<String> = HashSet::new();

    for (ingreds, alergens) in products.iter() {
        for alergen in alergens.iter() {
            all_ingreds = all_ingreds.union(&ingreds).cloned().collect();

            if alergen_canidates.contains_key(alergen) {
                let smaller_set = ingreds
                    .intersection(&alergen_canidates[alergen])
                    .cloned()
                    .collect();
                alergen_canidates.insert(alergen.to_string(), smaller_set);
            } else {
                alergen_canidates.insert(alergen.to_string(), ingreds.clone());
            }
        }
    }

    println!("Canidates: {:?}", alergen_canidates);
    let mut no_alergen = all_ingreds.clone();
    for canidates in alergen_canidates.values() {
        no_alergen = no_alergen.difference(canidates).cloned().collect();
    }

    println!("No Alergen: {:?}", no_alergen);

    let count = no_alergen
        .iter()
        .map(|na| {
            products
                .iter()
                .map(|(i, _)| if i.contains(na) { 1 } else { 0 })
                .fold(0, |x, y| x + y)
        })
        .fold(0, |x, y| x + y);

    println!("Answer 1: {}", count);

    //
    // Part 2
    //
    let mut canidates = alergen_canidates.clone();
    while canidates.values().any(|names| names.len() > 1) {
        let mut next_canidates: HashMap<String, HashSet<String>> = HashMap::new();
        for singleton in canidates
            .values()
            .filter(|names| names.len() == 1)
            .map(|names| names.iter().nth(0).unwrap())
        {
            for (alergen, names) in canidates.iter() {
                let mut new_names = names.clone();
                if new_names.len() > 1 {
                    new_names.remove(singleton);
                }
                next_canidates.insert(alergen.to_string(), new_names);
            }
        }
        canidates = next_canidates;
    }

    let mut tuples: Vec<(String, String)> = canidates
        .iter()
        .map(|(a, set)| (a.to_string(), set.iter().nth(0).unwrap().to_string()))
        .collect();

    tuples.sort_by(|(a, _), (b, _)| a.partial_cmp(b).unwrap());

    let answer2 = tuples
        .iter()
        .map(|(_, n)| n.to_string())
        .collect::<Vec<String>>()
        .join(",");

    println!("answer2: {}", answer2);
    Ok(())
}

#[cfg(test)]
mod tests {
    use crate::*;
}