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
|
use std::collections::{HashMap, HashSet};
use std::io::{self, Read};
fn solve1(input: &str) -> usize {
let mut pipes: HashMap<u32, Vec<u32>> = HashMap::new();
for line in input.lines() {
let mut words = line.split_whitespace();
let src = words.next().unwrap().parse().unwrap();
assert_eq!(Some("<->"), words.next());
for dest in words {
let dest = dest.trim_right_matches(',').parse().unwrap();
pipes.entry(src).or_insert(vec![]).push(dest);
pipes.entry(dest).or_insert(vec![]).push(src);
}
}
let mut group = HashSet::new();
group.insert(0);
let mut prev = None;
while Some(group.len()) != prev {
prev = Some(group.len());
for (src, dests) in &pipes {
if group.contains(src) {
group.extend(dests);
}
}
}
group.len()
}
fn solve2(input: &str) -> usize {
let mut pipes: HashMap<u32, Vec<u32>> = HashMap::new();
for line in input.lines() {
let mut words = line.split_whitespace();
let src = words.next().unwrap().parse().unwrap();
assert_eq!(Some("<->"), words.next());
for dest in words {
let dest = dest.trim_right_matches(',').parse().unwrap();
pipes.entry(src).or_insert(vec![]).push(dest);
pipes.entry(dest).or_insert(vec![]).push(src);
}
}
let mut group = HashSet::new();
let mut groups = 0;
group.insert(0);
loop {
let mut prev = None;
while Some(group.len()) != prev {
prev = Some(group.len());
for (src, dests) in &pipes {
if group.contains(src) {
group.extend(dests);
}
}
}
groups += 1;
match pipes.keys().find(|k| !group.contains(k)) {
Some(k) => { group.insert(*k); },
None => { return groups; },
}
}
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
println!("Part 1: {}", solve1(&input));
println!("Part 2: {}", solve2(&input));
}
#[test]
fn part1() {
assert_eq!(6, solve1(
"\
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
"
));
}
#[test]
fn part2() {
assert_eq!(2, solve2(
"\
0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
"
));
}
|