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

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

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

Haskell

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

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