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]) -> u32 {
29    let mut grid: Vec<_> = input.iter().map(|&n| n == 1).collect();
30    let mut groups = 0;
31
32    for start in 0..0x4000 {
33        // DFS from each new group.
34        if grid[start] {
35            groups += 1;
36            dfs(&mut grid, start);
37        }
38    }
39
40    groups
41}
42
43/// Each worker thread chooses the next available index then computes the hash and patches the
44/// final vec with the result.
45fn worker(prefix: &str, iter: ParIter<'_, usize>) -> Vec<(usize, [u8; 128])> {
46    iter.map(|&index| (index, fill_row(prefix, index))).collect()
47}
48
49/// Compute the knot hash for a row and expand into a fixed-size array.
50fn fill_row(prefix: &str, index: usize) -> [u8; 128] {
51    let s = format!("{prefix}-{index}");
52    let mut lengths: Vec<_> = s.bytes().map(|b| b as usize).collect();
53    lengths.extend([17, 31, 73, 47, 23]);
54
55    let knot = knot_hash(&lengths);
56    let mut result = [0; 128];
57
58    for (i, chunk) in knot.chunks_exact(16).enumerate() {
59        let reduced = chunk.iter().fold(0, |acc, n| acc ^ n);
60        for j in 0..8 {
61            result[8 * i + j] = (reduced >> (7 - j)) & 1;
62        }
63    }
64
65    result
66}
67
68/// Slightly tweaked version of the code from Day 10 that always performs 64 rounds.
69/// Uses a fixed-size array for better performance.
70#[inline]
71fn knot_hash(lengths: &[usize]) -> [u8; 256] {
72    let mut knot: [u8; 256] = from_fn(|i| i as u8);
73    let mut position = 0;
74    let mut skip = 0;
75
76    for _ in 0..64 {
77        for &length in lengths {
78            let next = length + skip;
79            knot[0..length].reverse();
80            knot.rotate_left(next % 256);
81            position += next;
82            skip += 1;
83        }
84    }
85
86    // Rotate the array the other direction so that the original starting position is restored.
87    knot.rotate_right(position % 256);
88    knot
89}
90
91/// Flood fill that explores the connected squares in the grid.
92fn dfs(grid: &mut [bool], index: usize) {
93    grid[index] = false;
94    let x = index % 128;
95    let y = index / 128;
96
97    if x > 0 && grid[index - 1] {
98        dfs(grid, index - 1);
99    }
100    if x < 127 && grid[index + 1] {
101        dfs(grid, index + 1);
102    }
103    if y > 0 && grid[index - 128] {
104        dfs(grid, index - 128);
105    }
106    if y < 127 && grid[index + 128] {
107        dfs(grid, index + 128);
108    }
109}
aoc/year2017/day14.rs

aoc/year2017/
day14.rs
