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

aoc/year2017/
day14.rs
