summary refs log tree commit diff homepage
path: root/2017/src/bin
diff options
context:
space:
mode:
authorJune McEnroe <june@causal.agency>2017-12-15 22:32:26 -0500
committerJune McEnroe <june@causal.agency>2020-11-22 00:14:25 -0500
commitd627b0bf64921cedc7343acccfccda16b68e47ba (patch)
treefbc51854e698006fc7609ffb4a9af20dc43233ec /2017/src/bin
parentDay 12 (diff)
downloadaoc-d627b0bf64921cedc7343acccfccda16b68e47ba.tar.gz
aoc-d627b0bf64921cedc7343acccfccda16b68e47ba.zip
Day 12, part 2
Diffstat (limited to '2017/src/bin')
-rw-r--r--2017/src/bin/day12.rs52
1 files changed, 52 insertions, 0 deletions
diff --git a/2017/src/bin/day12.rs b/2017/src/bin/day12.rs
index b133ba6..b7d07db 100644
--- a/2017/src/bin/day12.rs
+++ b/2017/src/bin/day12.rs
@@ -30,11 +30,48 @@ fn solve1(input: &str) -> usize {
     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]
@@ -51,3 +88,18 @@ fn part1() {
 "
     ));
 }
+
+#[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
+"
+    ));
+}