-
Notifications
You must be signed in to change notification settings - Fork 0
/
07.rs
123 lines (113 loc) · 4.06 KB
/
07.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
use std::collections::BTreeMap;
mod utils;
use utils::unique::*;
type Tree = BTreeMap<String, Vec<(u32, String)>>;
type ReverseTree = BTreeMap<String, Vec<String>>;
fn parse_reverse_rules(input: &str) -> ReverseTree {
input.lines().fold(BTreeMap::new(), |mut rules, rule| {
let mut rule_parts = rule.splitn(2, " contain ");
let parent = rule_parts
.next()
.expect("No parent!")
.to_string()
.replace(" bags", "");
let children = rule_parts.next().expect("No children!");
children
.split(", ")
.filter(|child| child != &"no other bags.")
.for_each(|child| {
rules
.entry(
child
.chars()
.filter(|character| {
character.is_ascii_alphabetic() || character.is_ascii_whitespace()
})
.skip(1)
.collect::<String>()
.replace(" bags", "")
.replace(" bag", ""),
)
.and_modify(|parents| parents.push(parent.clone()))
.or_insert_with(|| vec![parent.clone()]);
});
rules
})
}
fn parse_rules(input: &str) -> Tree {
input.lines().fold(BTreeMap::new(), |mut rules, rule| {
let mut rule_parts = rule.splitn(2, " contain ");
let parent = rule_parts
.next()
.expect("No parent!")
.to_string()
.replace(" bags", "");
let children = rule_parts.next().expect("No children!");
children
.split(", ")
.filter(|child| child != &"no other bags.")
.for_each(|child| {
let child_name = child
.chars()
.filter(|character| {
character.is_ascii_alphabetic() || character.is_ascii_whitespace()
})
.skip(1)
.collect::<String>()
.replace(" bags", "")
.replace(" bag", "");
let child_quantity = child
.chars()
.filter(char::is_ascii_digit)
.collect::<String>()
.parse::<u32>()
.expect("Couldn't parse number!");
rules
.entry(parent.clone())
.and_modify(|children| children.push((child_quantity, child_name.clone())))
.or_insert_with(|| vec![(child_quantity, child_name.clone())]);
});
rules
})
}
fn count_distinct_outer_layers(rules: &ReverseTree, pattern: &str, outers: &mut Vec<String>) {
if let Some(parents) = rules.get(pattern) {
parents.iter().for_each(|parent| {
outers.push(parent.to_string());
count_distinct_outer_layers(rules, parent, outers)
});
}
}
fn solve_part_one(input: &str) {
let rules = parse_reverse_rules(input);
let mut shiny_gold_possibilities = Vec::new();
count_distinct_outer_layers(
&rules,
&"shiny gold".to_string(),
&mut shiny_gold_possibilities,
);
println!(
"The number of bag colors that can eventually contain at least one shiny gold bag is {}.",
shiny_gold_possibilities.into_iter().unique().count()
);
}
fn count_inner_bags(rules: &Tree, pattern: &str) -> u32 {
rules
.get(pattern)
.map(|rule| {
rule.iter()
.map(|(quantity, name)| quantity + (quantity * count_inner_bags(rules, name)))
.sum()
})
.unwrap_or(0)
}
fn solve_part_two(input: &str) {
let rules = parse_rules(input);
let inner_bags = count_inner_bags(&rules, &"shiny gold".to_string());
println!("The shiny gold bag has to contain {} bags.", inner_bags);
}
fn main() {
let input = include_str!("07_data.rules");
solve_part_one(input);
solve_part_two(input);
}