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    u32::from(knot[0]) * u32::from(knot[1])
22}
23
24pub fn part2(input: &str) -> String {
25    let lengths: Vec<_> = input.bytes().map(usize::from).chain([17, 31, 73, 47, 23]).collect();
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: [_; 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
