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

aoc/year2017/
day14.rs
