Day 5, part 2

Introduction

Hello and welcome to part 2 of the day 5 Advent of Code puzzle. This is a continuation of the task and code written in Day 5, part 1, so please get familiar with that before you do the part 2. This part of the challenge is available only when you successfully finished the part 1. The second part of the challenge is described under section here.

What is the new problem

Now we have the new rule for the seed numbers we had before. Previously we were treating each number as a separate seed and we did the calculations for those seeds. Now the seed numbers are actually a ranges. Each pair of seed number represents the starting seed number and the length of the range respectively. If we take a look at the test data again:

we can see that our seeds are two seed ranges:

• first range starts at and spans for next numbers until number
• second range starts at and spans for next numbers, so until the number . Now we have to perform the mappings on every seed in those ranges and finally find the lowest location once again. For our test data the new lowest location is .

Solution

Technically we could create new array of seeds based on the ranges and this will work just fine with the test data as the numbers in there are small, so the arrays would be small as well. This solution will not work with the real input data tho, because the arrays will fill the whole memory rather quickly. We need a better approach this time:

1. We divide the seeds from the input into ranges
2. In each range we loop through the seeds (without storing the seed anywhere), calculate outputs for the seed and store the location if it is lower then the previously saved one. This in turn give us array of the lowest location in each range.
3. We simply find the lowest number in the array of all those lowest-in-range locations.

This is the final code. As you can see it basically loops through the seeds, doing the calculations for each seed separately, without storing all those seeds anywhere. For this piece of code to work we modified the function, dividing it in smaller parts.

We can now run this code on the test data and see the results.

This is it, we once again succeeded! Nice work! Lets commit the progress.

Final result

This is the time to do the final check on the real input data.

[!warning] This script will take a lot of time to finish as the amount of seeds to test is enormous. In my case it took more than 2 hours to test all the seeds.

Of course testing each seed separately is not the most efficient way. A good alternative would be dividing the seed ranges based on the maps ranges. So each seed range would be broken into ranges that are intersecting with the map and those which doeskin. This way we can only check the lowest value for each sub-range instead of checking every single seed value. I am really sorry that I do not provide this solution in here, but I simply have not enough free time to do so. You can read about the before mentioned concept of dividing the ranges on this Reddit page. But let's go back to our dumb solution. After patiently waiting for the result we can finally see in the console the new lowest location.

We can now submit this answer on the page to check if our results are good. And the time spend on calculations paid off! We made it once more! The final step is to save our progress.

This one was tough but it only makes us stronger. We will continue our adventure in Day 6, part 1