diff options
author | June McEnroe <programble@gmail.com> | 2017-12-15 22:32:26 -0500 |
---|---|---|
committer | June McEnroe <programble@gmail.com> | 2017-12-15 22:32:26 -0500 |
commit | f4bb366b822246ff6731fb676a4f87638cd4ed18 (patch) | |
tree | b8e8d8c65956afb86d789f92d2b6cb6fed753b99 /2017 | |
parent | Day 12 (diff) | |
download | aoc-f4bb366b822246ff6731fb676a4f87638cd4ed18.tar.gz aoc-f4bb366b822246ff6731fb676a4f87638cd4ed18.zip |
Day 12, part 2
Diffstat (limited to '2017')
-rw-r--r-- | 2017/src/bin/day12.rs | 52 |
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 +" + )); +} |