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
You are viewing a single thread.
View all comments 
5 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
