115 lines
3.5 KiB
Rust
115 lines
3.5 KiB
Rust
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::*;
|
|
}
|