Day 5: If You Give A Seed A Fertilizer | Advent of Code 2023

[@TheTrienco]

Kept coming back to this one. From brute force (2.5min), to multithreaded (45s), to parallel reverse lookup (75ms) and finally splitting the ranges from back to front (450us). Amazing how much difference an approach can make

[@briandawley7808]

For reverse lookup do you mean start with locations? I couldn't figure out how to handle when something "upstream" doesn't have a mapped downstream value so instead just uses itself in that case.

[@TheTrienco]

@@briandawley7808 yes. But you have to pretty much start at 0 and count up, because the default mapping says "if no mapping, value maps to itself". So you can't just look at the location ranges, since all values are potentially possible.

[@briandawley7808]

@TheTrienco yeah I tried going from zero but the "use self if unmapped" rule tripped me up.

[@bobruddy]

i brutes forced part 2. had a recursive function to find loc for each seed. then grouped all seeds into 10MM chunks and computed them across 64 cores on two machines in about five minutes with python. thx for the explanation. will try this approach.

[@womogenes]

no way 😅 that’s a really creative solution taking advantage of your hardware. love to see it 👏

[@DennisPing]

Thank you for the explanation. I could not understand this question for the life of me... felt more like reading ancient hebrew than doing computer science.

[@ccj2]

You explained it very well and I still don’t understand what’s going on lol. I’ll sub

[@sebastianbraun2473]

My Java (naive) approach took 900ms. I just reduced the input ranges to „net-ranges“ by reducing overlaps and then spawning a shit-load of threads to work through chunks of 100k input seeds 🎉

[@TheFrogfather1]

My excessively over engineered solution in Freepascal took 1ms for part 2 but has taken most of the evening! I'm sure day 5 wasn't this tough last year!

[@ittydev]

@@TheFrogfather1 Agreed... I feel like I noticed a huge ramp-up over previous years. That said, Day 6 (just completed) was a complete joke compared to 5... (thank goodness?)

[@ChS9712]

I actually let the brute force run while I was thinking about possible better solutions. Pretty sure I got lucky since my input only had ~2.4B possible seeds and using C++ the raw brute force took just under 2 mins. Definitely less time that it would have taken me to wrap my brain around the range based answers.

[@atdit]

Yeah, I think the inputs were generated to be still feasible for bruteforcing in a fast language, but soon we'll probably only be given inputs that won't be feasible to bruteforce anymore without at least some optimizations, or maybe not even at all

[@_sorashi]

The naïve solution in Rust for part 2 took 72 seconds to finish. Faster than writing the cleverer code. Thanks for showing it, though 🙂

[@TheFrogfather1]

I fell into the annual trap of forgetting about integer overflow. It doesn't usually happen this early in the puzzles. Int64 to the rescue!

[@_sorashi]

​@@TheFrogfather1 I used usize, thankfully on a 64-bit machine 😀

[@fsouza]

I used Python and running with pypy it took 130 seconds. Good enough for me heh

[@briandawley7808]

I think I basically had the same approach, but I thought about it a bit differently. Ultimately I think it's effectively the same as the "interval mapping" approach you explained. But here's how I thought about it (finally, after several hours wasted, lol). Suppose there were just one mapping function from seeds to locations. You're given several sets of seeds, where each set has a starting seed and a range, just like in Part 2. Since we're interested in the lowest location value, look into what location the first seed is mapped to. Call your starting seed X. f(X) maps your seed to some location L. L is in some location set, between the start of the set and the end of that set. Since we're interested in the lowest location, figure out how many entries are between L and the top range of the set. Call that "skippable." We can skip checking seeds from X+skippable, because each value between X+1 and X+skippable will be mapped to a location > L. But, we don't have just a single mapping function, we have a bunch. So for each mapping function, we figure out the distance from the mapped value in the set to the top value of that set. Call that "local_skippable." For the seed we just checked, we can say max_skippable = max_seed_in_set - current_seed. Then for each mapping, we can say local_skippable = max_in_range - mapped_value. Then we say max_skippable = min(max_skippable, local_skippable). At the end if this process, we get max_skippable, so we don't check current_seed+1, we check current_seed+max_skippable. Again I think this is effectively the same as the mapped ranges, but it made more sense to me to think of it as "how many seeds can I skip because they will just be mapped to larger location values, so who cares about those values?" Thanks for the video, nice explanation!

[@chindianajones3742]

Thank you very very much. I stopped reading your comment after the first few sentences because it helped me realize a better way to approach part 2. Hopefully i can figure out a betterway to find the minimum location number without brute forcing it.

[@briandawley7808]

@chindianajones3742 hey good luck! Hope you can get one.

[@VidarVV]

This is exactly how I solved it as well after spending a lot of time trying to work my way backwards first. Nice to exploit that any mapping is always increasing as long as you are in the same "range set" and you just keep track of how long to skip along for the next seed to process.

[@Alex-km3fz]

Not gonna lie I bruteforce part2 😂. Thanks for the explaination