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
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); } }
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. :/