aoc/year2017/
day10.rs

1//! # Knot Hash
2//!
3//! Instead of reversing elements from the starting position then trying to handle wrap around,
4//! it's easier to use [`rotate_left`] to rotate the array by the same amount so that the starting
5//! position is always zero, then take advantage of the built-in [`reverse`] method.
6//!
7//! [`rotate_left`]: slice::rotate_left
8//! [`reverse`]: slice::reverse
9use crate::util::parse::*;
10use std::array::from_fn;
11use std::fmt::Write as _;
12
13pub fn parse(input: &str) -> &str {
14    input.trim()
15}
16
17pub fn part1(input: &str) -> u32 {
18    let lengths: Vec<_> = input.iter_unsigned().collect();
19    let knot = hash(&lengths, 1);
20    knot[0] as u32 * knot[1] as u32
21}
22
23pub fn part2(input: &str) -> String {
24    let mut lengths: Vec<_> = input.bytes().map(|b| b as usize).collect();
25    lengths.extend([17, 31, 73, 47, 23]);
26
27    let knot = hash(&lengths, 64);
28    knot.chunks_exact(16).fold(String::new(), |mut result, chunk| {
29        let reduced = chunk.iter().fold(0, |acc, n| acc ^ n);
30        let _ = write!(&mut result, "{reduced:02x}");
31        result
32    })
33}
34
35/// Performs the knot hash algorithm using a fixed-size array for better performance.
36#[inline]
37fn hash(lengths: &[usize], rounds: usize) -> [u8; 256] {
38    let mut knot: [u8; 256] = from_fn(|i| i as u8);
39    let mut position = 0;
40    let mut skip = 0;
41
42    for _ in 0..rounds {
43        for &length in lengths {
44            let next = length + skip;
45            knot[0..length].reverse();
46            knot.rotate_left(next % 256);
47            position += next;
48            skip += 1;
49        }
50    }
51
52    // Rotate the array the other direction so that the original starting position is restored.
53    knot.rotate_right(position % 256);
54    knot
55}
aoc/year2017/day10.rs

aoc/year2017/
day10.rs
