146 lines
4.9 KiB
Rust
146 lines
4.9 KiB
Rust
use std::io::BufRead;
|
|
use std::str::FromStr;
|
|
use std::collections::{HashMap, HashSet};
|
|
|
|
#[derive(PartialEq, Debug)]
|
|
struct Rule {
|
|
colour: String,
|
|
content: HashMap<String, usize>
|
|
}
|
|
|
|
impl FromStr for Rule {
|
|
type Err = ();
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let mut split = s.split(" contain ");
|
|
let colour = split.next().map(|c| c.rsplitn(2, ' ').skip(1).next()).flatten().unwrap().to_string();
|
|
let content = match split.next().unwrap().trim_matches('.') {
|
|
"no other bags" => HashMap::new(),
|
|
bags => {
|
|
bags.split(", ").map(|bag| {
|
|
let mut it = bag.splitn(2, ' ');
|
|
let count = it.next().map(|c| c.parse::<usize>().ok()).flatten().unwrap();
|
|
let colour = it.next().map(|c| c.rsplitn(2, ' ').skip(1).next()).flatten().unwrap().to_string();
|
|
(colour, count)
|
|
}).collect()
|
|
}
|
|
};
|
|
Ok(Rule {
|
|
colour,
|
|
content
|
|
})
|
|
}
|
|
}
|
|
|
|
|
|
pub fn part1<F: BufRead> (input: F) {
|
|
let rules: Vec<_> = input.lines()
|
|
.map(|line| line.unwrap().parse::<Rule>().unwrap())
|
|
.collect();
|
|
let mut backref = HashMap::<String, HashSet<String>>::new();
|
|
|
|
for rule in rules.iter() {
|
|
for colour in rule.content.keys() {
|
|
let entry = backref.entry(colour.to_string()).or_insert(HashSet::new());
|
|
entry.insert(rule.colour.clone());
|
|
}
|
|
}
|
|
|
|
let mut stack: Vec<String> = backref.get("shiny gold").unwrap().iter().map(String::to_owned).collect();
|
|
let mut visited = HashSet::<String>::new();
|
|
|
|
while stack.len() > 0 {
|
|
let item = stack.pop().unwrap();
|
|
if !visited.contains(&item) {
|
|
visited.insert(item.clone());
|
|
if let Some(parents) = backref.get(&item) {
|
|
for parent in parents.iter() {
|
|
stack.push(parent.to_string());
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
println!("{:?}", visited.len());
|
|
}
|
|
|
|
fn count_bags(ruleset: &HashMap<String, HashMap<String, usize>>, bag: &str) -> usize {
|
|
let rules = ruleset.get(bag).unwrap();
|
|
rules.iter().map(|(colour, count)| count * (count_bags(ruleset, colour) + 1)).sum()
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (input: F) {
|
|
let rules: HashMap<_, _> = input.lines()
|
|
.map(|line| line.unwrap().parse::<Rule>().unwrap())
|
|
.map(|rule| (rule.colour, rule.content))
|
|
.collect();
|
|
|
|
println!("{:?}",count_bags(&rules, "shiny gold"));
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
#[test]
|
|
pub fn test_parse() {
|
|
let inputs = [
|
|
"light red bags contain 1 bright white bag, 2 muted yellow bags.",
|
|
"bright white bags contain 1 shiny gold bag.",
|
|
"dotted black bags contain no other bags.",
|
|
];
|
|
let expected = [
|
|
Rule {
|
|
colour: "light red".into(),
|
|
content: [("bright white".to_string(), 1), ("muted yellow".to_string(), 2)].iter().map(|v| v.to_owned()).collect()
|
|
},
|
|
Rule {
|
|
colour: "bright white".into(),
|
|
content: [("shiny gold".to_string(), 1)].iter().map(|v| v.to_owned()).collect()
|
|
},
|
|
Rule {
|
|
colour: "dotted black".into(),
|
|
content: HashMap::new()
|
|
}
|
|
];
|
|
|
|
for (input, expected) in inputs.iter().zip(expected.iter()) {
|
|
assert_eq!(input.parse::<Rule>().unwrap(), *expected);
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_count1() {
|
|
let input = r#"light red bags contain 1 bright white bag, 2 muted yellow bags.
|
|
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
|
|
bright white bags contain 1 shiny gold bag.
|
|
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
|
|
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
|
|
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
|
|
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
|
|
faded blue bags contain no other bags.
|
|
dotted black bags contain no other bags."#.as_bytes();
|
|
let rules: HashMap<_, _> = input.lines()
|
|
.map(|line| line.unwrap().parse::<Rule>().unwrap())
|
|
.map(|rule| (rule.colour, rule.content))
|
|
.collect();
|
|
|
|
assert_eq!(32, count_bags(&rules, "shiny gold"));
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_count2() {
|
|
let input = r#"shiny gold bags contain 2 dark red bags.
|
|
dark red bags contain 2 dark orange bags.
|
|
dark orange bags contain 2 dark yellow bags.
|
|
dark yellow bags contain 2 dark green bags.
|
|
dark green bags contain 2 dark blue bags.
|
|
dark blue bags contain 2 dark violet bags.
|
|
dark violet bags contain no other bags."#.as_bytes();
|
|
let rules: HashMap<_, _> = input.lines()
|
|
.map(|line| line.unwrap().parse::<Rule>().unwrap())
|
|
.map(|rule| (rule.colour, rule.content))
|
|
.collect();
|
|
|
|
assert_eq!(126, count_bags(&rules, "shiny gold"));
|
|
}
|
|
}
|