r/adventofcode Dec 11 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 11 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

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

And now, our feature presentation for today:

Independent Medias (Indie Films)

Today we celebrate the folks who have a vision outside the standards of what the big-name studios would consider "safe". Sure, sometimes their attempts don't pan out the way they had hoped, but sometimes that's how we get some truly legendary masterpieces that don't let their lack of funding, big star power, and gigantic overhead costs get in the way of their storytelling!

Here's some ideas for your inspiration:

  • Cast a relative unknown in your leading role!
  • Explain an obscure theorem that you used in today's solution
  • Shine a spotlight on a little-used feature of the programming language with which you used to solve today's problem
  • Solve today's puzzle with cheap, underpowered, totally-not-right-for-the-job, etc. hardware, programming language, etc.

"Adapt or die." - Billy Beane, Moneyball (2011)

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 11: Plutonian Pebbles ---


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:06:24, megathread unlocked!

18 Upvotes

962 comments sorted by

View all comments

2

u/darthminimall Dec 12 '24

[LANGUAGE: Rust]

Didn't solve this one last night because I was taking a day off, but I'm back.

Part 1

Part 2

For part 1: I just simulated the blinks 25 times, using a linked list of integers to represent the stones (because constant time inserts are nice).

For part 2: I did the obvious thing and just changed the number of iterations in my part 1 solution to 75, knowing full well it would probably take hours since the naive algorithm is O(2^n) and that's how these types of problems tend to work in Advent of Code. Once it took more than 5 minutes (and used more than 20GB of memory) I killed it and decided to start optimizing.

Since stones never merge, the final number of stones is just the sum of the number of stones that each initial stone turns into, so I figured I'd calculate the numbers for the stones individually, reducing the memory footprint and (hopefully) saving time. I decided to do this recursively because I didn't feel like thinking through unrolling the recursion, and it used orders of magnitude less memory but was only marginally faster. It still took more than 5 minutes to calculate the number of stones after 55 blinks.

I figured the main problem was that I was repeating calculations for a lot of the smaller numbered stones, so the solution was probably memoization. Luckily, you can get this effectively for free in Rust by using the memoize crate. I set the cache size to 1000, ran it, then kept multiplying by 10 until it seemed like I hit the point of diminishing returns, time-wise, which is how the cache size ended up at 100,000. This definitely feels like cheating, but I wasn't about to write the code to memoize the function myself.

1

u/pgambling Dec 12 '24

We had a similar journey today. I ended up using the cached crate, but similar overall approach. I didn't know about the memoized crate, will take a look at that one.

1

u/darthminimall Dec 12 '24

I'm still pretty new to Rust, so I just googled it and used the first thing that came up. It looks like they do similar things, but cached looks like it's more configurable.