Rust

Nice breather today (still traumatized from the robots). At some point I thought you had to do some magic for predicting special properties of the pseudorandom function, but no, just collect all values, have a big table for all sequences and in the end take the maximum value in that table. Part 1 takes 6.7ms, part 2 19.2ms.

::: spoiler Solution

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!();

:::

Also on github

Uiua

It's been a while since I posted one of these, but I thought this would be straightforward in Uiua. Turns out that bitwise operations are a bit (haha) of a pain, so the Rng operation is very slow at 4sec for live data.

I took this as an opportunity to play with the ⧈(stencil) operator which probably slowed things down too.

Data ← 1_2_3_2024
Xor  ← °⋯◿2⬚0+∩⋯ # Bitwise xor of two numbers.
Rng  ← ⊙◌◿,Xor×2048.◿,Xor⌊÷32.◿,Xor×64.⊙16777216
Runs ← ⍉(⇌[⍥(Rng.)])2000 Data # Should be constant?
Firsts ← (
  ⊟⊂0⧈₂/-.◿10 ↘¯1         # Build run, gen pair diffs
  ⊢⧈(⊟⊙⊣/(+×40+20)°⊟) 2_4 # Convert 4-diff into key, collect.
  ⊕⊢⊛⊙⍉⊙◌°⊟.⍉             # Only keep first of each key. # ⍜(map°⊟⍉⇌|∘) failed. 
)
&p /+≡⊣.Runs
&p /↥⊕(/+)+1⊛°⊟⍉/◇⊂wait≡spawn(□Firsts) # Group by key, sum prices, return highest.

Haskell

I have no Idea how to optimize this and am looking forward to the other solutions that probably run in sub-single-second times. I like my solution because it was simple to write which I hadn't managed in the previous days, runs in 17 seconds with no less than 100MB of RAM.

import Control.Arrow
import Data.Bits (xor)
import Data.Ord (comparing)

import qualified Data.List as List
import qualified Data.Map as Map

parse :: String -> [Int]
parse = map read . filter (/= "") . lines

mix = xor 
prune = flip mod 16777216
priceof = flip mod 10

nextSecret step0 = do
        let step1 = prune . mix step0 $ step0 * 64
        let step2 = prune . mix step1 $ step1 `div` 32
        let step3 = prune . mix step2 $ step2 * 2048
        step3

part1 = sum . map (head . drop 2000 . iterate nextSecret)
part2 = map (iterate nextSecret
                >>> take 2001
                >>> map priceof
                >>> (id &&& tail)
                >>> uncurry (zipWith (curry (uncurry (flip (-)) &&& snd)))
                >>> map (take 4) . List.tails
                >>> filter ((==4) . length)
                >>> map (List.map fst &&& snd . List.last)
                >>> List.foldl (\ m (s, p) -> Map.insertWith (flip const) s p m) Map.empty
                )
        >>> Map.unionsWith (+)
        >>> Map.assocs
        >>> List.maximumBy (comparing snd)

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

Rust

Not too hard today, apart from yesterday's visit to a cocktail bar leaving me a little hazy in the mind.

::: spoiler code

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(())
}

:::

Rust

Part 2 is crazy slow, but it works, so thats cool :D

Edit: Gonna fix this, because pt2 is stupid.

Much better, 2.4s. Still slow, but not 6 minutes slow.

#[cfg(test)]
mod tests {
    use std::collections::HashMap;
    use std::iter::zip;

    fn step(start: usize) -> usize {
        let mut next = start;
        next = ((next * 64) ^ next) % 16777216;
        next = ((next / 32) ^ next) % 16777216;
        next = ((next * 2048) ^ next) % 16777216;
        next
    }

    fn simulate(initial: usize) -> usize {
        let mut next = initial;
        for _ in 0..2000 {
            next = step(next);
        }
        next
    }
    #[test]
    fn test_step() {
        assert_eq!(15887950, step(123));
    }
    #[test]
    fn test_simulate() {
        assert_eq!(8685429, simulate(1));
    }

    #[test]
    fn day22_part1_test() {
        let input = std::fs::read_to_string("src/input/day_22.txt").unwrap();
        let initial_values = input
            .split("\n")
            .map(|s| s.parse::<usize>().unwrap())
            .collect::<Vec<usize>>();

        let mut total = 0;

        for value in initial_values {
            total += simulate(value);
        }

        println!("{}", total);
    }

    #[test]
    fn day22_part2_test() {
        let input = std::fs::read_to_string("src/input/day_22.txt").unwrap();
        let initial_values = input
            .split("\n")
            .map(|s| s.parse::<usize>().unwrap())
            .collect::<Vec<usize>>();

        let mut all_deltas = vec![];
        let mut all_values = vec![];

        for value in initial_values {
            let mut deltas = String::with_capacity(2000);
            let mut values = vec![];
            let mut prev = value;
            for _ in 0..2000 {
                let next = step(prev);
                values.push(next % 10);
                deltas.push((10u8 + b'A' + ((prev % 10) as u8) - ((next % 10) as u8)) as char);
                prev = next;
            }

            all_deltas.push(deltas);
            all_values.push(values);
        }

        let mut totals = HashMap::with_capacity(100000);

        for (delta, value) in zip(&all_deltas, &all_values) {
            let mut cache = HashMap::with_capacity(2000);
            for j in 0..delta.len() - 4 {
                let seq = &delta[j..j + 4];
                let bananas = value[j + 3];
                cache.entry(seq).or_insert(bananas);
            }
            for (key, value) in cache {
                *totals.entry(key).or_insert(0) += value;
            }
        }

        let max_bananas = totals.values().max().unwrap();

        println!("{}", max_bananas);
    }
}

Go

Re-familiarizing myself with Go. The solution to Part 2 is fairly simply, the whole packing of the sequence into a single integer to save on memory was an optimization I did afterwards based on looking at other solutions. I thought it was cool.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type SequenceMap struct {
	Data map[int32]int
}

func PackSeq(numbers [4]int8) int32 {
	var packed int32
	for i, num := range numbers {
		packed |= int32(num+9) << (i * 5)
	}
	return packed
}

func UnpackSeq(packed int32) [4]int8 {
	var numbers [4]int8
	for i := range numbers {
		numbers[i] = int8((packed>>(i*5))&0x1F) - 9
	}
	return numbers
}

func NewSequenceMap() SequenceMap {
	return SequenceMap{make(map[int32]int)}
}

func (m *SequenceMap) Increment(seq [4]int8, val int) {
	pSeq := PackSeq(seq)
	acc, ok := m.Data[pSeq]
	if ok {
		m.Data[pSeq] = acc + val
	} else {
		m.Data[pSeq] = val
	}
}

func (m *SequenceMap) Has(seq [4]int8) bool {
	pSeq := PackSeq(seq)
	_, ok := m.Data[pSeq]
	return ok
}

type Generator struct {
	Secret         int64
	LastPrice      int8
	ChangeSequence []int8
}

func NewGenerator(Secret int64) Generator {
	var ChangeSequence []int8
	return Generator{Secret, int8(Secret % 10), ChangeSequence}
}

func (g *Generator) Mix(value int64) *Generator {
	g.Secret = g.Secret ^ value
	return g
}

func (g *Generator) Prune() *Generator {
	g.Secret = g.Secret % 16777216
	return g
}

func (g *Generator) Next() {
	g.Mix(g.Secret * 64).Prune().Mix(g.Secret / 32).Prune().Mix(g.Secret * 2048).Prune()
	Price := int8(g.Secret % 10)
	g.ChangeSequence = append(g.ChangeSequence, Price-g.LastPrice)
	g.LastPrice = Price
	if len(g.ChangeSequence) > 4 {
		g.ChangeSequence = g.ChangeSequence[1:]
	}
}

func ParseInput() []int64 {
	if fileInfo, _ := os.Stdin.Stat(); (fileInfo.Mode() & os.ModeCharDevice) != 0 {
		fmt.Println("This program expects input from stdin.")
		os.Exit(1)
	}
	scanner := bufio.NewScanner(os.Stdin)

	var numbers []int64
	for scanner.Scan() {
		line := scanner.Text()
		num, err := strconv.ParseInt(line, 10, 64)
		if err != nil {
			fmt.Printf("ERROR PARSING VALUE: %s\n", line)
			os.Exit(1)
		}
		numbers = append(numbers, num)
	}

	return numbers
}

func main() {
	numbers := ParseInput()

	m := NewSequenceMap()
	sum := int64(0)

	for i := 0; i < len(numbers); i += 1 {
		g := NewGenerator(numbers[i])
		tM := NewSequenceMap()
		for j := 0; j < 2000; j += 1 {
			g.Next()
			if len(g.ChangeSequence) == 4 {
				if !tM.Has([4]int8(g.ChangeSequence)) {
					tM.Increment([4]int8(g.ChangeSequence), 1)
					if g.LastPrice > 0 {
						m.Increment([4]int8(g.ChangeSequence), int(g.LastPrice))
					}
				}
			}
		}
		sum += g.Secret
	}

	fmt.Printf("Part One: %d\n", sum)

	var bestSeq [4]int8
	bestPrice := 0
	for pSeq, price := range m.Data {
		if price > bestPrice {
			bestPrice = price
			bestSeq = UnpackSeq(pSeq)
		}
	}

	fmt.Printf("Part Two: %d\n", bestPrice)
	fmt.Printf("Best Sequence: %d\n", bestSeq)
}

Haskell

::: spoiler solution

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

:::

Dart

Well, that was certainly a bit easier than yesterday...

I know running a window over each full list of 2000 prices rather than looking for cycles etc means I'm doing a lot of unnecessary work, but it only takes a couple of seconds, so that'll do.

import 'package:collection/collection.dart';
import 'package:more/more.dart';

rng(int i) {
  i = ((i << 6) ^ i) % 16777216;
  i = ((i >> 5) ^ i) % 16777216;
  i = ((i << 11) ^ i) % 16777216;
  return i;
}

Iterable<int> getPrices(int val, int rounds) {
  var ret = [val];
  for (var _ in 1.to(rounds)) {
    ret.add(val = rng(val));
  }
  return ret.map((e) => e % 10);
}

int run(int val, int rounds) => 0.to(rounds).fold(val, (s, t) => s = rng(s));
part1(lines) => [for (var i in lines.map(int.parse)) run(i, 2000)].sum;

part2(List<String> lines) {
  var market = <int, int>{}.withDefault(0);
  for (var seed in lines.map(int.parse)) {
    var seen = <int>{};
    for (var w in getPrices(seed, 2000).window(5)) {
      var key = // Can't use lists as keys, so make cheap hash.
          w.window(2).map((e) => e[1] - e[0]).reduce((s, t) => (s << 4) + t);
      if (seen.contains(key)) continue;
      seen.add(key);
      market[key] += w.last;
    }
  }
  return market.values.max;
}

Kotlin

I experimented a lot to improve the runtime and now I am happy with my solution. The JVM doesn't optimize code that quickly :)

I have implemented a few optimizations in regards to transformations so that they use arrays directly (The file with the implementations is here)

::: spoiler Code

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
    }
}

:::

Python3

Hey there lemmy, I recently transitioned from using notepad to Visual Studio Code along with running a local LLM for autocomplete(faster than copilot, big plus but hot af room)

I was able to make this python script with a bunch of fancy comments and typing silliness. I ended up spamming so many comments. yay documentation! lol

Solve time: ~3 seconds (can swing up to 5 seconds)

:::spoiler Code

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)

:::

Haskell

A nice easy one today; shame I couldn't start on time. I had a go at refactoring to reduce the peak memory usage, but it just ended up a mess. Here's a tidy version.

import Data.Bits
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map

next :: Int -> Int
next = flip (foldl' (\x n -> (x `xor` shift x n) .&. 0xFFFFFF)) [6, -5, 11]

bananaCounts :: Int -> Map [Int] Int
bananaCounts seed =
  let secrets = iterate next seed
      prices = map (`mod` 10) secrets
      changes = zipWith (-) (drop 1 prices) prices
      sequences = map (take 4) $ tails changes
   in Map.fromListWith (const id) $
        take 2000 (zip sequences (drop 4 prices))

main = do
  input <- map read . lines <$> readFile "input22"
  print . sum $ map ((!! 2000) . iterate next) input
  print . maximum $ Map.unionsWith (+) $ map bananaCounts input

C

Really proud of this one! Started with with an O(n^atoms in the universe) scan which took 44s even after adding a dedup check.

But iterating on a trick to encode the deltas for the dedup check, using it to build a mapping table here, a lookup there etc brought it down to a very fast, fairly low memory, linear complexity solution!

::: spoiler Code

#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;
}

:::

day22 0m00.04s real

https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day22.c