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; 128 * 128];
19    for (index, row) in result.into_iter().flatten() {
20        grid[index * 128..(index + 1) * 128].copy_from_slice(&row);
21    }
22    grid
23}
24
25pub fn part1(input: &[u8]) -> u32 {
26    input.iter().map(|&n| n as u32).sum()
27}
28
29pub fn part2(input: &[u8]) -> usize {
30    let mut grid = input.to_vec();
31    let connect = |i: usize| (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; 128])> {
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; 128] {
43    let s = format!("{prefix}-{index}");
44    let mut lengths: Vec<_> = s.bytes().map(|b| b as usize).collect();
45    lengths.extend([17, 31, 73, 47, 23]);
46
47    let knot = knot_hash(&lengths);
48    let mut result = [0; 128];
49
50    for (i, chunk) in knot.chunks_exact(16).enumerate() {
51        let reduced = chunk.iter().fold(0, |acc, n| acc ^ n);
52        for j in 0..8 {
53            result[8 * i + j] = (reduced >> (7 - j)) & 1;
54        }
55    }
56
57    result
58}
59
60/// Slightly tweaked version of the code from Day 10 that always performs 64 rounds.
61/// Uses a fixed-size array for better performance.
62#[inline]
63fn knot_hash(lengths: &[usize]) -> [u8; 256] {
64    let mut knot: [u8; 256] = from_fn(|i| i as u8);
65    let mut position = 0;
66    let mut skip = 0;
67
68    for _ in 0..64 {
69        for &length in lengths {
70            let next = length + skip;
71            knot[0..length].reverse();
72            knot.rotate_left(next % 256);
73            position += next;
74            skip += 1;
75        }
76    }
77
78    // Rotate the array the other direction so that the original starting position is restored.
79    knot.rotate_right(position % 256);
80    knot
81}
82
83/// Flood fill that explores the connected squares in the grid.
84fn dfs(grid: &mut [u8], index: usize) {
85    grid[index] = 0;
86    let x = index % 128;
87    let y = index / 128;
88
89    if x > 0 && grid[index - 1] == 1 {
90        dfs(grid, index - 1);
91    }
92    if x < 127 && grid[index + 1] == 1 {
93        dfs(grid, index + 1);
94    }
95    if y > 0 && grid[index - 128] == 1 {
96        dfs(grid, index - 128);
97    }
98    if y < 127 && grid[index + 128] == 1 {
99        dfs(grid, index + 128);
100    }
101}
aoc/year2017/day14.rs

aoc/year2017/
day14.rs
