Advent of Code 2024 - Day 22

Learning Questions & Discussions Coding Challenges
,
21

Yeah, it’s C#. I’m not as fluent with elixir, but here’s the immutable implementation of my latest strategy (using mostly linq query syntax – hopefully, the logic comes through):

    var bananasByPricing =
        from initialMonkeySecret in initialBuyerSecrets
        let monkeySecrets = EvolveRep2001(initialMonkeySecret)
        let bananaPricePoints =
            from pricing in Pricings(monkeySecrets).DistinctBy(pricing => pricing.Key)
            select (pricing.Key, bananas: pricing.Bananas)
        from bananaPricePoint in bananaPricePoints
        group bananaPricePoint.bananas by bananaPricePoint.Key
        into pricePointBananas
        select (totalBananas: pricePointBananas.Sum(), pricing: pricePointBananas.Key);

    var answer = bananasByPricing.MaxBy(p => p.totalBananas);

Notes: “Pricing” key is a 4-tuple on price differences (D1-D4 values), and the “bananas” result for that price point, EvolveRep2001 generates a sequence of 2001 secrets from the initial secret. DistinctBy and MaxBy will choose the first qualifying element in the sequence.

Apologies if you wanted elixir directly - I posted more on the comment/question about possible further optimizations that might exist. My original idea was noting that the sum could potentially short circuit using an aggregation/reduce step, that could stop early rather than continuing to add more bananas once it was determined that there would not be enough remaining pricing results to exceed a current running maximum. You’re correct to point out that it could be a very different performance characteristic on elixir, and while I agree that there are some algorithms that may suffer due to pure functional immutability, I do not believe this is one of them.

22

I was looking into the algorithm a bit, and if you convert it to bitshift operations it boils down to this:

secret = bxor(secret <<<  6, secret) &&& 2 ** 22 - 1
secret = bxor(secret >>>  5, secret) &&& 2 ** 22 - 1
secret = bxor(secret <<< 11, secret) &&& 2 ** 22 - 1

So it shifts left, right, left, XORing with itself and cutting off at 22 bits each time.
I was thinking maybe you could reduce it down to one operation, but the XOR prevents that. Or maybe it doesn’t… :thinking:

23

I tried but the gain was not measurable. I don’t know why but my machine gives very variable times of execution between runs. So it may have helped a bit but it was not really noticeable.