aoc/year2017/
day12.rs

1//! # Digital Plumber
2//!
3//! This problem is the classic [union-find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).
4//! A variant of [flood fill](https://en.wikipedia.org/wiki/Flood_fill) is used to find the
5//! connected groups or cliques.
6//!
7//! For each program we [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search)
8//! from each of its neighbors that we have not already seen. If a neighbor has been seen
9//! then it must be either already in this clique or in another clique.
10use crate::util::parse::*;
11
12type Input = (u32, usize);
13
14pub fn parse(input: &str) -> Input {
15    let lines: Vec<_> = input.lines().collect();
16    let size = lines.len();
17
18    let mut seen = vec![false; size];
19    let part_one = dfs(&lines, &mut seen, 0);
20    let part_two = 1 + (1..size).filter(|&i| dfs(&lines, &mut seen, i) > 0).count();
21
22    (part_one, part_two)
23}
24
25pub fn part1(input: &Input) -> u32 {
26    input.0
27}
28
29pub fn part2(input: &Input) -> usize {
30    input.1
31}
32
33#[inline]
34fn dfs(lines: &[&str], seen: &mut [bool], index: usize) -> u32 {
35    if seen[index] {
36        0
37    } else {
38        seen[index] = true;
39        // Skip the first 6 characters of each line as they contain the index that we already know.
40        1 + lines[index][6..].iter_unsigned().map(|i| dfs(lines, seen, i)).sum::<u32>()
41    }
42}
aoc/year2017/day12.rs

aoc/year2017/
day12.rs
