https://kotlinlang.org logo
#advent-of-code
Title
# advent-of-code
d

Davio

12/05/2023, 9:06 AM
Advent of Code 2023 day 5 NO SOLUTIONS, be careful with spoilers 🧵
Might be useful to have a thread like this for people like me who are still stuck on solving it, but don't yet want to look at other people's code
plus1 1
This is my first hurdle where part 1 runs in under 1 second and part 2 runs out of memory 😄
p

phldavies

12/05/2023, 9:13 AM
Happy to provide a hint or two but not sure what level would be considered a spoiler 😉
d

Davio

12/05/2023, 9:14 AM
For now I'm fine just soldiering on on my own, tried to reverse the lookup (instead of going from seed to location, going from location to seed), but didn't yet help much
👍 1
d

Dan Fingal-Surma

12/05/2023, 9:17 AM
I tried that first as well
d

Davio

12/05/2023, 9:20 AM
Changed the initial thread message to better represent its purpose, I think discussing without giving even minor spoilers is nigh impossible
So this thread is for people who struggle, but still want to try and solve it on their own without accidentally looking at full solutions
r

Riccardo Lippolis

12/05/2023, 9:34 AM
I'm in a similar situation, part 1 could be 'brute-forced' easily, but that indeed doesn't work for part 2. Didn't have the time this morning before work to create an alternative solution, but I'm thinking of modifying my solution to work with number ranges instead of single numbers. So something like: seed range
a..b
, mapped with the
seed-to-soil
map becomes soil ranges
[a..c,d..b]
(variable size, depending on the overlaps), etc etc. down the chain of maps. In the end I should have a set of ranges where it should be more straightforward to get the minimum. My fingers are itching to try this out, but can only try this tonight 😅
p

phldavies

12/05/2023, 9:38 AM
That's what lunch breaks and/or meetings are for 😉
💡 1
d

Davio

12/05/2023, 9:44 AM
That might be an idea, to collapse the maps into a super map, or aggregated map that just goes from the seed ranges to the location ranges immediately without any steps in between, now we just need a way to collapse two maps into one
j

Johannes Gätjen

12/05/2023, 11:42 AM
Potentially useful information without spoilering (I hope): My brute-force solution runs in ~6m30s. Others in the solution thread have mentioned runtimes of a bit under 5 minutes. My coworker says he doesn't expect his brute-force solution to run that quickly. If you're running out of memory, try to think about how you can process one element at a time, which will allow to continuously update the minimum value you're looking for.
Speculation: doing a reverse lookup (i.e. going from location to seed) I would expect a roughly 10 times improvement compared to the forward brute-force. So still around 30 seconds.
r

Riccardo Lippolis

12/05/2023, 12:40 PM
my out-of-memory was most likely caused by the fact that I had created some hastily written memoization implementation. Haven't tried running the code without it, but it most likely wouldn't run out of memory then (not sure how long it would take, however 😛 ) EDIT: less than 10 minutes, meh good enough for now 😁
j

Jesse McKee

12/05/2023, 3:02 PM
I got my part 1 down to 1m40, still having a tough go at part 2. Those OOMs hit hard. Taking a small break and getting back at it 😮
n

Neil Banman

12/05/2023, 3:57 PM
I solved my heap space problems with lazy evaluation (Sequences). I also reversed the lookup, took 10 seconds on my five year old machine. I had an aha moment just as I laid my head down to sleep. I think I know how those others get those millisecond times. Gonna try to refactor today. Though it would also be fun to see how much I can improve my brute force by running it in parallel.
d

Dan Fingal-Surma

12/05/2023, 6:05 PM
After warming with 10k runs, for the final run my solutions take 3.417us and 78.916us
For my input a brute force approach would require checking 1,699,478,662 seeds, each seed->location expansion takes ~292 nanos, so at least 8 mins
n

Neil Banman

12/05/2023, 7:50 PM
Well, there's brute force, and then there's brute force. Mine went in reverse so a (0, 1, 2, ...) sequence working backwards through the conversions gives us a starting seed value. Check to see if that's in a seed range and you're done. This drastically speeds things up because you can stop as soon as you find a match, knowing that it is the smallest. Not really a spoiler because nobody should do it this way!
🧠 1
r

Riccardo Lippolis

12/05/2023, 8:48 PM
tried out my earlier described approach, managed to get part 2 down to about 16 milliseconds (cold start without warmup), good enough 😁
d

Dan Fingal-Surma

12/05/2023, 8:56 PM
Would be about 10x faster going in reverse brute force based on what my answer was
e

Edgars

12/05/2023, 9:12 PM
I also did the "reverse brute force" as Neil described. Both doing it the Part 1 way and this gave me the same answer. But somehow it's off by one. Of course, works on test input and part 1 is correct.
d

Davio

12/06/2023, 7:43 AM
I got my part 2 answer with the reverse lookup:
Copy code
Part 2 answer
---------------
47909639
---------------
Took 98213796us
So optimistic that my code still gives me the runtime in microseconds 😄
It's about 1.5mins so not all too bad 😉
21 Views