year2017/
day12.rs

1use utils::array::ArrayVec;
2use utils::prelude::*;
3
4/// Finding connected components in a graph.
5#[derive(Clone, Debug)]
6pub struct Day12 {
7    part1: u32,
8    part2: u32,
9}
10
11impl Day12 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let programs = parser::u32()
14            .repeat_arrayvec(", ", 1)
15            .with_prefix(parser::take_while1(u8::is_ascii_digit).with_suffix(" <-> "))
16            .parse_lines(input)?;
17
18        let mut groups = Vec::new();
19        let mut visited = vec![false; programs.len()];
20        for i in 0..programs.len() {
21            if !visited[i] {
22                groups.push(Self::connect(&programs, &mut visited, i));
23            }
24        }
25
26        Ok(Self {
27            part1: groups[0],
28            part2: groups.len() as u32,
29        })
30    }
31
32    fn connect(programs: &[ArrayVec<u32, 8>], visited: &mut [bool], program: usize) -> u32 {
33        visited[program] = true;
34
35        let mut group_len = 1;
36        for &connected in &programs[program] {
37            if !visited[connected as usize] {
38                group_len += Self::connect(programs, visited, connected as usize);
39            }
40        }
41
42        group_len
43    }
44
45    #[must_use]
46    pub fn part1(&self) -> u32 {
47        self.part1
48    }
49
50    #[must_use]
51    pub fn part2(&self) -> u32 {
52        self.part2
53    }
54}
55
56examples!(Day12 -> (u32, u32) [
57    {file: "day12_example0.txt", part1: 6, part2: 2},
58]);
year2017/day12.rs

year2017/
day12.rs
