year2017/
day14.rs

1use crate::knot_hash::knot_hash;
2use core::fmt::NumBuffer;
3use utils::bit::BitIterator;
4use utils::prelude::*;
5
6/// Finding connected regions in a hash-derived grid.
7///
8/// This puzzle is a combination of [`Day10`](crate::Day10), which introduced the custom knot hash
9/// function used to create the grid, and [`Day12`](crate::Day12), which also involved finding
10/// connected components.
11#[derive(Clone, Debug)]
12pub struct Day14 {
13    grid: [u128; 128],
14}
15
16impl Day14 {
17    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
18        let mut grid = [0u128; 128];
19
20        let mut num_buf = NumBuffer::new();
21        for (i, row) in grid.iter_mut().enumerate() {
22            let suffix = i.format_into(&mut num_buf);
23            let lengths = input.bytes().chain(*b"-").chain(suffix.bytes());
24            *row = u128::from_be_bytes(knot_hash(lengths));
25        }
26
27        Ok(Day14 { grid })
28    }
29
30    #[must_use]
31    pub fn part1(&self) -> u32 {
32        self.grid.iter().map(|x| x.count_ones()).sum()
33    }
34
35    #[must_use]
36    pub fn part2(&self) -> u32 {
37        let mut regions = 0;
38        let mut visited = [0u128; 128];
39
40        for (r, &row) in self.grid.iter().enumerate() {
41            for (_, bit) in BitIterator::ones(row) {
42                if visited[r] & bit == 0 {
43                    regions += 1;
44                    self.visit(&mut visited, r, bit)
45                }
46            }
47        }
48
49        regions
50    }
51
52    fn visit(&self, visited: &mut [u128; 128], r: usize, bit: u128) {
53        visited[r] |= bit;
54
55        if r > 0 && self.grid[r - 1] & bit != 0 && visited[r - 1] & bit == 0 {
56            self.visit(visited, r - 1, bit);
57        }
58        if r < 127 && self.grid[r + 1] & bit != 0 && visited[r + 1] & bit == 0 {
59            self.visit(visited, r + 1, bit);
60        }
61
62        let left = bit << 1;
63        if left != 0 && self.grid[r] & left != 0 && visited[r] & left == 0 {
64            self.visit(visited, r, left);
65        }
66        let right = bit >> 1;
67        if right != 0 && self.grid[r] & right != 0 && visited[r] & right == 0 {
68            self.visit(visited, r, right);
69        }
70    }
71}
72
73examples!(Day14 -> (u32, u32) [
74    {input: "flqrgnkx", part1: 8108, part2: 1242},
75]);
year2017/day14.rs

year2017/
day14.rs
