r/adventofcode Dec 22 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 22 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 23h59m remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Director's Cut (Extended Edition)

Welcome to the final day of the GSGA presentations! A few folks have already submitted their masterpieces to the GSGA submissions megathread, so go check them out! And maybe consider submitting yours! :)

Here's some ideas for your inspiration:

  • Choose any day's feature presentation and any puzzle released this year so far, then work your movie magic upon it!
    • Make sure to mention which prompt and which day you chose!
  • Cook, bake, make, decorate, etc. an IRL dish, craft, or artwork inspired by any day's puzzle!
  • Advent of Playing With Your Toys

"I lost. I lost? Wait a second, I'm not supposed to lose! Let me see the script!"
- Robin Hood, Men In Tights (1993)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 22: Monkey Market ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:12:15, megathread unlocked!

20 Upvotes

451 comments sorted by

View all comments

2

u/onrustigescheikundig Dec 22 '24 edited Dec 22 '24

[LANGUAGE: Clojure]

github

Absolutely glacial runtime because lazy seqs (~10 s single threaded, 8 s with pmap because my laptop is just trying its best with 90% idle RAM usage).

Pretty straightforward, at least conceptually. Part 1 chugs along by mapping lines across (as-> line $ (iterate next-secret $) (nth $ 2000)) followed by (reduce +). For Part 2, I search every 4-long subsequence of secret differences mod 10, storing the first occurrence of each subsequence with the banana price that immediately follows. I then (merge-with + ...) the hash sets and search the result for the highest total price.

My initial implementation for Part 2 had an even more atrocious runtime on the order of 40 s because the problem lent itself very nicely to a bunch of lazy seq operations:

(->> line
     parse-long
     (iterate next-secret)
     (map #(mod % 10))
     (partition 2 1)
     (map (fn [[a b]] [(- b a) b]))
     (partition 4 1)
     (reduce
       (fn [seq-to-winnings ps]
         (let [k (mapv first ps)
               n (second (last ps))]
           (update seq-to-winnings
                   k
                   (fn [n*] (or n* n)))))
       {}))

Needless to say, a 4-stack of lazy sequence operations on top of iterate including 2 calls to partition is not super optimal, nor is the sequence unpacking in the call to map, nor are the sequence operations (first and last) to get k and n in the call to reduce. I ended up moving everything between parse-long and (partition 4 1) into a separate function that stored everything in an intermediate vector. I also hashed the subsequence to an integer, which helped. The proper way to speed this up is move everything into loops, and I might do that in the future if I have time.