Advent of Code 2023 day 5 NO SOLUTIONS, be carefu...

# advent-of-code

[Davio]

Advent of Code 2023 day 5 NO SOLUTIONS, be careful with spoilers 🧵

[Davio]

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

[Davio]

This is my first hurdle where part 1 runs in under 1 second and part 2 runs out of memory 😄

[phldavies]

Happy to provide a hint or two but not sure what level would be considered a spoiler 😉

[Davio]

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

[Dan Fingal-Surma]

I tried that first as well

[Davio]

Changed the initial thread message to better represent its purpose, I think discussing without giving even minor spoilers is nigh impossible

[Davio]

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

[Riccardo Lippolis]

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 😅

[phldavies]

That's what lunch breaks and/or meetings are for 😉

[Davio]

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

[Johannes Gätjen]

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.

[Johannes Gätjen]

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.

[Riccardo Lippolis]

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 😁

[Jesse McKee]

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 😮

[Neil Banman]

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.

[Dan Fingal-Surma]

After warming with 10k runs, for the final run my solutions take 3.417us and 78.916us

[Dan Fingal-Surma]

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

[Neil Banman]

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!

[Riccardo Lippolis]

tried out my earlier described approach, managed to get part 2 down to about 16 milliseconds (cold start without warmup), good enough 😁

[Dan Fingal-Surma]

Would be about 10x faster going in reverse brute force based on what my answer was

[Edgars]

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.

[Davio]

I got my part 2 answer with the reverse lookup:

Part 2 answer
---------------
47909639
---------------
Took 98213796us

So optimistic that my code still gives me the runtime in microseconds 😄

[Davio]

It's about 1.5mins so not all too bad 😉