Advent of Code 2023 - Day 5

This is a thread to discuss Day 5

https://adventofcode.com/2023/day/5

REMEMBER!
It is VERY important NOT to write any public spoilers :slight_smile:
ALWAYS keep spoiler stuff hidden inside one of these

Summary

This text will be hidden

which you can obtain by clicking on the gear icon

image

Good luck :slight_smile:
FYI one of the features of Advent of Code is that we all get given different inputs so our answers will be different.
The examples are all the same but each of us gets different inputs for us to solve

Not even started on Day 5 due to too many things going on here at home !

[edit] Just read the puzzle and I haven't got a clue where to even start - might give this whole day a miss!

yeah, I feel like this year has been getting very hard very quickly. I mean, I got pretty far in 2021, because the puzzles didn't escalate in difficulty very quickly.

Part I, updated

Final

Part II ... not really

There are $$2*10^9$$ seeds to be planted.
So the "brute force" approach does not work. For me, only a few thousand seeds were tested in a sec.
Something more sophisticated must be used. Like reverse-mapping to check if a location, starting from 0, maps to the seed. Or slice the maps over overlapped ranges to test only the boudaries.

BTW, I've noticed, lastly, that saving a project often fails without notice. I lost a few nightly updates of my AoC projects.

Yeah, this part 2 is rather difficult. I guess a function is required that takes a range of contiguous input values (e.g. (10 5)) and a conversion table (e.g. ((4 9 2) (14 13 100))) as inputs, and produces a list of output value ranges (e.g. ((5 1) (11 1) (14 2)). I think this can relatively easily be approached recursively.

To complicate things, overlapping ranges may appear in the process, potentially creating an explosion of data - so a kind of range merge work may need to be done between conversion stages.

I just had the same after I'd completed Day 6 Part 2 - locked up when saving my scripts :frowning:

I've got the 2 Gold Stars so not going to redo it

I finally solved part 2. Quite complicated, I spent a lot of time debugging. I wonder if anyone found a simpler solution?

BTW in the process I developed a MERGE function that might be of more general use. In this case I used it to merge integer series such as: (1..8), (2..4), (9..12), (15..16), (19..20), (20..25). For the algorithm to work itโ€™s essential theyโ€™re pre-sorted by their lower bounds. The first series overlaps with the second, and immediately borders the third, therefore the three are merged: (1..12) - we donโ€™t care about doubles. The final two are merged, too; so in all the new list of series is: (1..12), (15..16), (19..25).

More generally, I derived a (recursive) algorithm that may be used to merge items that were pre-sorted in such way that only if X and Successor of X (hence: S(X) ) can be merged, X, and the merging result of X and S(X), may be merged with the Successor of S(X). Or, perhaps more precisely put: if X and S(X) can not be merged, neither can X and any of S(X)โ€™s successors.

Here it is:

Demo

, with: