Day 22: Monkey Market
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
2 points
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)
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
}
}
2 points
*
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);
}
}
2 points
Six minutes? 😅 I was feeling crappy about my 30 seconds (my naive big O cubed(?) logic means my code spends most of its time testing array equalities - 72 billion samples in the flamegraph!)
Most of my time is wasted on hashmap stuff. And the processing into the string, which really isnt needed anymore. :/
1 point
*
5 points
*
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_10_100_2024
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.
First ← (
⊟⊂0⧈₂/-.◿10 ↘¯1 # Build run, gen pair diffs
⍣⊢0▽⊸>0⊢⧈(⨬⋅0⊣≍¯2_1_¯1_3°⊟) 2_4 # Take first value for matching diffs.
)
&p /+≡⊣.Runs
&p /+≡First
4 points
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.
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
3 points
3 points
Rust
Not too hard today, apart from yesterday’s visit to a cocktail bar leaving me a little hazy in the mind.
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(())
}
