this post was submitted on 22 Dec 2024
18 points (95.0% liked)

Advent Of Code

981 readers
28 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
 

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

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 3 points 3 days ago

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