fn step(n: u32) -> u32 {
    let a = (n ^ (n << 6)) % (1 << 24);
    let b = a ^ (a >> 5);
    (b ^ (b << 11)) % (1 << 24)
}

fn part1(input: String) {
    let sum = input
        .lines()
        .map(|l| {
            let n = l.parse().unwrap();
            (0..2000).fold(n, |acc, _| step(acc)) as u64
        })
        // More than 2¹⁰ 24-bit numbers requires 35 bits
        .sum::<u64>();
    println!("{sum}");
}

const N_SEQUENCES: usize = 19usize.pow(4);

fn sequence_key(sequence: &[i8]) -> usize {
    sequence
        .iter()
        .enumerate()
        .map(|(i, x)| (x + 9) as usize * 19usize.pow(i as u32))
        .sum()
}

fn part2(input: String) {
    // Table for collecting the amount of bananas for every possible sequence
    let mut table = vec![0; N_SEQUENCES];
    // Mark the sequences we encountered in a round to ensure that only the first occurence is used
    let mut seen = vec![false; N_SEQUENCES];
    for l in input.lines() {
        let n = l.parse().unwrap();
        let (diffs, prices): (Vec<i8>, Vec<u8>) = (0..2000)
            .scan(n, |acc, _| {
                let next = step(*acc);
                let diff = (next % 10) as i8 - (*acc % 10) as i8;
                *acc = next;
                Some((diff, (next % 10) as u8))
            })
            .unzip();
        for (window, price) in diffs.windows(4).zip(prices.iter().skip(3)) {
            let key = sequence_key(window);
            if !seen[key] {
                seen[key] = true;
                table[key] += *price as u32;
            }
        }
        // Reset seen sequences for next round
        seen.fill(false);
    }
    let bananas = table.iter().max().unwrap();
    println!("{bananas}");
}

util::aoc_main!();

use std::{fs, str::FromStr};

use color_eyre::eyre::{Report, Result};
use gxhash::{HashMap, HashMapExt};

const SECRETS_PER_DAY: usize = 2000;
const SEQ_LEN: usize = 4;

type Sequence = [i8; SEQ_LEN];

fn produce(n: usize) -> usize {
    let n = (n ^ (n * 64)) % 16777216;
    let n = (n ^ (n / 32)) % 16777216;
    (n ^ (n * 2048)) % 16777216
}

#[derive(Debug)]
struct Buyer {
    prices: [u8; SECRETS_PER_DAY + 1],
    changes: [i8; SECRETS_PER_DAY],
}

impl Buyer {
    fn price_at_seq(&self, seq: &Sequence) -> Option<u8> {
        self.changes
            .windows(SEQ_LEN)
            .position(|win| win == *seq)
            .and_then(|i| self.price_for_window(i))
    }

    fn price_for_window(&self, i: usize) -> Option<u8> {
        self.prices.get(i + SEQ_LEN).copied()
    }
}

struct BananaMarket {
    buyers: Vec<Buyer>,
}

impl FromStr for BananaMarket {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let buyer_seeds = s
            .lines()
            .map(|s| s.parse::<usize>())
            .collect::<Result<Vec<_>, _>>()?;

        let buyers = buyer_seeds
            .into_iter()
            .map(|seed| {
                let mut prices = [0; SECRETS_PER_DAY + 1];
                let mut changes = [0; SECRETS_PER_DAY];

                let mut secret = seed;
                let mut price = (seed % 10) as u8;
                prices[0] = price;
                for i in 0..SECRETS_PER_DAY {
                    let last_price = price;
                    secret = produce(secret);
                    price = (secret % 10) as u8;
                    prices[i + 1] = price;
                    changes[i] = price as i8 - last_price as i8;
                }
                Buyer { prices, changes }
            })
            .collect();
        Ok(Self { buyers })
    }
}

impl BananaMarket {
    fn sell_with_seq(&self, seq: &Sequence) -> usize {
        self.buyers
            .iter()
            .map(|b| b.price_at_seq(seq).unwrap_or(0) as usize)
            .sum()
    }

    fn maximise_bananas(&self) -> usize {
        let mut cache: HashMap<Sequence, usize> = HashMap::new();

        for seq in self
            .buyers
            .iter()
            .flat_map(|buyer| buyer.changes.windows(SEQ_LEN))
        {
            let seq = seq.try_into().unwrap();
            cache.entry(seq).or_insert_with(|| self.sell_with_seq(&seq));
        }

        cache.into_values().max().unwrap_or(0)
    }
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?
        .lines()
        .map(|s| s.parse::<usize>())
        .collect::<Result<Vec<_>, _>>()?;
    let res = input
        .into_iter()
        .map(|n| (0..SECRETS_PER_DAY).fold(n, |acc, _| produce(acc)))
        .sum();
    Ok(res)
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let market = BananaMarket::from_str(&input)?;
    Ok(market.maximise_bananas())
}

fn main() -> Result<()> {
    color_eyre::install()?;

    println!("Part 1: {}", part1("d22/input.txt")?);
    println!("Part 2: {}", part2("d22/input.txt")?);
    Ok(())
}

class Day22 {

    private fun nextSecretNumber(start: Long): Long {
        // Modulo 2^24 is the same as "and" with 2^24 - 1
        val pruneMask = 16777216L - 1L
        // * 64 is the same as shifting left by 6
        val mul64 = ((start shl 6) xor start) and pruneMask
        // / 32 is the same as shifting right by 5
        val div32 = ((mul64 shr 5) xor mul64) and pruneMask
        // * 2048 is the same as shifting left by 11
        val mul2048 = ((div32 shl 11) xor div32) and pruneMask
        return mul2048
    }

    fun part1(inputFile: String): String {
        val secretNumbers = readResourceLines(inputFile)
            .map { it.toLong() }
            .toLongArray()

        repeat(NUMBERS_PER_DAY) {
            for (i in secretNumbers.indices) {
                secretNumbers[i] = nextSecretNumber(secretNumbers[i])
            }
        }

        return secretNumbers.sum().toString()
    }

    fun part2(inputFile: String): String {
        // There is a different sample input for part 2
        val input = if (inputFile.endsWith("sample")) {
            readResourceLines(inputFile + "2")
        } else {
            readResourceLines(inputFile)
        }
        val buyers = input
            .map {
                LongArray(NUMBERS_PER_DAY + 1).apply {
                    this[0] = it.toLong()
                    for (i in 1..NUMBERS_PER_DAY) {
                        this[i] = nextSecretNumber(this[i - 1])
                    }
                }
            }

        // Calculate the prices and price differences for each buyer.
        // The pairs are the price (the ones digit) and the key/unique value of each sequence of differences
        val differences = buyers
            .map { secretNumbers ->
                // Get the ones digit
                val prices = secretNumbers.mapToIntArray {
                    it.toInt() % 10
                }

                // Get the differences between each number
                val differenceKeys = prices
                    .zipWithNext { a, b -> (b - a) }
                    // Transform the differences to a singular unique value (integer)
                    .mapWindowed(4) { sequence, from, _ ->
                        // Bring each byte from -9 to 9 to 0 to 18, multiply by 19^i and sum
                        // This generates a unique value for each sequence of 4 differences
                        (sequence[from + 0] + 9) +
                                (sequence[from + 1] + 9) * 19 +
                                (sequence[from + 2] + 9) * 361 +
                                (sequence[from + 3] + 9) * 6859
                    }

                // Drop the first 4 prices, as they are not relevant (initial secret number price and 3 next prices)
                prices.dropFromArray(4) to differenceKeys
            }

        // Cache to hold the value/sum of each sequence of 4 differences
        val sequenceCache = IntArray(NUMBER_OF_SEQUENCES)
        val seenSequence = BooleanArray(NUMBER_OF_SEQUENCES)

        // Go through each sequence of differences
        // and get their *first* prices of each sequence.
        // Sum them in the cache.
        for ((prices, priceDifferences) in differences) {
            // Reset the "seen" array
            Arrays.fill(seenSequence, false)
            for (index in priceDifferences.indices) {
                val key = priceDifferences[index]
                if (!seenSequence[key]) {
                    sequenceCache[key] += prices[index]
                    seenSequence[key] = true
                }
            }
        }

        return sequenceCache.max().toString()
    }

    companion object {
        private const val NUMBERS_PER_DAY = 2000

        // 19^4, the differences range from -9 to 9 and the sequences are 4 numbers long
        private const val NUMBER_OF_SEQUENCES = 19 * 19 * 19 * 19
    }
}

import Control.Arrow
import Data.Bits
import Data.List
import qualified Data.Map as M

parse = fmap (secretNums . read) . lines

secretNums :: Int -> [Int]
secretNums = take 2001 . iterate (step1 >>> step2 >>> step3)
 where
  step1 n = ((n `shiftL` 06) `xor` n) .&. 0xFFFFFF
  step2 n = ((n `shiftR` 05) `xor` n) .&. 0xFFFFFF
  step3 n = ((n `shiftL` 11) `xor` n) .&. 0xFFFFFF

part1 = sum . fmap last
part2 = maximum . M.elems . M.unionsWith (+) . fmap (deltas . fmap (`mod` 10))

deltas l = M.fromListWith (\n p -> p) $ flip zip (drop 4 l) $ zip4 diffs (tail diffs) (drop 2 diffs) (drop 3 diffs)
 where
  diffs = zipWith (-) (tail l) l

main = getContents >>= print . (part1 &&& part2) . parse

#include "common.h"

#define STEPS	2000
#define NCODES	(19*19*19*19)

int
main(int argc, char **argv)
{
	static int8_t prices[STEPS];
	static int8_t by_deltas[NCODES];
	static int sums[NCODES];

	uint64_t p1=0, secret;
	int p2=0, i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (scanf(" %"SCNu64, &secret) == 1) {
		memset(by_deltas, 0, sizeof(by_deltas));

		for (i=0; i<STEPS; i++) {
			secret = (secret ^ secret << 6)  & 0xFFFFFF;
			secret = (secret ^ secret >> 5);
			secret = (secret ^ secret << 11) & 0xFFFFFF;

			prices[i] = secret % 10;
		}

		/*
		 * Build a deltas->price map for the buyer. Deltas are
		 * encoded as an integer for easy indexing. Iterating
		 * backwards ensures the stored price is the _earliest_
		 * occurence of that sequence.
		 */
		for (i=STEPS-1; i>=4; i--)
			by_deltas[
			    (prices[i-3] - prices[i-4] +9) *19*19*19 +
			    (prices[i-2] - prices[i-3] +9) *19*19 +
			    (prices[i-1] - prices[i-2] +9) *19 +
			    (prices[i]   - prices[i-1] +9)
			] = prices[i];

		for (i=0; i<NCODES; i++)
			sums[i] += by_deltas[i];

		p1 += secret;
	}

	for (i=0; i<NCODES; i++)
		p2 = MAX(p2, sums[i]);

	printf("22: %"PRIu64" %d\n", p1, p2);
	return 0;
}

from tqdm import tqdm
from os.path import dirname,isfile,realpath,join

from collections.abc import Callable
def profiler(method) -> Callable[..., any]:
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret
    return wrapper_method

# Process a secret to a new secret number
# @param n: The secret number to be processed
# @return: The new secret number after processing
def process_secret(n: int) -> int:
    """ 
    Process a secret number by XORing it with the result of shifting left and right operations on itself. 
    The process involves several bitwise operations to ensure that the resulting number is different from the original one.
    
    First, multiply the original secret number by 64 with a left bit shift, then XOR the original secret number with the new number and prune to get a new secret number
    Second, divide the previous secret number by 32 with a right bit shift, then XOR the previous secret number with the new number and prune to get another new secret number
    Third, multiply the previous secret number by 2048 with a left bit shift, then XOR the previous secret number with the new number and prune to get the final secret number
    Finally, return the new secret number after these operations.

    """
    n ^= (n << 6) 
    n &= 0xFFFFFF
    n ^= (n >> 5)
    n &= 0xFFFFFF
    n ^= (n << 11)
    return n & 0xFFFFFF

# Solve Part 1 and Part 2 of the challenge at the same time
@profiler
def solve(secrets: list[int]) -> tuple[int, int]:
    # Build a dictionary for each buyer with the tuple of changes being the key and the sum of prices of the earliest occurrence for each buyer as the value
    # At the same time we solve Part 1 of the challenge by adding the last price for each secret
    last_price_sum = 0
    changes_map = {}
    for start_secret in (secrets):
        # Keep track of seen patterns for current secret
        changes_seen = set()
        # tuple of last 4 changes
        # first change is 0 because it is ignored
        last_four_changes = tuple([
                                    (cur_secret:=process_secret(start_secret)), 
                                   -(cur_secret%10) + ((cur_secret:=process_secret(cur_secret)) % 10) , 
                                   -(cur_secret%10) + ((cur_secret:=process_secret(cur_secret)) % 10) , 
                                   -(cur_secret%10) + ((cur_secret:=process_secret(cur_secret)) % 10) 
                                   ]
                                   )
        current_price = sum(last_four_changes)
        # Map 4-tuple of changes -> sum of prices index of earliest occurrence for all secrets
        for i in range(3, 1999):
            # sliding window of last four changes
            last_four_changes = (*last_four_changes[1:], -(cur_secret%10) + (current_price := (cur_secret:=process_secret(cur_secret)) % 10) )
            # if we have seen this pattern before, then we continue to next four changes
            # otherwise, we add the price to the mapped value
            # this ensures we only add the first occurence of a patten for each list of prices each secret produces
            if last_four_changes not in changes_seen:
                # add to the set of seen patterns for this buyer
                changes_seen.add(last_four_changes)
                # If not recorded yet, store the price
                # i+4 is the index of the price where we sell
                changes_map[last_four_changes] = changes_map.get(last_four_changes, 0) + current_price

        # Sum the 2000th price to the total sum for all secrets
        last_price_sum += cur_secret
    # Return the sum of all prices at the 2000th iteration and the maximum amount of bananas that one pattern can obtain
    return last_price_sum,max(changes_map.values())

if __name__ == "__main__":
    # Read buyers' initial secrets from file or define them here
    BASE_DIR = dirname(realpath(__file__))
    with open(join(BASE_DIR, r'input'), "r") as f:
        secrets = [int(x) for x in f.read().split()]
    last_price_sum,best_score = solve(secrets)
    print("Part 1:")
    print(f"sum of each of the 2000th secret number:", last_price_sum)
    print("Part 2:")
    print("Max bananas for one of patterns:", best_score)