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

aoc/year2017/
day10.rs
