[MIT] does not allow removing the original license and purport that the code was created by someone else.

Sounds like it wouldn’t matter which licence he used. Shitty behaviour from Microsoft.

I do if I can raise the laptop up so that the screen is where it should be for good ergonomics.

It’s how everyone who’s anyone does code reviews!

One core was busier, but it wasn’t at 100%. My Rust code yesterday was the same, perhaps it’s taking too much time accessing memory.

The time was wall time (as per Starship’s output) but it was still waaay too slow to bother with again!

Have you tried gxhash or one of the other non-cryptographic hashers?

I just ran this on a laptop - it worked (part one only) but took 4h28m21s so Nushell is not a language for AoC (or I just coded it very poorly).

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!)

How have I never noticed that scan() exists? Very handy.

I liked the zipping of the offset prices, neater than my helper method.

Rust

Not too hard today, apart from yesterday’s visit to a cocktail bar leaving me a little hazy in the mind.

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

I missed that line too:

Because there is only a single path from the start to the end

So I also did my pathfinding for every variation in the first part, but realised something must be wrong with my approach when I saw part 2.

That full version is extremely satisfying. I think it’d be even better if there were sound - maybe ascending notes in a scale like in some puzzle games.

I like the take that they have in that thread: Perforce is forking Puppet into a non-Open Source version (but they’re keeping the name).

The main thing I remember about Dijkstra’s algorithm was that at uni when we coded it up in the lab my version had a bug where a certain node was always 0, so I just left the mouse cursor on top of that mode when I demoed it - got full marks 🤓

I think just announce it’s a thing and let people post as they will. I don’t think a daily thread is necessary, for the reason you say but also that individual posts would get more attention - and extra attention is warranted since there’s a lot of extra work that goes in to them.

Perhaps you could run an “advent of vis” where on the first of Jan we post visualisations of our solutions for day 1, etc.

Maybe you’re already editing it in, but there’s no description in your post.

Haha, thanks but we both know they’re #1 by a country mile. I think my phone’s now downclocking as it’s burning up and still hasn’t spat out an answer after two hours, so I technically haven’t completed it yet!

Edit: Calling it for now, I might figure out later why it’s so slow (there’s some easy but minor gains to be made but I’m guessing there’s some O(awful) going on that the input’s blown up)

Nushell

As I’m still on holiday and normal languages are a PITA to type on a phone, I though I’d try a compiled scripting language. I’m not very familiar with it so it took longer to code and also it’s been running the first reduce step for 35 minutes so I’ve missed the 24h cutoff 😔

use std repeat
use std/iter

let memory = open input.txt | str trim 
  | split chars | chunks 2
  | enumerate | each {|pair| [
    ...($pair.index | repeat ($pair.item.0 | into int))
    ...("." | repeat (if ($pair.item|length) < 2 {0} else {$pair.item.1 | into int}))
  ]}
  | flatten

let defragged = (($memory | length) - 1)..(($memory | filter {$in != .} | length))
 | reduce --fold $memory {|i, acc| 
    let space = $acc | iter find-index {|$i| $i == .}
    $acc | update $space ($acc | get $i)
      | update $i .
  }

$defragged | enumerate
  | reduce --fold 0 {|i,acc| $acc + ($i.index * if $i.item == "." {0} else {$i.item | into int})}

Fascinating, thanks for taking the time to write this up.

My rust code ran in 6s on my phone (Samsung A35 running under Termux). When I’m back at a computer it’d be interesting to compare times properly.