year2017/
day14.rs

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

year2017/
day14.rs
