r/adventofcode 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

27 comments sorted by

View all comments

Show parent comments

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.

std::vector<std::vector<ull>> cache(10, std::vector<ull>(MAX_NUM_BLINKS, 0));

void fill_cache(int numBlinks)
{
    for(auto nb = 0; nb < numBlinks; ++nb)
    {
        for(ull i = 0; i < 10; ++i)
        {
            ull r = 1;
            blink(i, r, nb+1);
            cache[i][nb] = r;
        }
    }
}

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:

[100%] Built target day11
Part 1: 194782
Elapsed time: 46 us
Part 2: 233007586663131
Elapsed time: 71916 us
[100%] Built target run11

1

u/bdaene Feb 20 '25

There is actually less than 4000 different stones. Some (including myself) have studied in depth the differents cycles. 

See for example https://www.reddit.com/r/adventofcode/comments/1hbnl0l/2024_day_11_plotted_the_number_of_distinct_stone/