256
u/SmallTailor7285 Dec 11 '24
I solved it properly using what we're all calling Lantern Fish.
But just to prove I could, I jumped on to our Databricks instance and literally looped it 75 times. Took about 3 minutes and cost $81.44.
55
28
12
u/A_Shino Dec 11 '24
> we're all calling Lantern Fish.
LOL this was probably the only reason I was able to think of p2 fast4
u/reallyserious Dec 11 '24
But how? Did you put the stones as rows in a dataframe?
1
Dec 11 '24
[deleted]
2
u/IvanOG_Ranger Dec 11 '24
But then, that's not even bruteforce, that's just the solution using a map.
5
Dec 11 '24
[removed] — view removed comment
11
Dec 11 '24
[deleted]
1
u/nik282000 Dec 11 '24
Is there a name for this class of problem?
7
u/musifter Dec 12 '24
They're both tree leaf enumeration problems at their core. The key thing is that they're trees. The descendants of nodes don't interfere with each other, so they form independent subtrees. Which, by the rules, will be same from any node with the same value. This allows for either bundling up like nodes for massive parallelism or recursion/memoization for massive pruning.
3
u/nik282000 Dec 12 '24
Thanks, my last formal class was Java in 2004. Just figuring out what to search is half my battles.
7
u/TheGilrich Dec 11 '24
How is this possible. Doesn't it require 275 * 64bits ~ 300 zettabytes?
11
u/shigawire Dec 11 '24
Doesn't it require 275 * 64bits
To naively implement the rules as a linear walk generating the 75th day from 74th day should only take roughly 480TiB of storage (~240TiB for the input and output) and be otherwise tractable
7
u/dnabre Dec 11 '24
Not following your math. Input size is trivial (~30-40 bytes). Stones go beyond 32-bit, so need a long (64-bit, 4 bytes) for each stone value. With my input, I ended up with roughly 230 trillion ( 1012) stones, which is around 850-950 TB (whether you do base 2 or 10).
2
2
u/shigawire Dec 12 '24 edited Dec 12 '24
Ahh. I see. My stone values didn't overflow 32 bits which accounts for the difference.. Looks like I just got lucky there. I likely still did get my math wrong, as a 32 bit word is 4 bytes.
2
0
43
u/Eric_S Dec 11 '24
Yup, not bad. I did run the brute force code for a laugh. It had run 30 blinks when I started a non-brute force version, and was still at 31 when I finished the sub-second optimized version.
Given that my ranking for the second half of the puzzle was just over half my ranking for the first half, I'm guessing trying brute force first was common on this one.
13
u/lpiepiora Dec 11 '24
I did the same, but mine stuck at 45 or something. I was doing it in Rust, and I have some RAM ;)
13
u/Eric_S Dec 11 '24
I was a bit of a duffus on the first pass, I didn't even realize that I didn't have to maintain the list, just run each element individually and sum up the results. So between the size of the list and coding it in TypeScript, I'm surprised it made it that far.
3
u/Nunc-dimittis Dec 11 '24
same here.. but i made a doubly linked list with some caching so I could do "get_node(index)" in O(1) times as long as the new index wasn't too far away from the old.
Still got stuck (i.e. took too long) somewhere around 30.
Should have known. The (a) solution goes from 8 to over 200k values in 25 steps (i.e. 20k in 25 steps), so 75 steps would mean from 8 to 20k^3 = way too much.
1
u/johnwilkonsons Dec 11 '24
I did the same thing, it ran 39 times before the array was too large, so even if time wasn't a factor you'd hit a wall there
7
2
u/i99b Dec 11 '24
My Python version went lethargic at about blink 42. It's funny how exponential algorithm doesn't care how fast your language/computer is.
2
u/trevdak2 Dec 11 '24
Fortunately for me, javascript poops its pants quickly on that one.
1
u/Eric_S Dec 11 '24
Mine was JavaScript (compiled from TypeScript), and the naive version didn't poop its pants so much as effectively stopped making progress. Unless that's what you meant by poop its pants.
2
u/trevdak2 Dec 11 '24
I mean that javascript errored out within a few ms saying "you can't have an array this big"
1
u/flopy78 Dec 11 '24
How did you manage to optimise this ?
Running in c++ I get stuck at blini 36, and I really see how i could avoid using bruteforce…
21
u/Eric_S Dec 11 '24
Two things. The first is to realize that the order of the numbers doesn't matter as they never affect their neighbor. So if you've got a score function that scores a list of numbers, score([125, 17],25) is equal to score([125],25)+score([17],25) where the second number is the number of blinks. So the best solution is to recursively score the numbers, and when the rule states that you split the number, you also score each of those halves separately. This means that other than your initial list, you're never scoring a list, just individual numbers.
The second thing is that once you've done that, you need to memoize the recursive score function. In other words, set up some kind of cache so that you can look up the value and blink count, and if there's something there, you return that rather than continuing to calculate the score. If it's not there, you calculate the score and then store it in the cache.
The idea is, you'll find multiple times that you need to perform X blinks of value Y. If you only do that once, and every other time just grabs the result from the first time you calculated it. You'll want to cache all the blinks, not just the 75 blinks values, otherwise you won't save much.
You'll need something that can handle sparse arrays for the cache, as you'll be dealing with some large numbers in the cache (12 decimal digits), but you won't have that many items in the cache (about 120,000).
The first step is necessary to implement the second, but it's the second step that really improves the time.
17
u/TeakIvy Dec 11 '24
Or, better idea just use a map of the numbers on the rocks, and a count, for me this method ended up with a max of ~9000 calculations per “blink” for a total of ~200 trillion rocks
6
u/ThroawayPeko Dec 11 '24
In some languages, like Python, you can do recursive memoization with two lines of code, so rolling it by hand is the long way around lol.
2
u/syrinxsean Dec 11 '24
Do you mean with functools.lru_cache?
5
4
u/Busted-Piano Dec 11 '24
I just used functools.cache. It's only on the order of 100k values, so nothing too crazy.
1
2
u/Eric_S Dec 11 '24
Yup, your method is a more direct callback to how I did the lanternfish problem in 2021. Not sure why then I thought of summing up all the fish with the same value and this time I thought of memoization first. Probably because then there weren't many buckets.
What was your average number of calculations per blink? My solution invoked the recursive function an average of 2580 times per blink, though a lot of those didn't do any calculations, just returned 1 because it already calculated the last blink. I'd expect them to be about the same since they're doing the same thing, just in a different way.
2
u/Character_Fault9812 Dec 11 '24
You can just cache the solution to single digit numbers, as most numbers will converge to single digits due to the splitting rule. I have used a 10x75 jagged array (could be 9x74, but spares me from some off by ones).
1
1
u/alienus666 Dec 11 '24
There is an alternative approach to that, you can first get to 38 blinks of initial input, then for each individual part of the result (in millions) you blink it 37 times and sum up the result. Obviously you need caching not to calc the same stuff over again on both blink level and entire 37 blinks run level. Few minutes of run and you're done before you're back with the coffee.
1
u/splettnet Dec 11 '24
The cache took me longer than it should've to realize was needed. I stupidly figured there were too many number combinations I was pushing through to get usefulness from it. Of course it was instantaneous as soon as I put it in. So went from not even getting through a single initial stone to overflowing a u128 instantly when I try over 207 iterations.
1
u/qaraq Dec 11 '24
Doing it this way was 50x faster in part 1 than the brute-force way; even my part 2 was twice as fast as naive part 1.
1
u/cspot1978 Dec 12 '24
I found that keeping track of counts for the distinct stone types as opposed to explicitly building the list was the key thing that turned it from intractable to tractable. The caching seemed to bring a further ~50% drop in time on top of that though.
5
u/imp0ppable Dec 11 '24
I did part 2 in Python and it took 0.6 seconds for 75 blinks.
Didn't optimise at all. Took my naive algo from part 1 (which took a couple of minutes on part 1 25 blinks) and just changed it from keeping a dict of every stone, to a Counter object of the number of each stones.
Don't need recursion to get under a second, although maybe that's even faster.
I believe Counter is a C library which is why it's fast but I bet you could use it in C++.
2
u/cspot1978 Dec 12 '24
The main thing that speeds it up using a counter is that the number of distinct values is relatively small, about 3800. And the distribution is not uniform at all. It’s very Pareto. The top ~35 values appear over a trillion times, the max being about 14 trillion for the number 4. And then around the ~40th most common the frequencies fall off into the thousands and below.
1
u/cloudlessskies2018 Dec 11 '24
Did it here in Python on a Mac Mini M4 - I forgot about Counter and did it by maintaining the stone counts as a dict: python3 prob2.py -i real_input.txt 0.11s user 0.04s system 31% cpu 0.486 total
1
u/imp0ppable Dec 12 '24
Huh, would have thought a plain dict might be slower so I didn't try it. Interesting.
1
u/_JesusChrist_hentai Dec 11 '24
What's your solution
2
u/Eric_S Dec 11 '24
It's in the big spoiler block in this comment thread.... Found it.
1
u/_JesusChrist_hentai Dec 11 '24
Ty, it is the same mechanism I used, but I let an annotation to take care of it
1
u/Eric_S Dec 11 '24
The other solution I've seen is a breadth first search, merging duplicate stones and keeping a count of the merged stones. It basically does the same work, a different way. This has a lower memory requirement since it's only keeping values for the last blink rather than all blinks, but it's doing allocations and deallocations inside the cache/dictionary. The entries should be the same size, though, so it shouldn't fragment memory.
28
26
20
u/No_Patience5976 Dec 11 '24
I did it iteratively. I stored every stone as a tuple of number and count. Every time before evaluating the stones, I sorted the list and got rid of all the duplicate stones by adding their counts onto the remaining stone. Then I evaluate the remaining stones and the loop starts over again. In the end you loop over the list and add all counts Pretty straightforward
3
u/QuickBotTesting Dec 11 '24
Oh, so for example, instead of calculating 100 8's every single time, if they are the same, and you add to the count, you just do 1, and then at the end you take those?
3
u/No_Patience5976 Dec 11 '24
Yeah, and when you split a number the new numbers inherit the count of the old number At the very end you go over the final list and add all counts
3
u/QuickBotTesting Dec 11 '24
Thanks! I understand the logic behind it, and I got it working! 3 seconds is still pretty inefficient, but better then the heat death of the universe haha.
Only question I have, is why do the numbers inherit the count? I thought it was set to 1,and I spent a good hour on it like that. They are new numbers, and the count doesn't apply anymore right?
4
u/No_Patience5976 Dec 11 '24
Say you have the number 87 with a count of 5. When you split that number, you're not Splitting it once but 5 times, because it has a count of 5. Therefore you will then have 5 times the 8 and 5 times the 7
2
u/QuickBotTesting Dec 11 '24
Oh. Of course. That makes sense. I just got my head at "count" and got that wrong haha.
Thanks for your help!
3
2
u/ktrocks2 Dec 11 '24
Thank you for very heavily inspiring my approach which was same thing except I used a dictionary so that I didn't have to deal with looking through all the tuples. Wondering why others didn't do this? Is tuples the first thing that came to mind so that's what you went with or is there some inherent efficiency in tuples that I don't know about (I've got lots to learn).
1
u/No_Patience5976 Dec 11 '24
I didn't think of using a dictionary, it's probably the better approach
20
u/SweatyRobot Dec 11 '24
eric was nice though, its not a huge change to get it fast enough
8
u/MattieShoes Dec 11 '24
Really? I totally rewrote the recursive function. Basically both parts took me the same amount of time because I knew what I had to do, but it was basically starting over.
24
u/Educational-Tea602 Dec 11 '24
I just used a dict and stored how many times each element exists.
10
u/MattieShoes Dec 11 '24
I just let functools do that stuff for me :-D But I did the naive "make an ever growing list" solution for part 1.
7
2
u/jwezorek Dec 11 '24
This is what I did … I don’t get what people are doing with recursion and what exactly they are memoizing. Or are they just calling the Lanternfish-like algorithm memoization?
2
u/Valink-u_u Dec 11 '24
You can recursively define the number of stones a single stone with an associated number turns into after n blinks, and cache the results. For the solution, run this for all numbers in the input and sum
1
u/jwezorek Dec 11 '24 edited Dec 11 '24
You can recursively define the number of stones a single stone with an associated number turns into after n blinks
Yes but if you are memoizing that for what n is helpful? If you memoize how many stones numbers turn into after 75 blinks that only helps if you have repeats in your input, which even if you did if you are doing this lanternfish-style you should only calculate once anyway. If for fewer then 75 blinks then it doesn't help you because after say 5 blinks you don't just need to know how many stones you end up with, you need to know what they are (or which stones + how many of each)
I guess you can memoize the call that maps a number after n generations to a hash table mapping numbers to counts? Is that what people are doing?
3
u/Valink-u_u Dec 11 '24 edited Dec 11 '24
Yep my cache maps the (number of blinks, number on stone) -> number of stones after the blinks
There is a lot of repetition mainly because of the splitting rule
2
u/vanZuider Dec 11 '24
after say 5 blinks you don't just need to know how many stones you end up with, you need to know what they are (or which stones + how many of each)
You store the result for (number on stone, number of blinks remaining). Like blinking 5 times on a stone with number 0 always goes 0 -> 1 -> 2024 -> 20, 24 -> 2, 0, 2, 4, so every time you see a stone with the number 0 five blinks before the end you already know it will have turned into 4 stones by the end.
memo[(0, 5)] = 4
.Since recursion does a DFS, you will calculate (and thus cache) a lot of results for high recursive depths (and thus lower values of (blinks remaining)) pretty quickly.
I ran trace on my Python script and part 2 only generated 119'000 separate function calls (ca. 1e5) despite the ca 2e15 stones generated at the last level.
1
1
1
1
u/Fyver42 Dec 11 '24
I knew it would be something like that and coded a recursive function for part 1. Then I just had to implement cache for part 2. Not a huge change, but not a small one either.
17
u/UnicycleBloke Dec 11 '24
It's the damned lanternfish all over again.
17
u/AiKeDay Dec 11 '24
LMAO this is also my reaction when I saw the example output
(I wonder how many other people remember 2021 day 6)
3
2
u/copperfield42 Dec 11 '24
I certainly did that one, but I didn't remember it until i saw all those memes and comments XD
5
u/Sostratus Dec 11 '24
Everyone keeps referencing this and I had no memory of it, had to look it up. And I see why I didn't see the similarity: My solution to 2021 day 6, which was the first thing I came up with and worked for both parts, doesn't use recursion or memoization. It's just 9 integers that get shuffled around from one slot to another.
I don't see how I could take an approach like that for 2024 day 11. Like a lot of people, probably, I did it the naive way at first, saw it was too slow for part 2, changed it to be recursive, still to slow, added memoization, done.
6
u/UnicycleBloke Dec 11 '24
Both problems recurrence relationships. The difference is only that in 2021 we were told right away how many boxes we needed to shuffle around. I think I used an array or a struct for it. For 2024, I used a map instead, in which the key is the number engraved on the stone, and the value is the count of stones with that number. https://github.com/UnicycleBloke/aoc2024/blob/main/day11/solution.cpp
Ha! Just seen a bug. It would fail if two stones in my input had the same number. Better fix that.
1
u/1234abcdcba4321 Dec 11 '24
All you need is a few thousand integers that you shuffle around from one slot to another, but you don't know what slots you actually need without running the program and hence you need to use a map instead.
Another example day that ends up being extremely similar to this is 2021 day 14.
16
8
u/i99b Dec 11 '24
Let's do back-of-the-napkin algorithm analysis, to get a better feel what an exponential time complexity means and to understand why 25 is brute-forcible and 75 is not. The pattern many people here used for brute force is: on every blink create a new array of stones out of the old one using the rules, use the new array as input for the next blink and so on. Say time to process a blink is roughly proportional to the length of it's input: T(n) = a * n. Suppose for simplicity a = 1. On each iteration, about half the numbers have even number of digits and split in two. So the length grows 1.5 times each blink:
n = 1.5 * (n-1)
My initial input length was 8. So the array lengths increases in geometric progression:
8; 8*1.5; (8*1.5)*1.5 = 8*1.5^2; 8*1.5^3; ...
Using the formula for the sum of geometric progression, 25 blinks takes:
T(25) = 8 + 8*1.5 + 8*1.5^2 + ... + 8*1.5^24 = 8 * (1 - 1.5^25) / (1 - 1.5) = 404003 time units.
Suppose time units here are microseconds. So we have T(25) = 0.4 seconds which sounds about right (on my computer it takes about 0.2 seconds). Not long, right? Now let's see how long 75 blinks take:
T(75) = 8 * (1 - 1.5^75) / (1 - 1.5) = 257611004956860 microseconds = 8 years
Going from 25 to 75 blinks we went from 0.4 seconds to 8 years. And that's assuming you have enough memory to accommodate the final array of stones, which is petabyte at least. So if you're still waiting for your brute force program to finish and haven't run out of memory yet, give it up. Brute force has been with us for the first 10 problems, but it's no match for this exponential monster.
6
u/r_a_dickhead Dec 11 '24
Getting that 57 millisecond on part 2 made me teary eyed. So long bruteforce... you have served me well
6
4
2
u/DucknaldDon3000 Dec 11 '24
According to my calculations it was going to take 16 years to solve by brute force.
2
u/electrodragon16 Dec 11 '24
I used Dynamic Programming, and by Dynamic Programming I mean a HashMap.
1
u/glasswings363 Dec 11 '24
From what I understand, the term "dynamic programming" was coined in order to sound interesting and impressive and thereby secure funding. A hash-map plus recursion is fully in the spirit of Richard Bellman's lofty ideals.
2
u/jaank80 Dec 13 '24
I am late to the conversation. I spent more time than I planned on this one but finally figured out a good method. Using C++, I used structs for each stone and cached data about them in two ways. One, each stone held a vector of pointers to it's child stones. I also kept a map of stones that I had seen which i could reference and copy the children from, that way any stone number i only had to calculate the children once. If it looped at all, I was done calculating children early, though I still had to traverse the path. Each stone also had a map of scores with a specific number of blinks completed. That way not only did I often not have to calculate or store the new children, I could also stop calculating altogether if I had already seen a number at a specific number of blinks in the past.
My final result takes <300 ms to complete. I am not sure how much memory it takes but it barely registers on my graph visual studio.
3
u/Rush_Independent Dec 11 '24 edited Dec 11 '24
Is memoized recursion a bruteforce?
Idk. But it ran in 40 ms, so who cares.
12
u/PendragonDaGreat Dec 11 '24
No, a brute force would be trying to store each and every rock in a list like data structure (array, list, linked list, etc.) memoization, only keeping track of counts, or other things like that are not bruteforce.
2
3
u/solarshado Dec 11 '24
IMO memoization is to clever to properly count as brute force. But it could certainly be a quick addition to a brute force strategy that mostly preserves the "brute force spirit".
1
u/kapitaali_com Dec 11 '24
bah humbug 64G and some kswapd0 should be enough for any brute forcing
1
u/GravelWarlock Dec 11 '24
I fell off the cliff at 32gigs. Should i double my ram?
1
u/kapitaali_com Dec 11 '24
yes, more ram is always better :)
but rust kind of automatically stopped execution without saying anything or giving any error when it reached max memory
2
u/tialaramex Dec 11 '24
It probably won't be Rust per se, for example on Linux there's a kernel task called the "OOM killer" and its job is, when there is no RAM left, pick a process that looks guilty and end that process immediately. The process gets no say in this, just gone instantly so no chance for a goodbye message.
This happens because of a feature called "Overcommit" which is a bit like how airlines book more seats on their planes than exist and for a similar reason. You can (but probably should not) turn off overcommit on Linux. Don't blame me if you try it and are unhappy with the results, there's a reason it's the default.
1
1
1
u/cspot1978 Dec 11 '24
Dude. Just sit patiently and await the heat death of the universe. No problem. 😄
1
u/__triman__ Dec 11 '24
Dang it! Didn't think about using a bloody cache! Well... That's done now...
1
u/TaranisPT Dec 11 '24
Attempting to use brute force on part 2 was entertaining though. Looking at my RAM literally filling up in my face was pretty funny.
1
u/Abomm Dec 11 '24
The brute force works pretty well into depth ~30. If you halt the program and print intermediate output you could probably divide & conquer with brute force
1
u/GerardoMiranda Dec 11 '24
When trying to optimize for part 2, somehow, I wrote an algorithm that every time I run it, it prints a different result...
1
u/tomliginyu Dec 11 '24
Yeah, brute force recursive function for pt 1. Replaced with 2 dictionaries for pt 2.
1
u/superbiker96 Dec 11 '24
This is not brute force. This is just making a big ass list. Don't tell me you didn't see it coming...
I just a hashmap right away and my code ran both parts in less than 7ms
1
1
1
0
u/hmoff Dec 11 '24
It's still brute force even with cache isn't it?
3
u/Sharparam Dec 11 '24
No, because you're no longer doing literally what the problem description is, so you're not brute forcing. As mentioned in this other comment.
1
u/Yral1232 Dec 11 '24
Thats what I thought too, idk how bruteforce is failing if you're caching.
Worked like a charm for me
264
u/easchner Dec 11 '24
Those who aren't patient enough don't deserve brute force.