year2024/
day22.rs

1use utils::prelude::*;
2
3/// Simulating a pseudorandom number generator.
4#[derive(Clone, Debug)]
5pub struct Day22 {
6    input: Vec<u32>,
7}
8
9impl Day22 {
10    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
11        Ok(Self {
12            input: parser::number_range(0..=0x00FF_FFFF).parse_lines(input)?,
13        })
14    }
15
16    #[must_use]
17    pub fn part1(&self) -> u64 {
18        let mut numbers = self.input.clone();
19        for _ in 0..2000 {
20            // Inner loop over numbers allows for vectorization
21            for n in &mut numbers {
22                *n = Self::next(*n);
23            }
24        }
25        numbers.iter().map(|&n| u64::from(n)).sum()
26    }
27
28    #[must_use]
29    pub fn part2(&self) -> u16 {
30        let mut bananas = [0; 130_321]; // 19 ** 4
31        let mut seen = [0; 130_321];
32        for (i, &(mut n)) in self.input.iter().enumerate() {
33            let mut prev = n % 10;
34            let mut s4;
35
36            n = Self::next(n);
37            let mut s3 = ((9 + n % 10 - prev) as usize) * 19 * 19;
38            prev = n % 10;
39
40            n = Self::next(n);
41            let mut s2 = ((9 + n % 10 - prev) as usize) * 19;
42            prev = n % 10;
43
44            n = Self::next(n);
45            let mut s1 = (9 + n % 10 - prev) as usize;
46            prev = n % 10;
47
48            for _ in 3..2000 {
49                n = Self::next(n);
50                let digit = n % 10;
51                (s1, s2, s3, s4) = ((9 + digit - prev) as usize, 19 * s1, 19 * s2, 19 * s3);
52
53                let index = s4 + s3 + s2 + s1;
54                if seen[index] != (i + 1) as u16 {
55                    bananas[index] += digit as u16;
56                    seen[index] = (i + 1) as u16;
57                }
58
59                prev = digit;
60            }
61        }
62        bananas.iter().max().copied().unwrap()
63    }
64
65    #[expect(clippy::inline_always)]
66    #[inline(always)]
67    fn next(mut n: u32) -> u32 {
68        n = (n ^ (n << 6)) & 0x00FF_FFFF;
69        n = (n ^ (n >> 5)) & 0x00FF_FFFF;
70        (n ^ (n << 11)) & 0x00FF_FFFF
71    }
72}
73
74examples!(Day22 -> (u64, u16) [
75    {input: "1\n10\n100\n2024", part1: 37327623},
76    {input: "1\n2\n3\n2024", part2: 23},
77]);
year2024/day22.rs

year2024/
day22.rs
