aoc/year2017/
day14.rs

1//! # Disk Defragmentation
2//!
3//! This problem is a blend of the hashing from [`Day 10`] and the connected clique finding
4//! from [`Day 12`] and reuses the same flood fill approach to count groups.
5//!
6//! [`Day 10`]: crate::year2017::day10
7//! [`Day 12`]: crate::year2017::day12
8use std::array::from_fn;
9
10use crate::util::thread::*;
11
12/// Parallelize the hashing as each row is independent.
13pub fn parse(input: &str) -> Vec<u8> {
14    let prefix = input.trim();
15    let rows: Vec<_> = (0..128).collect();
16    let result = spawn_parallel_iterator(&rows, |iter| worker(prefix, iter));
17
18    let mut grid = vec![[[0; 8]; 16]; 128];
19    for (index, row) in result.into_iter().flatten() {
20        grid[index] = row;
21    }
22    grid.into_flattened().into_flattened()
23}
24
25pub fn part1(input: &[u8]) -> u32 {
26    input.iter().map(|&n| u32::from(n)).sum()
27}
28
29pub fn part2(input: &[u8]) -> usize {
30    let mut grid = input.to_vec();
31    let connect = |i| (grid[i] == 1).then(|| dfs(&mut grid, i));
32    (0..input.len()).filter_map(connect).count()
33}
34
35/// Each worker thread chooses the next available index then computes the hash and patches the
36/// final vec with the result.
37fn worker(prefix: &str, iter: ParIter<'_, usize>) -> Vec<(usize, [[u8; 8]; 16])> {
38    iter.map(|&index| (index, fill_row(prefix, index))).collect()
39}
40
41/// Compute the knot hash for a row and expand into a fixed-size array.
42fn fill_row(prefix: &str, index: usize) -> [[u8; 8]; 16] {
43    let s = format!("{prefix}-{index}");
44    let lengths: Vec<_> = s.bytes().map(usize::from).chain([17, 31, 73, 47, 23]).collect();
45
46    let knot = knot_hash(&lengths);
47    let mut result = [[0; 8]; 16];
48
49    for (i, chunk) in knot.chunks_exact(16).enumerate() {
50        let reduced = chunk.iter().fold(0, |acc, n| acc ^ n);
51        result[i] = from_fn(|j| (reduced >> (7 - j)) & 1);
52    }
53
54    result
55}
56
57/// Slightly tweaked version of the code from Day 10 that always performs 64 rounds.
58/// Uses a fixed-size array for better performance.
59#[inline]
60fn knot_hash(lengths: &[usize]) -> [u8; 256] {
61    let mut knot: [_; 256] = from_fn(|i| i as u8);
62    let mut position = 0;
63    let mut skip = 0;
64
65    for _ in 0..64 {
66        for &length in lengths {
67            let next = length + skip;
68            knot[0..length].reverse();
69            knot.rotate_left(next % 256);
70            position += next;
71            skip += 1;
72        }
73    }
74
75    // Rotate the array the other direction so that the original starting position is restored.
76    knot.rotate_right(position % 256);
77    knot
78}
79
80/// Flood fill that explores the connected squares in the grid.
81fn dfs(grid: &mut [u8], index: usize) {
82    grid[index] = 0;
83    let x = index % 128;
84    let y = index / 128;
85
86    if x > 0 && grid[index - 1] == 1 {
87        dfs(grid, index - 1);
88    }
89    if x < 127 && grid[index + 1] == 1 {
90        dfs(grid, index + 1);
91    }
92    if y > 0 && grid[index - 128] == 1 {
93        dfs(grid, index - 128);
94    }
95    if y < 127 && grid[index + 128] == 1 {
96        dfs(grid, index + 128);
97    }
98}
aoc/year2017/day14.rs

aoc/year2017/
day14.rs
