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 std::array::from_fn;
10use std::fmt::Write as _;
11
12use crate::util::parse::*;
13
14pub fn parse(input: &str) -> &str {
15    input.trim()
16}
17
18pub fn part1(input: &str) -> u32 {
19    let lengths: Vec<_> = input.iter_unsigned().collect();
20    let knot = hash(&lengths, 1);
21    knot[0] as u32 * knot[1] as u32
22}
23
24pub fn part2(input: &str) -> String {
25    let mut lengths: Vec<_> = input.bytes().map(|b| b as usize).collect();
26    lengths.extend([17, 31, 73, 47, 23]);
27
28    let knot = hash(&lengths, 64);
29    knot.chunks_exact(16).fold(String::new(), |mut result, chunk| {
30        let reduced = chunk.iter().fold(0, |acc, n| acc ^ n);
31        let _ = write!(&mut result, "{reduced:02x}");
32        result
33    })
34}
35
36/// Performs the knot hash algorithm using a fixed-size array for better performance.
37#[inline]
38fn hash(lengths: &[usize], rounds: usize) -> [u8; 256] {
39    let mut knot: [u8; 256] = from_fn(|i| i as u8);
40    let mut position = 0;
41    let mut skip = 0;
42
43    for _ in 0..rounds {
44        for &length in lengths {
45            let next = length + skip;
46            knot[0..length].reverse();
47            knot.rotate_left(next % 256);
48            position += next;
49            skip += 1;
50        }
51    }
52
53    // Rotate the array the other direction so that the original starting position is restored.
54    knot.rotate_right(position % 256);
55    knot
56}
aoc/year2017/day10.rs

aoc/year2017/
day10.rs
