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

aoc/year2017/
day14.rs
