Advent of Code 2024 | Day 11 "Plutonian Pebbles"

[@m.e.6271]

I solved this one a bit differently. I didn't do it recursively, instead I used a dictionary to store the number of times a stone appears in a given step, so that I know that in the next step there will be as many of its "children", but I only calculate what that stone will turn into once per iteration. In the end I summed all of the values in the dict. It seems to be a bit slower than your solution but I just tested and I can still calculate 5000 iterations (in approx. 15 seconds), as I don't run into any stack problems.

[@flwi]

I did it the same 🎉 Tried it with 5k iterations and it runs in 1.2s. Guess I could still optimize it a bit more to figure out how to iterate over the hashmap and mutate entries at the same time. Cloning the map 5k times is probably the bottleneck.

[@treelibrarian7618]

nice method :) I prefer to the recursion, but only because I dislike function-call recursion and will go to great lengths to avoid it ;)

[@Dawnspell]

I realized that we don't care about the order of stones and that we only count the number. So, I did something similar as you, however I used the "Counter" class from "collections". Runs smooth as butter (~10s for 5000 iterations).

[@morningsage5673]

I also used this method with some caching and other optimizations for 5,000 iterations in 139ms. But in C# rather than python.

[@0_0...]

Hey Hyper, can't thank you enough for these vids while we're doing AOC 2024. I'm incredibly poor at programming compared to what you can come up with on the fly and following these videos really shows me how deep programming can be. (I'd been bruteforcing all the daily challenges up to day 10 without using common DSA/Algo practises and writing my own super janky hyperspecific algorithms for each day for sometimes up to 12 hours or more) If anyone has any tips on how to "git gud" I'd love to get some advice.

[@AledD2000]

Just watching and making sure you truly understand the solutions in these videos (after doing your own ideally) will go a long way! Leetcode is also a great way to improve general problem solving and algorithms , again by trying yourself , if you can’t get it , properly understanding ideal solution from someone like Neetcode. Good luck!

[@pmareke]

Great use of the @cache, I didn't think about it!

[@Meridian-lk2fo]

I watched until about 4:50 and then the problem with my code clicked for me, and I was able to solve it. Thanks!

[@flwi]

Really clever approach. Didn't think about that

[@klipronhoward]

I used a Counter to track totals for each iteration and was able to to 2000 iterations without a problem.

[@gorkemeldeniz9579]

Great approach i implement my own cache logic in javascript

[@Em.2-9188]

3:56 :3

[@TheFrogfather1]

On looking at the puzzle I realised 3 things. 1) It was probably going to involve recursion 2) Part 2 was bound to involve the same puzzle with a much higher number 3) I didn't know how to implement anything other than a fairly naive solution So thank you for your video - I initially tried without a cache and, as expected part 2 takes an impossibly long time. Since I'm working in Object Pascal there isn't (afaik) any built in cache so I had to write my own. Since this is based on arrays it isn't particularly fast but got the time for part 2 down to 19s.

[@yajusgakhar6969]

I used math.floor and math.log10 to find the length of the number and dividing the number in half faster because I remember in one of your vids you mentioned string computation is quite slow in Python. Here's the forumula -> from math import floor, log10 half_digits = floor(log10(number) + 1) // 2 divisor = 10**half_digits return elem // divisor, elem % divisor

[@yajusgakhar6969]

I also used PyPy and my answer came out in an instant after implementing your cache method. Thanks!

[@derechtepilz]

Interesting. We have the exact same solutions for this puzzle. I wonder if the inputs are the same too or if it's just a coincidence.

[@dernett]

A slightly harder problem: given an index `i`, find the value of the `i`-th stone in the ordered list after blinking 75 times.

[@treelibrarian7618]

but only slightly: the recursive memoised approach can still be used but along with the value, pass in the number of stones so that when the memoised value would take the total over i you follow down into the stack anyway until reaching the bottom at stone i.

[@taxatogaming]

I dont know if youve done this already but can you walk us through your setup? Like your input() function and what happens when you call aoc in your console

[@mikoaj1349]

I rely on specific file names, let's say for day 11 the code is in 11.py, input in 11_sample.txt and 11_data.txt respectively, and functions for both parts are named part1 and part2. Then I created a decorator which - with a bit of Python magic - extracts the names of a function and a file, then reads input from a correct file and finally runs the calling function with read input as its argument. And it even checks if the result is correct on the sample input. :)

[@mihirbpi]

I can do a max of 996 blinks before I get a recursion error using DP/caching

[@mikoaj1349]

I must say I didn't like this problem. Finally I came up with the same idea as you, but with those strange rules of generating new stones there was no reason to expect that we'll have a lot of repeating numbers, which would facilitate using a cache. What I tried first was using paralel computations (because, as you've said, each stone can be processed independently). And when that didn't work I tried to limit the creation of new strings by working with tuples (original value, start, end) in order not to generate new strings on splitting. But ultimately dynamic programming out of the blue prevailed...

[@hyper-neutrino]

fair enough. just out of curiosity, i ran a test, and if you start with a 0 and keep going indefinitely, you only reach 54 unique stones after less than 20 iterations so i suppose it does make sense that the number of unique numbers does not grow too fast. i do agree that it's not necessarily expectable, but when you see iteration numbers that high, it's kind of a pattern that you eventually pick up that this sort of dynamic programming / cached recursion approach is standard

[@diojoestar5178]

:3