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
|
use crate::prelude::*;
type Graph = HashMap<String, Vec<(i64, String)>>;
pub fn parse(fh: File) -> Result<Graph> {
let input = parse::string(fh);
let mut graph = Graph::new();
for line in input.lines() {
let (k, v) = parse_line(line)?;
graph.insert(k, v);
}
Ok(graph)
}
pub fn part1(graph: Graph) -> Result<i64> {
let mut colors = 0;
for color in graph.keys() {
if bag_contains(&graph, color, "shiny gold")? {
colors += 1;
}
}
Ok(colors)
}
pub fn part2(graph: Graph) -> Result<i64> {
// subtract 1 to not count the shiny gold bag itself
count_bags(&graph, "shiny gold").map(|i| i - 1)
}
fn parse_line(line: &str) -> Result<(String, Vec<(i64, String)>)> {
let main_rx = Regex::new(r"^(.*) bags contain (.*)\.$").unwrap();
let contents_rx = Regex::new(r"^([0-9]+) (.*) bags?").unwrap();
let captures = main_rx
.captures(line)
.context("line failed to match regex")?;
let color = captures.get(1).unwrap().as_str();
let contents = captures.get(2).unwrap().as_str();
if contents == "no other bags" {
Ok((color.to_string(), vec![]))
} else {
Ok((
color.to_string(),
contents
.split(", ")
.map(|s| {
let captures = contents_rx
.captures(s)
.context("line failed to match regex")?;
Ok((
captures
.get(1)
.unwrap()
.as_str()
.parse()
.context("invalid number of bags")?,
captures.get(2).unwrap().as_str().to_string(),
))
})
.collect::<Result<_>>()?,
))
}
}
fn bag_contains(graph: &Graph, start: &str, target: &str) -> Result<bool> {
let mut to_check = graph
.get(&start.to_string())
.context("failed to find starting color in graph")?
.clone();
while let Some((_, next)) = to_check.pop() {
if next == target {
return Ok(true);
}
to_check.extend(
graph
.get(&next)
.context("failed to find next color in graph")?
.iter()
.cloned(),
);
}
Ok(false)
}
fn count_bags(graph: &Graph, color: &str) -> Result<i64> {
Ok(1 + graph
.get(&color.to_string())
.context("failed to find starting color in graph")?
.iter()
.map(|(count, child)| Ok(count * count_bags(graph, child)?))
.collect::<Result<Vec<_>>>()?
.iter()
.sum::<i64>())
}
#[test]
fn test() {
assert_eq!(
part1(parse(parse::data(2020, 7).unwrap()).unwrap()).unwrap(),
169
);
assert_eq!(
part2(parse(parse::data(2020, 7).unwrap()).unwrap()).unwrap(),
82372
);
}
|
