#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct SuperSecretPseudoRandomNumberGenerator {
    value: u64,
}

impl SuperSecretPseudoRandomNumberGenerator {
    pub fn new(seed: u64) -> Self {
        Self { value: seed }
    }
}

impl Iterator for SuperSecretPseudoRandomNumberGenerator {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        self.value ^= self.value << 6; // times 64, mix
        self.value &= 0x00FF_FFFF;
        self.value ^= self.value >> 5; // divide by 32, mix
        self.value &= 0x00FF_FFFF;
        self.value ^= self.value << 11; // times 2048, mix
        self.value &= 0x00FF_FFFF;

        Some(self.value)
    }
}

#[aoc_generator(day22)]
pub fn parse(input: &str) -> Vec<u64> {
    input.lines().map(|line| line.parse().unwrap()).collect()
}

#[aoc(day22, part1, v1)]
fn part1_v1(input: &[u64]) -> u64 {
    input
        .iter()
        .map(|&seed| {
            SuperSecretPseudoRandomNumberGenerator::new(seed)
                .into_iter()
                .nth(1999) // It's zero based :)
                .unwrap()
        })
        .sum()
}

$ cargo aoc --day 22 --part 1

AOC 2024
Day 22 - Part 1 - v1 : 13764677935
	generator: 80.5µs,
	runner: 8.88625ms

#[aoc(day22, part2, bruteforce)]
fn part2_bruteforce(input: &[u64]) -> usize {
    fn banana_score(input: &[u64], seq: &[i8]) -> usize {
        input
            .iter()
            .map(|&seed| {
                let mut rng = SuperSecretPseudoRandomNumberGenerator::new(seed);
                let mut previous_ones = (seed % 10) as i8;
                let mut delta_buffer = VecDeque::new();

                let mut index = 0;
                loop {
                    index += 1;
                    let value = rng.next().unwrap();
                    let ones = (value % 10) as i8;

                    delta_buffer.push_back(ones - previous_ones);
                    if delta_buffer.len() > 4 {
                        delta_buffer.pop_front();
                    }

                    previous_ones = ones;

                    if delta_buffer.len() == 4
                        && delta_buffer[0] == seq[0]
                        && delta_buffer[1] == seq[1]
                        && delta_buffer[2] == seq[2]
                        && delta_buffer[3] == seq[3]
                    {
                        break;
                    }

                    if index >= 2_000 {
                        return 0;
                    }
                }

                previous_ones as usize
            })
            .sum()
    }

    repeat_n(-9..=9, 4)
        .multi_cartesian_product()
        .map(|seq| banana_score(input, seq.as_slice()))
        .max()
        .unwrap()
}

$ cargo aoc --day 22 --part 2

AOC 2024
Day 22 - Part 2 - bruteforce : 1619
	generator: 50.75µs,
	runner: 1741.269152208s

$ cargo aoc --day 22 --part 2

Day 22 - Part 2 - bruteforce : 1619
	generator: 36.084µs,
	runner: 810.663676041s

#[aoc(day22, part2, seqscore)]
fn part2_seqscore(input: &[u64]) -> usize {
    let mut sequence_scores = HashMap::new();

    input.iter().for_each(|&seed| {
        // Find the first time each sequence appears and store the score for that sequence
        let mut local_sequence_scores = HashMap::new();
        let mut delta_buffer = VecDeque::new();

        SuperSecretPseudoRandomNumberGenerator::new(seed)
            .into_iter()
            .take(2_000)
            .fold((seed % 10) as i8, |previous_ones, value| {
                let ones = (value % 10) as i8;

                delta_buffer.push_back(ones - previous_ones);
                if delta_buffer.len() > 4 {
                    delta_buffer.pop_front();
                }

                if delta_buffer.len() == 4 {
                    let key = (
                        delta_buffer[0],
                        delta_buffer[1],
                        delta_buffer[2],
                        delta_buffer[3],
                    );
                    if !local_sequence_scores.contains_key(&key) {
                        local_sequence_scores.insert(key, ones as usize);
                    }
                }

                ones
            });

        // Add the new local sequence scores to the overall map
        local_sequence_scores.into_iter().for_each(|(key, value)| {
            sequence_scores
                .entry(key)
                .and_modify(|v| *v += value)
                .or_insert(value);
        });
    });

    // Find whichever sequence has the highest overall score
    sequence_scores
        .into_iter()
        .map(|(_key, value)| value)
        .max()
        .unwrap()
}

$ cargo aoc --day 22 --part 2

AOC 2024
Day 22 - Part 2 - seqscore : 1619
	generator: 35.458µs,
	runner: 96.270583ms

// ...

delta_buffer <<= 5;
delta_buffer |= (ones - previous_ones + 9) as u32;
delta_buffer &= 0b11111_11111_11111_11111;

if index > 4 && !local_sequence_scores.contains_key(&delta_buffer) {
    local_sequence_scores.insert(delta_buffer, ones as usize);
}
// ...

$ cargo aoc --day 22 --part 2

AOC 2024
Day 22 - Part 2 - seqscore : 1619
	generator: 35.458µs,
	runner: 96.270583ms

Day 22 - Part 2 - bitbuffer : 1619
	generator: 130.541µs,
	runner: 105.354917ms

$ cargo aoc bench --day 22

Day22 - Part1/v1        time:   [5.6602 ms 5.7042 ms 5.7508 ms]

Day22 - Part2/seqscore  time:   [97.792 ms 98.759 ms 99.974 ms]
Day22 - Part2/bitbuffer time:   [81.465 ms 81.937 ms 82.441 ms]