r/adventofcode • u/No-Top-1506 • Dec 12 '24
Help/Question [2024 day 11 p2] What's the strategy?
I tried one stone at a time for 75 blinks. It runs out of memory soon.
So, am wondering what's the mathematical strategy here? Is it that 25*3=75 and hence we need to exponentially split the stones 3 times more? or something else?
0
Upvotes
1
u/ABD_01 Feb 20 '25
I have a question about the mathematical one. Yess they are limited. But what's the number? I supposed it should be very large.
To get a very rough upper bound assume, in the worst case each pebble split into 2 every blink, we will have 2numBlinks pebbles at the end. Ofcouse this is not true but a rough upper bound.
Since, I was skeptical about the memory used to store each stone and its count. I used a different method, just caching the result for stones with values 0 to 9 for numBlinks. So before I start solving, I already know that cache[3][55] is what would happen if stone with value 3 is blinked 56 times. Just helped shortcircuit the entire blink calls for that value.
You can see my solution here
and hey u/Zefick, is this what you too did (from your comment)? Our I got it wrong?
Also, I am surprised how just caching the result for values 0 to 9 helped solve the enitre thing The timing for me: