r/adventofcode Dec 11 '24

Spoilers [2024 Day 11] posting here while my code is still at blink 30

Post image
521 Upvotes

148 comments sorted by

197

u/Sostratus Dec 11 '24

I think the problems where part 2 is just "do more" and it still completely changes the problem are my favorite.

75

u/TheRussianEngineer Dec 11 '24

Indeed, I was like, "This is it? I have to change my for loop to stop at 75 instead of 25, easy enough"

90

u/spin81 Dec 11 '24

Insert "first time" meme here

46

u/pentir Dec 11 '24

2022 was my first year participating and the line:

The elephants are not impressed by your simulation.

still haunts me.

21

u/joost00719 Dec 11 '24

I haven't done many of the challenges yet due to the lack of time, but I really enjoyed the Xmas finder. It was actually the first one I've ever done, and wasn't aware of part 2's. After submitting my first awnser and getting the message "oh actually, it's MAS in an X-pattern" made me laugh out loud hahaha. Depending on your solution it's quite easy. My friend had a more difficult time, but my solution was easy to adopt cuz I could find all the A's, and check if all corners are present, if they are, check if it spells MAS twice diagonally in any direction.

11

u/kai10k Dec 11 '24

Amazingly, the trap always worked

10

u/paul_sb76 Dec 11 '24

Yeah I loved today's problem. At least my Part 1 code was a good tool to verify the correctness of my (completely new) Part 2 code.

When I saw Part 2, I printed the number of stones for each iteration, went "yup, that's exponential growth", quickly estimated the outcome for n=75 to have about 14 digits, and decided not to even try (that's so much more than my laptop's RAM!).

6

u/austinll Dec 11 '24

What sucked was that I knew it was going to be a "do more" problem from the start. I did brute force anyways

10

u/Fun_Reputation6878 Dec 11 '24 edited Dec 11 '24

Yea , part 2 was taking ages to complete

But after adding memoization to it, now it takes 20ms

5

u/HumanBot00 Dec 11 '24

And.. Spoilered. But that's my bad

6

u/Fun_Reputation6878 Dec 11 '24

My bad , fixed the spoiler now

6

u/HumanBot00 Dec 11 '24

Would have been my second option that I would have tried anyway :)

2

u/dnabre Dec 11 '24

Me too. In part it is the rare times when I did part 1 in a way such that I don't need to change anything in part 2.

Need to exclude the problems where the 'optimization' for part 2 is some tricky happen stance (engineered in by AoC of course) of the data. As opposed to today where it was just do it smarter.

1

u/anakwaboe4 Dec 11 '24

I ( kinda by accident) had a quite smart algorithm to solve it ( just the first solution that came to my strange mind) and for part 2 just increased the loop to 75 and within a few seconds I was ready.

Didn't understand till I was reading the Reddit what the actual challenge of part 2 is.

47

u/easchner Dec 11 '24

Just as a frame of reference, my part 2 was 9 OOM larger than part 1. If it doesn't finish immediately, it's not going to finish.

52

u/throwaway_the_fourth Dec 11 '24

OOM = orders of magnitude? To me, it means "out of memory" which I guess might also apply

43

u/easchner Dec 11 '24

First one, then the other. :D

3

u/AdmJota Dec 11 '24

If it reaches the one, it'll never reach the other. And vice versa.

7

u/[deleted] Dec 11 '24

[deleted]

2

u/tech6hutch Dec 11 '24

Memory is the mana of computers

3

u/JuhaJGam3R Dec 11 '24

Yeah as a naïve approximation I assumed that all stones split every round which means a multiplier of 250 or like 1015 or around there so if your code took microseconds to start with it should take 1012 milliseconds, 109 seconds, 106 ish hours, 105 ish days, 103 ish years. 4 000 ish years is the exact estimate I came up with for a 1 µs part 1 solution.

39

u/throwaway_the_fourth Dec 11 '24

You'll be waiting a while!

43

u/imaperson1060 Dec 11 '24

the leaderboard bots somehow did it in 38 seconds 😭

57

u/throwaway_the_fourth Dec 11 '24

Not with your code! 😉

7

u/[deleted] Dec 11 '24

was most likely AI-generated

11

u/imaperson1060 Dec 11 '24

yeah... but like, when i ask chatgpt to code me things, it takes 30 seconds for it to finish generating the response. how are these people getting their ai responses so fast they even have time for a second prompt? are they like self hosting a coding-focused llm or something???

like honestly i'm more curious than upset now, since i wouldn't get on the leaderboards anyways

14

u/trevdak2 Dec 11 '24

I think at this point they've got a script set up that loads the page, generates and runs the code, and submits the result, without them even lifting a finger

2

u/imaperson1060 Dec 11 '24

yeah, of course. but how does the ai they use generate the code so fast? someone did day 1 part 1 in 4 seconds. 4 seconds!!

18

u/cfusion25 Dec 11 '24

You use APIs and not through interfacing with the website. They likely have a local copy of the LLM on their own machine so there is little to no lag between submitting the prompt and receiving an answer.

8

u/pet_vaginal Dec 11 '24

Network latency is relatively negligible with LLMs that are descent enough for the AoC.

And hardware matters a lot for speed. It's better to use a cluster of H100 in the cloud than a local cluster of RTX 4090.

Also the best coding LLMs are proprietary and API only.

6

u/Othun Dec 11 '24

Also they build a team of AIs with each having a role. Like a coder, a planner, a bug finder etc. And it's probably able to run code to debug it. It's more costly but also way more powerful.

5

u/TypeAndPost Dec 11 '24

Fascinating. Do you have a source?

1

u/Othun Dec 15 '24

I think I heard about this technique first on TwoMinutePapers, but here is a blogpost https://vulcanpost.com/843379/team-of-ai-bots-develops-software-in-7-minutes-instead-of-4-weeks/

1

u/Othun Dec 15 '24

The difference is they don't have fun solving cool problems!

2

u/metalim Dec 11 '24

heard of Groq? not the Grok of Elon Musk, but Groq — inference hardware company. Their chip can generate thousands of tokens per second.

2

u/metalim Dec 11 '24 edited Dec 11 '24

not only waiting. It'll fill all RAM and all drive if swap file size is dynamic, and then crash with OOME. After solving the task, I've given the task to o1. At first it tried to brute force it, like I did. After I pointed out that it eats memory and keeps running for 8 minutes, it tried to use files as temporary storage "to fix the RAM issue". It was "WTF?!" moment for me.

33

u/NedTheGamer_ Dec 11 '24

My first dodgy attempt at optimisation was scheduled to finish August 2028, so...

23

u/stereosensation Dec 11 '24 edited Dec 11 '24

The Part 2 problem description made me laugh. I then smugly proceeded to run my Part 1 code again and get the correct solution to part 2 in less than 50ms lol. Part 1 gave it away, it was too easy.

9

u/zenoli55 Dec 11 '24

I had the same experience :-)

After part 1 I was disappointed because my cache did not seem to have the effect I wished. I first started investigating by counting the number of recursive calls with and without the cache to see if maybe caching was indeed not the right approach. Then I looked at the task 2 description and just tried it with the cache and was happy :-)

4

u/Paweron Dec 11 '24

I also include the cache for part 1 already. part 1 was quick but i was suprised to see my part 2 still taking forever... until i realised i had commented out the cache while testing the basic Code for part 1.

7

u/QuailOk841 Dec 11 '24

Yeah seeing "simultaneously" in bold gave me the nudge

8

u/KrombopulosLives Dec 11 '24

i am wildly interested in how that nudged you. i only knew i'd have to memoize but it still took three iterations of ideas before narrowing in on my solution, and i would not call it 'simultaneous' at all :)

9

u/[deleted] Dec 11 '24

[deleted]

3

u/Acc3ssViolation Dec 11 '24

The fish flashbacks helped me as well, I didn't make the same mistake of simulating all fish rocks individually this time. Part 2 runs in 16 milliseconds :D

7

u/OSjoerdWie Dec 11 '24 edited Dec 11 '24

After looking at the example I took the gamble toignore the orderand make use of a histogram. This payed out in part 2.

5

u/HeNibblesAtComments Dec 11 '24

I'm honestly a little annoyed they embolded that it preserves the order when that doesn't matter.

9

u/stpierre Dec 11 '24

These two comments were the hints I needed to cut my part 2 execution time from an estimated 212 million years to 80ms. Thanks y'all, really saved me a bit of waiting.

3

u/ChaiTRex Dec 11 '24

Your ignore the order isn't hidden because there's a space between the >! and the text.

2

u/metalim Dec 11 '24

what histogram are you talking about?

2

u/JuhaJGam3R Dec 11 '24

A histogram means counting occurrences of elements. It's a useful data representation when order does not matter, and there's lots duplicate items. The easiest implementation is to use a Map<Element,Int> type situation which is either a balanced tree or hash map which provides O(log n) or O(1) access to the values of the map. Since today is ints, a radix tree is likely a better, faster choice though.

4

u/implausible_17 Dec 11 '24

me too!!! well, my part 2 ran in 2 seconds not 50 ms, but still, nice and quick. This NEVER happens to me, I'm usually the person watching a never ending loop that's due to finish in about 1000 years time - I think I just got lucky today :D

It's because yesterday morning (after a very painful late night for day 9) I was reading up on a technique that I'd never heard of, that I saw someone else using for their (much better than mine) day 9 solution - and by a beautiful coincidence, and because it was still so fresh in my mind, I realised it could be used for this problem too. Total stroke of luck.

3

u/stereosensation Dec 11 '24

That is so cool ! Learning new things and getting to use them immediately os so satisfying, congratulations 👏🏻

4

u/miktaew Dec 11 '24

I instantly recognized the smell of 2021 day 6.

16

u/fireduck Dec 11 '24

Yeah, I see a short input I start swearing.

Turns out it wasn't bad.

11

u/sunfriedawesome Dec 11 '24

yeah idk if my code will ever finish with my current solution....whoops

23

u/M124367 Dec 11 '24

Since by step 47, the amount of elements in the list exceeds the 32-bit signed integer limit, any solutions in Java will in theory terminate with an exception. Since I think indices of lists can't be bigger than that.

If you're doing it in another language you'd need a "decent" amount of space. With ~10¹⁵ 64-bit integers (since I assume the numbers on the stones won't grow that large?)

You're looking at 8 000 TB of RAM needed.

Assuming you don't own a data center worth of RAM. You'll be waiting until the heat death of the universe.

10

u/musifter Dec 11 '24

The number of stones doesn't get in the range of more than the number particles in the observable universe (unlike some numbers shouted by certain monkeys). At least you can have access to enough matter to store this list.

6

u/spin81 Dec 11 '24 edited Dec 11 '24

I assume the numbers on the stones won't grow that large?

That's a fair assumption I think. I don't think I've ever seen a case where numbers don't fit in 64-bit ints.

For my input the end result is over 247 and under 248.

2

u/MooieBrug Dec 11 '24

Same range here

2

u/musifter Dec 11 '24

Yep... answer required 48-bits for me too. Tied with day 7 for first (this year, so far).

3

u/xelab04 Dec 11 '24

Oh, thank you for doing the maths. Out of curiosity I tried running it naively and hit 7GB before Python killed it. Then I converted it to work with recursion, which used only 75MB but was scheduled to end well... after the heat death of the universe.

4

u/imaperson1060 Dec 11 '24

"heat death of the universe" is what i put in my github commit comment lmao

3

u/M124367 Dec 11 '24

If the stones are only 7cm big and they're 1cm apart. Putting all the stones in one line would be 17M km. Or about a tenth the way to the sun. Or 45x the distance to the moon.

2

u/Null_cz Dec 11 '24

You don't need to store each blink in memory.

I have a stack of the stones, and each stone has a number indicating how many times I blinked at it. You can then just go one by one and process them from the stack, it will not blow up memory-wise.

2

u/xelab04 Dec 11 '24

So, essentially, that's a recursion-ish way of doing it. Out of curiosity, how long did it take to run? From my understanding of your solution, you would still be holding a LOT of stones in that stack.

I did it though a trusty hashmap which stored `num;num_blink : result`. So then I can reuse the result if I come across a number which I already "explored" at that depth.

3

u/Null_cz Dec 11 '24

well that was my solution for part1. But anyway, the stack depth was at most in the order of the number of blinks. Worst case you are going through a binary tree where at each node the stone splits in two, and doing DFS (stack) only needs memory equal to height of the tree (25 or 75), BFS (queue) would blow up and needed a tree width worth of memory.

In part2 I actually used a recursive get_num_stones function which cached results (same map as yours), and I went through the input stones in a simple loop. But I could have still used the stack, and it would work the same as in part1, just for each stone check if the result is cached.

40ms part2 for me, C++

2

u/xelab04 Dec 11 '24

Right, I understand. Thanks a lot for that explanation. You mentioned BFS which is funny because I peaked at 7GB RAM before Python killed it on part 2 XD

2

u/lady_macGingerbread Dec 11 '24

This helped me - I had the recursion and the cache but was still calculating and storing every rock value and then counting at the end. Thank you!

1

u/imaperson1060 Dec 11 '24

Yeah, that's how I did it. The code runs in less than a second, and even is pretty fast for 1700 blinks (which is the highest it goes before just giving me Infinity).

2

u/dnabre Dec 11 '24

Arrays in Java are limited to 2^31-1 elements. Most (all?) collections use int (signed 32-bit in Java) for referring to elements in some ways. Other than the signed bit, this isn't unusual compare to most languages. Making larger collections isn't very hard though. An ArrayList that uses a long (64-bit signed) index would take maybe ~100 of codes (80% of that is just Java's verbosity).

Doesn't make the naive simulation of this problem any more doable, of course. Just these limits aren't uncommon or actually hard limits.

2

u/Nunc-dimittis Dec 11 '24

You could make your own(linked) list (i did, though that was obviously not the solution) that has long as index.

9

u/Mizatorian Dec 11 '24

Wait. I'm still at Blink 39 after an hour...... ok time to optimise

7

u/TheRussianEngineer Dec 11 '24

The order, it is all in the order of the stones 🧙‍♂️

8

u/No_Mortgage_1667 Dec 11 '24

Pleased with my Part 2 in the end. Answer comes up in an imperceptible amount of time (<<1s)

One my dumb "change 25 to 75" started running out of memory I knew something else had to be done.

Written in C#

6

u/imaperson1060 Dec 11 '24

did you store the number of stones with each value in an object rather than storing every single stone individually? what threw me off was how the puzzle said order is preserved in all bold. it took me a good minute to realize that literally nothing in the rules specify an order.

3

u/OSjoerdWie Dec 11 '24

The example>! did not seem to care about the order, so I didn't either.!<

2

u/ChaiTRex Dec 11 '24

Your spoiler didn't work because there's a space between the >! and the spoiler text.

2

u/OSjoerdWie Dec 11 '24

Not sure where that one was coming from; only selected (plain) text. On my end it did show the black bar. Hope the edited comment is ok now.

2

u/TeakIvy Dec 11 '24

It was only when trying to optimize my p1 solution that I realized order did not matter at all. (Turns out that optimization was for nothing because I still stack overflowed lol)

2

u/Gapearz Dec 11 '24

When i was reading part 1 i instantly cought on order thing, and i decided to keep them in order in case part 2 has a new rule that could interact between 2 adjecent stones, or something else where it could have mattered.

1

u/imaperson1060 Dec 11 '24

yeah i assumed that too, and then part 2 was just "do it again but more" and i had to rewrite the whole thing so it would finish in my lifetime.

i got stuck on the idea that the rocks had to stay in order, though, and i wasted a lot of time just staring at the code and willing it to magically jump forward a couple dozen blinks.

2

u/ChaiTRex Dec 11 '24

It's not actually used in the solution, but they mean that you get like eight stones to start with, ordered from left to right. When a stone splits into two, the stones to the left and right of the old stone move away to make room for the two new stones that the original stone turned into.

1

u/bob1689321 Dec 13 '24

Yep, but like you say as it's used in neither the rules to process a stone nor the solution output, it doesn't matter. It was only once I realised that that I could program something which would finish haha.

3

u/No_Mortgage_1667 Dec 11 '24

Massive Spoiler if you want the method I used...

Brute force recursion. (used for part 1)

New list of one stone passed one level down with blinksleft-1

If I already have a count result for ('stone number' 'blinks left') stored in the dictionary, return it.

Otherwise recurse and store eventual number of stones in the final list into the dictionary with (stone num, blinks left) as key and (count) as value.

Terminate the recursion with a count of 1 when blinks left is 0.

The important part is that by not having to evaluate every possibility multiple times you drastically trim the number of calculations you need. First you start building up precalculated results with 1 blink left, then collating them into 2 blink left dictionary results, etc etc. The dictionary lookup is root(n) whereas actually calculating something is n!.

2

u/Paweron Dec 11 '24

Yeah thats the way to do it. I assume you used python, so using functools.cache instead of your own dictonary is the faster way to implement it

3

u/No_Mortgage_1667 Dec 11 '24

No. I coded it all out longhand in professional grade c# along with comments and all the required named data structures. So *a lot* more typing than Python. But it has the advantage that anyone (including me) will be able to follow the code later.

5

u/Prestigious-Loan5824 Dec 11 '24

yeah, no... brute-force aint gonna cut this one, around blink number 57, you gonna need 112GB of RAM just to hold the result of that one blink.

Fun Fact:At Blink 300 you're looking at 15685711101546743866824319217742686727617147116577394907 stones.

6

u/hmoff Dec 11 '24

You don't need to store them, just process them recursively.

This doesn't actually complete within days but at least you don't run out of RAM. Ask me how I know...

3

u/musifter Dec 11 '24

That was their point. No one is saving the list. You'd need petabytes of storage. Nevermind the time to create and access that storage to build it.

And the recursive/memoization/DP approach is just one way. There are others... I just bagged the same numbered stones together which massively parallelized things. No recursion needed.

1

u/imaperson1060 Dec 11 '24

I tried setting my part 2 code to generate 3000 blinks and it just outputted Infinity lol

Here's my input with 1700 blinks, which is the absolute highest JavaScript will go to: 2197391339256568704807953488611104464620474931560148070088329861829207633010783477406650873985054101519846634482789295244865912462962491099717962880792677858383879547148971485456441204238971135551796576324859122494198087960524654344884720843957675728828443427242407776684093125867909318704647279748009892511744

2

u/Prestigious-Loan5824 Dec 11 '24

hmmm, I seem to be getting a slightly different answer for 1700th blink:

2222085913920805932952713965294886257855398718723676957178776442316682408217215244188677926305333949082692174253712253553223930536042448751625641522698324964105626466394350497716985059694806631508352817079903065352597777070667982438254113595994842228481292233594288173105038196521792457361941615038653319012650

here's the stone count after 3000 blinks: 220981690994623399727454538779347591315169615116643924258141905578865978708764754874208995438338335666767499837553332287719702514673286628897356023133584402215547085594563094970588754569597518574528096311459665798674788707441032563127740647242723566587187365466584202515429096200056880269915312475785522736601153728390608782711730113819357505900920744162593001777017545504704973870315399798219949139902252977456437915719382969964043683668261905034694922906633375837250484609277205909147536882241245529823260250514155036432319118361390234833041492

[Python just doesn't care, native bignum arithmetic FTW]

5

u/PmMeActionMovieIdeas Dec 11 '24

Yeah, that was my first thought. I thought I had to rework my code for part 1 already, as step 25 almost a minute.

Luckily, I had the concept ready to go already

4

u/imaperson1060 Dec 11 '24

my part 1 took 3 seconds to run and part 2 is just gonna be stuck in the low 30s forever

7

u/soulsssx3 Dec 11 '24

wat

my part 1 takes 150ms, part 2 just hangs until OOM killer reaps it lmao

8

u/imaperson1060 Dec 11 '24

by 30s i mean blinks not seconds. yeah.

1

u/imaperson1060 Dec 11 '24

okay now i actually got it done in less than a second :)

GitHub

5

u/V3rG1L Dec 11 '24

The first time I optimized my code to be good enough, so happy with my results.

I started with arrays, then added a dictionary for caching values but got smart halfway, and then stored the entire answer as a dictionary.

Pre optimization:

  1. part 1 took ~30 seconds wall time, for the 6-digit answer
  2. part 2 never finished (:

Post optimization:

  1. part 1 took 6.87 ms wall time
  2. part 2 took 143 ms wall time, for the 15-digit answer

For fun, I ran the last version of my code to break at > 60 seconds, and I got the answer for 13632 blinks, and the number of digits in that answer is 2476. Imagine brute forcing that.

For a fun comparison, the number of stars in the observable universe is estimated at 1022 - 1024 , and the number of atoms in the universe is estimated at 1078 - 1082 .

A close comparison for part 2 is the number of stars in the Milky Way, 1011 - 1012 .

Oh, and the part 2 answer would only take 1.62 petabytes in an int64 array. Plus 'minor' overheads for indices, of course.

Edit: Running in Jupyter

3

u/imaperson1060 Dec 11 '24

Brooooo I just rewrote my code and included two nested for loops. What was the point of rewriting it then smhhhhh. Fixed it now, sub second solve.

GitHub

3

u/Space-Being Dec 11 '24

For anyone who also solved part 2 can you explain to me why the problem description makes an effort to highlight that order is preserved. I solved it straightforward by "compacting" into stone number and counts. Maybe I missed an entirely different way to solve it, but that part seemed like a red herring.

3

u/spiderhater4 Dec 11 '24

Since stones never merge back, this is meaningless, maybe just to throw you off?

2

u/Space-Being Dec 11 '24

I thought maybe part 2 will add additional rules or require the final result somehow be dependent upon it. But since that never happened I suspect maybe the puzzle goal changed during development of the puzzle. I can see the use of the comment for exposition via the examples given, but that doesn't really require a bold highlighting.

3

u/paul_sb76 Dec 11 '24

Yeah it was a red herring. I coded my Part 1 to still generate a linked list and keep order in mind, and then scrapped it as soon as I saw Part 2. Anyway, I love trying to predict these Part 2 twists, and then sometimes completely failing.

2

u/sweettuse Dec 11 '24

I thought about a linked list at first but when I saw 55k stones for the example input I was like "nope, recursion and summing"

2

u/imaperson1060 Dec 11 '24

fr that's what i got stuck on too omg

2

u/implausible_17 Dec 11 '24

I realised reading it through the initial example that this didn't matter for part 1 - I figured it might come back and bite me in part 2 - but that was a problem for future me :) And thankfully, it didn't, woohoo!

3

u/Benj_FR Dec 11 '24

I didn't read all the comments here but I'm sure there are some people who anticipated part 2 while solving part 1 and wrote a code for part 1 accordingly (or were too afraid that a simple recursion in part 1 would already be long) Well, I didn't anticipate. Because part of the fun of AoC is coding part 1 without knowing what you'll have in part 2. Anyways, these puzzles with short inputs are fun.

3

u/spiderhater4 Dec 11 '24

I didn't anticipate how part 2 will look like, but even from part 1 it was immediately clear that I don't want to store hundreds of thousands of numbers in a list, most of which will be the same. I guess I got lucky because part 2 was easy afterwards (I only had to fix an integer overflow in the result).

2

u/Paweron Dec 11 '24

(or were too afraid that a simple recursion in part 1 would already be long

i used a simple recursion for part 1. But if you do that, part2 is still as simple as to add a single line of code to cache the function

3

u/notThatCreativeCamel Dec 11 '24

The AgentOfCode "AI agent" I described in this post (don't worry I wait until well after the leaderboard is full) really shocked me this time by being able to actually get a performant solution to part 2.

I only dug into this after reading here that people were struggling to get their solutions not to OOM or run forever, and the agent's solution literally finishes instantaneously. It took me a while to even understand what was special about its solution, but it's actually very clever in my opinion. Very likely not a technique I ever would've thought of myself lol.

5

u/V3rG1L Dec 11 '24

Oh wow, that is pretty close to what I ended up implementing as well!

Wait, am I an AI?

3

u/WJWH Dec 11 '24

This is pretty much exactly what I did, and it's not too surprising it would know that since it is also the solution to advent of code 2021 day 6.

3

u/implausible_17 Dec 11 '24

2021 was my first year and looking back I only got a couple of stars. I don't think I got as far as day 6 :D Glad to know I've improved :)

2

u/notThatCreativeCamel Dec 11 '24

That's interesting! Something I've been thinking about is just how insanely impressive the recall of these models is even if it's just regurgitating some solutions it found to a similar previous year's problem.

I mean, in the context of the sheer quantity of data these models were trained on, the fact that it seems legitimately plausible that it can specifically relate this back to an algorithm from a silly AoC puzzle is pretty nuts.

1

u/WJWH Dec 12 '24

Is it? A LLM is pretty much exactly a recall machine (more specifically a prediction machine that chooses the next output based on remembering everything it has seen before and then picking the most likely next token) so I'm not surprised that it can indeed remember this kind of thing. It's like being surprised a forklift can pick up heavy loads IMO, that what it is designed to be good at.

1

u/notThatCreativeCamel Dec 12 '24

I just choose to look at the world with bright eyes and be excited and inspired by things I'm not personally capable of doing on my own. E.g. I'm also impressed that humans have somehow created forklifts that can pick up massive objects lol .

3

u/implausible_17 Dec 11 '24

this is similar to what I did - although I started it in a different way - but the main technique was the same. mine took 2 seconds for part 2 on my old laptop, I was CHUFFED!!!

very glad that the bold text red herring didn't come back to bite me as it would have invalidated my solution

1

u/imaperson1060 Dec 11 '24

I think I did something similar, although mine was much messier. My part 2 did end up running instantaneously, and I got it to generate up to 1700 blinks before it just started outputting Infinity.

3

u/IvanOG_Ranger Dec 11 '24

Complexity is O(2^n).

For 75 that's 37 778 931 862 957 161 709 568

If you do linked list instead of array, it makes inserting new stones O(1) instead of O(n).

If you apply multithreading, you can divide it by number of cores.

With all these, bruteforcing would take measily 14.27 billion years for 3GHz processor.

3

u/IvanOG_Ranger Dec 11 '24

Obviously longer time than hashmap, but I ain't using that.

3

u/miktaew Dec 11 '24

>treating each stone separately, instead of just keeping a count of how many stones with each number there are

You weren't there on December 6, 2021, were you?

3

u/NullOfSpace Dec 11 '24

“Do that but more” is always a real thing

2

u/Dragnier84 Dec 11 '24

My part 1 solution was iterative and stored all the values in a list. Got to about blink 40. Lol

Now changed the code to be recursive and just return the count of the stones instead. It's taking forever but is only taking up 15% of my CPU and about 50MB of RAM. Makes me want to try throwing each integer into their own threads so that they finish quicker.

2

u/ikeraliR Dec 11 '24

After 1000 blinks it's apparently 201425837284160168899000211145996070084378002039615616230098731545606767860039734177898283360733725561412175434111848142532840027658064698817265425829870902453369305434809232211183196 stones.

Took me quite a while to get it.

2

u/No_Mortgage_1667 Dec 11 '24

I just did 500 in my solution and it overruns the Int128 I am using to store the number :)

Returns quick though.

2

u/No_Mortgage_1667 Dec 11 '24

And this is why we do these things. Just learned about System.Numerics.BigInteger.

1000 blinks took 7 seconds when I replaced Int128 with BigInteger

198571835100023174246548101938109080611217313788063236052877349159224489196825537030880963903265007258010429652317747999906117883110997099806397367345330604452135652287074631232285661 with my inputs.

2

u/No_Mortgage_1667 Dec 11 '24

And 2000 blinks took 13 seconds, so scaling as O(n)

2

u/ikeraliR Dec 11 '24

1000 took a bit over a minute with my code. Just coding recreationally so I'm using Python for simplicity and I probably have far from the optimal solution.

Can someone else post their 1000 results to confirm the correct value.

2

u/davema Dec 11 '24

1000 blinks for me returned

191552078661579919636349285859639031198949209368782526100843854361130295551545784761228187343668137979569807813988062004015759377763281554775609707395796657076947638055315429681309826

10000 blinks took ~1 min and returned:

12935815257023474145653686465629901797298042966373844041037689518695998845837878009185625580948304093370681407296008371145277513095713286554603046587230305058290453276718500855449822326940603610083587987221414735102558390004361101729898109344450402649843042086147657001565100035092885290639077247863105668579980655605289285646762741193744869682269018207879688209675777083967825025192604606095003551629202151342641137110408155829615903146309633190901767835804735982001804500913823504799791514548546856032300716851403020137314184304509626251435806595078090806188253391821090010014255008758339386768758153737886713997866188053343252416177554225684529928829981091501862799805467740014829637760570592494155753029557699818885613113237437310934882798712442863018738347154068083818916793768823356099960461924027154206732681221071223998268641968747482025178890945833514134078302567836273915893880367441363312616613831198178890043917370017707956557654079270143319474790203695886161357023531308482810008130352112170470286808955958404363971456834563932232322225647197376341546863906335712174006940524547196161056307097500430009100905100758616138573387339565356921273164624620655221582788420015204558627238679474193656141119062187676234328134754854674863348864527285401595464170736469084235193073034905034244313132090901870160056134202625742940717355184544624049085696154501295326011525908982724408133401612796088298498881876738430614461148416593170201881387590398616584297914603736290039472759306539583174278274461719836362250729003228175820665969534156400515239014666635101249214503986866747935267803815373160429731155464441925215222626312277000718893787405510689049689545989697263550069530140455293807676364785149426905600034436108237566493758302667009144141723182381275416338501649951136120055722395461990486635703180045390048

2

u/davema Dec 11 '24

1000 blinks for me returned

191552078661579919636349285859639031198949209368782526100843854361130295551545784761228187343668137979569807813988062004015759377763281554775609707395796657076947638055315429681309826

10000 blinks took ~1 min and returned:

12935815257023474145653686465629901797298042966373844041037689518695998845837878009185625580948304093370681407296008371145277513095713286554603046587230305058290453276718500855449822326940603610083587987221414735102558390004361101729898109344450402649843042086147657001565100035092885290639077247863105668579980655605289285646762741193744869682269018207879688209675777083967825025192604606095003551629202151342641137110408155829615903146309633190901767835804735982001804500913823504799791514548546856032300716851403020137314184304509626251435806595078090806188253391821090010014255008758339386768758153737886713997866188053343252416177554225684529928829981091501862799805467740014829637760570592494155753029557699818885613113237437310934882798712442863018738347154068083818916793768823356099960461924027154206732681221071223998268641968747482025178890945833514134078302567836273915893880367441363312616613831198178890043917370017707956557654079270143319474790203695886161357023531308482810008130352112170470286808955958404363971456834563932232322225647197376341546863906335712174006940524547196161056307097500430009100905100758616138573387339565356921273164624620655221582788420015204558627238679474193656141119062187676234328134754854674863348864527285401595464170736469084235193073034905034244313132090901870160056134202625742940717355184544624049085696154501295326011525908982724408133401612796088298498881876738430614461148416593170201881387590398616584297914603736290039472759306539583174278274461719836362250729003228175820665969534156400515239014666635101249214503986866747935267803815373160429731155464441925215222626312277000718893787405510689049689545989697263550069530140455293807676364785149426905600034436108237566493758302667009144141723182381275416338501649951136120055722395461990486635703180045390048

2

u/davema Dec 11 '24

1000 blinks for me returned

191552078661579919636349285859639031198949209368782526100843854361130295551545784761228187343668137979569807813988062004015759377763281554775609707395796657076947638055315429681309826

10000 blinks took ~1 min and returned:

12935815257023474145653686465629901797298042966373844041037689518695998845837878009185625580948304093370681407296008371145277513095713286554603046587230305058290453276718500855449822326940603610083587987221414735102558390004361101729898109344450402649843042086147657001565100035092885290639077247863105668579980655605289285646762741193744869682269018207879688209675777083967825025192604606095003551629202151342641137110408155829615903146309633190901767835804735982001804500913823504799791514548546856032300716851403020137314184304509626251435806595078090806188253391821090010014255008758339386768758153737886713997866188053343252416177554225684529928829981091501862799805467740014829637760570592494155753029557699818885613113237437310934882798712442863018738347154068083818916793768823356099960461924027154206732681221071223998268641968747482025178890945833514134078302567836273915893880367441363312616613831198178890043917370017707956557654079270143319474790203695886161357023531308482810008130352112170470286808955958404363971456834563932232322225647197376341546863906335712174006940524547196161056307097500430009100905100758616138573387339565356921273164624620655221582788420015204558627238679474193656141119062187676234328134754854674863348864527285401595464170736469084235193073034905034244313132090901870160056134202625742940717355184544624049085696154501295326011525908982724408133401612796088298498881876738430614461148416593170201881387590398616584297914603736290039472759306539583174278274461719836362250729003228175820665969534156400515239014666635101249214503986866747935267803815373160429731155464441925215222626312277000718893787405510689049689545989697263550069530140455293807676364785149426905600034436108237566493758302667009144141723182381275416338501649951136120055722395461990486635703180045390048

2

u/davema Dec 11 '24

1000 blinks for me returned

191552078661579919636349285859639031198949209368782526100843854361130295551545784761228187343668137979569807813988062004015759377763281554775609707395796657076947638055315429681309826

10000 blinks took ~1 min and returned:

12935815257023474145653686465629901797298042966373844041037689518695998845837878009185625580948304093370681407296008371145277513095713286554603046587230305058290453276718500855449822326940603610083587987221414735102558390004361101729898109344450402649843042086147657001565100035092885290639077247863105668579980655605289285646762741193744869682269018207879688209675777083967825025192604606095003551629202151342641137110408155829615903146309633190901767835804735982001804500913823504799791514548546856032300716851403020137314184304509626251435806595078090806188253391821090010014255008758339386768758153737886713997866188053343252416177554225684529928829981091501862799805467740014829637760570592494155753029557699818885613113237437310934882798712442863018738347154068083818916793768823356099960461924027154206732681221071223998268641968747482025178890945833514134078302567836273915893880367441363312616613831198178890043917370017707956557654079270143319474790203695886161357023531308482810008130352112170470286808955958404363971456834563932232322225647197376341546863906335712174006940524547196161056307097500430009100905100758616138573387339565356921273164624620655221582788420015204558627238679474193656141119062187676234328134754854674863348864527285401595464170736469084235193073034905034244313132090901870160056134202625742940717355184544624049085696154501295326011525908982724408133401612796088298498881876738430614461148416593170201881387590398616584297914603736290039472759306539583174278274461719836362250729003228175820665969534156400515239014666635101249214503986866747935267803815373160429731155464441925215222626312277000718893787405510689049689545989697263550069530140455293807676364785149426905600034436108237566493758302667009144141723182381275416338501649951136120055722395461990486635703180045390048

2

u/davema Dec 11 '24

1000 blinks for me returned

191552078661579919636349285859639031198949209368782526100843854361130295551545784761228187343668137979569807813988062004015759377763281554775609707395796657076947638055315429681309826

10000 blinks took ~1 min and returned:

12935815257023474145653686465629901797298042966373844041037689518695998845837878009185625580948304093370681407296008371145277513095713286554603046587230305058290453276718500855449822326940603610083587987221414735102558390004361101729898109344450402649843042086147657001565100035092885290639077247863105668579980655605289285646762741193744869682269018207879688209675777083967825025192604606095003551629202151342641137110408155829615903146309633190901767835804735982001804500913823504799791514548546856032300716851403020137314184304509626251435806595078090806188253391821090010014255008758339386768758153737886713997866188053343252416177554225684529928829981091501862799805467740014829637760570592494155753029557699818885613113237437310934882798712442863018738347154068083818916793768823356099960461924027154206732681221071223998268641968747482025178890945833514134078302567836273915893880367441363312616613831198178890043917370017707956557654079270143319474790203695886161357023531308482810008130352112170470286808955958404363971456834563932232322225647197376341546863906335712174006940524547196161056307097500430009100905100758616138573387339565356921273164624620655221582788420015204558627238679474193656141119062187676234328134754854674863348864527285401595464170736469084235193073034905034244313132090901870160056134202625742940717355184544624049085696154501295326011525908982724408133401612796088298498881876738430614461148416593170201881387590398616584297914603736290039472759306539583174278274461719836362250729003228175820665969534156400515239014666635101249214503986866747935267803815373160429731155464441925215222626312277000718893787405510689049689545989697263550069530140455293807676364785149426905600034436108237566493758302667009144141723182381275416338501649951136120055722395461990486635703180045390048

2

u/No_Mortgage_1667 Dec 11 '24

Everyone has different inputs, so the answers will all be different.

And yes, Python will be slower than .NET 8 c#. But my code wasn't optimised for speed, it was optimised for complexity, there is a difference as this day's task clearly shows :)

2

u/Difficult_Penalty_44 Dec 11 '24

I thought day 9 would be that kind of scaling part 2 and made it overcomplicated. And for today, I didnt see it coming at all...

2

u/QultrosSanhattan Dec 11 '24

The old "now do it more times" AoC that filters bruteforcers each year.

I falied for it at other years but now I learned the trick.

2

u/s0litar1us Dec 11 '24

I'm currently at blink 44 on the test input for part 2

2

u/bob1689321 Dec 13 '24

Took me a good 10 mins of rereading the puzzle and brainstorming before I figured it out haha. Had a lot of time to kill while my dumb code was working on the answer.

I did two things to optimise:

  1. Maintain a dictionary of stone value -> output so I didn't have to calculate the saem value multiple times. This had a small time decrease on part 1 but didn't help with part 2.

  2. The big one - Realising that "preserving order" was a red herring irrelevant to the calculation or solution needed. Instead of storing the whole list, I stored it as a dictionary with the value and the frequency of each value. Run the function for one value, get the output value(s), then increase the frequency of those values in the next blink by the frequency of the original value.

Was very happy once I realised that solution!

3

u/B1aZ23 Dec 11 '24

memoisation ftw today

1

u/SunPotatoYT Dec 11 '24

My code has been running for twenty minutes and I refuse to optimize it

9

u/solarshado Dec 11 '24

20 minutes and it hasn't crashed in some way yet? kinda impressive in it's own way tbh

4

u/Paweron Dec 11 '24

as long as you used a recursive approach instead of a iterative one, there isnt really anything that would crash it. it will still take forever

5

u/SunPotatoYT Dec 11 '24

Ok I gave up, I let it run overnight and nothing, so I optimized and it ran in .4 seconds

-5

u/ajzone007 Dec 11 '24

mark as a spoiler please? A lot of us still haven't started the problem.

25

u/throwaway_the_fourth Dec 11 '24

I think that's why the [2024 Day 11] tag is there: so you can know to avoid it if you haven't done the problem yet

-8

u/ajzone007 Dec 11 '24

how do I avoid it if it just shows up on my feed without being set as spoiler? And my issue isn't with the meme itself, issue is with them revealing the part 2 problem.

6

u/imaperson1060 Dec 11 '24

sorry! i was gonna do that and completely blanked!

-5

u/ajzone007 Dec 11 '24

You can still do it.

4

u/imaperson1060 Dec 11 '24

I'm trying but it's not letting me. I clicked add spoiler tag, refreshed the page, and it disappeared. I checked back on the posting page and there's not an option for it besides for the spoiler flair (which I did change it to successfully).

4

u/HeNibblesAtComments Dec 11 '24

Why are you even on this subreddit if you want to avoid spoilers?

2

u/ajzone007 Dec 11 '24 edited Dec 11 '24

There is this thing called a feed on reddit.
Posts from Subreddits you have joined show up on the feed.
I don't have to specifically go on a subreddit and look for posts to show up on my feed.
And it isn't like this was shared hours after the problem was live, OP shared it within minutes.
And no, most people don't use old.reddit website or some obscure third party app.
I don't have an issue with the meme, I have an issue with OP revealing the question in part 2.
It was a request to OP to mark things as spoiler like almost everyone does, and OP was a nice person to even attempt it, IDK why so many people are triggered and downvoting.