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 visited. If a neighbor has been visited
9//! then it must be either already in this clique or in another clique.
10use crate::util::parse::*;
11
12pub fn parse(input: &str) -> Vec<u32> {
13    let lines: Vec<_> = input.lines().collect();
14    let size = lines.len();
15
16    let mut visited = vec![false; size];
17    let mut groups = Vec::new();
18
19    for start in 0..size {
20        // DFS from each unvisited program.
21        if !visited[start] {
22            visited[start] = true;
23            let size = dfs(&lines, &mut visited, start);
24            groups.push(size);
25        }
26    }
27
28    groups
29}
30
31pub fn part1(input: &[u32]) -> u32 {
32    input[0]
33}
34
35pub fn part2(input: &[u32]) -> usize {
36    input.len()
37}
38
39fn dfs(lines: &[&str], visited: &mut [bool], index: usize) -> u32 {
40    let mut size = 1;
41
42    // At least the first 6 characters of each line can be skipped as it only contains the index
43    // that we already know.
44    for next in (&lines[index][6..]).iter_unsigned::<usize>() {
45        if !visited[next] {
46            visited[next] = true;
47            size += dfs(lines, visited, next);
48        }
49    }
50
51    size
52}
aoc/year2017/day12.rs

aoc/year2017/
day12.rs
