It’s hard to predict, given you can only initially see the first part of the puzzle, what the second part will look like. You prepare as best you can. And, in the first four days of this year’s Advent of Code, part 2 was just like part 1, except more. Usually I could do part 2 with the same code as part 1, with some minor changes.
Not the case for “Cafeteria“. The input is in two parts; the first part is a series of number ranges, and the second is a series of numbers. Part 1 is simple: count the number of that second set that fit within any of the ranges given in the first part.
And that was simple. No trouble at all to come up with the part 1 answer. But there was a clue hidden in that line. The word “any”. “Any” implied more than one, and I knew that part 2 would expand on that. Maybe we want to find fresh fruits that are only in one range? That wouldn’t have been too hard, really.
But actually, part 2 had nothing to do with the freshness of fruit; the whole second part of the input was for part 1 only. Part 2 only dealt with the ranges, thusly: the ranges needed to merge so that there were no overlaps, and then part 2 would be the sum of the values that fell within each range.
A brute force approach would be to take each range and compare it to every other range and if an overlap was found, remove them both, make a new merged range, add it to the list, start over, and continue until no more merges were found.
You can skip a lot of that complexity by sorting ranges by the start and the end, and keeping track of the lower and higher bounds of the ranges you’ve seen thus far. Once sorted, you can go through the ranges and if the low bounds of that range is greater than the highest bound you’ve seen, you don’t have to check anything, it is guaranteed not to overlap any other range. Only when that is not the case do you have to go check the other conditions — new range completely encloses an old range, old range completely encloses a new range, new range extends an old range higher (can’t go lower, as we’re sorted).
This limits the brute forcing to those times when you really need it.
There was just one problem. One small, minor problem. One really trivial afterthought of a problem.
There was no way to sort these ranges. Oh, Lua has a sort, a good one, a fully featured one. But not the Picotron implementation of Lua. It’s a fantasy retro console. Fantasy retro consoles don’t sort (fact: Doom was built on sorting. Sorting and trigonometric lookup tables.)
I didn’t know immediately that there was no sorting in Picotron Lua. I tried it, no dice. I tried a different sort I found talk of. Nope, not that either. I wrote some debugging stuff and found out that the sort function plain did not exist. I was only using it wrong by using it at all.
I went to the Picotron forums and found people had written their own sorts, were willing to share, and provided the code. I pasted it into my program and everything worked.
I’m as shocked as you are. I did some minor optimizations but I was pretty much done at that point and ate breakfast and went to work. Thought about it all day and couldn’t think of anything I needed to change.
Imagine a programming language without sort. It’s easy if you try. No bounds beneath us. Above us, bounds are high. Imagine all the ranges, in one big array…
Leave a Reply