Advent of Code 2020 - Day 5

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This one is a breeze with the right idea. The common part is converting the seats into the numerical IDs. At first sight, it looks like a bisection scheme would fit the description perfectly: keep track of the upper and lower bound, and depending on the letter keep the high or low half-interval until it is reduced to a single number. Do that for the row and repeat for the column. It's not even hard to do, but it can be simplified.

Instead we can notice that the scheme it describes corresponds exactly to decimal encoded binary: each position encodes this half-interval concept by adding or not the corresponding power of two. So the first of the seven digits encoding the row leaves the number encoded with the other six bits in its [0, 63] range if it's 0, or moves it into the [64, 127] range, and so on.

Furthermore, multiplying by 8 is equivalent to shifting three positions to the left; then adding the column part just fills in those three positions. If we take the seat as given, and substitute the letters with 0s (for F, L) or 1s (for B, R), we only need to interpret that as a base-2 int to get the ID.

Part 1

Once we have the IDs, finding the maximum is trivial using the max built-in.

Part 2

Now we need to find the gap in the consecutive IDs, but the start and end are not known.

In reality we know the end, that was part 1. We can calculate the minimum in the same way, then go from minimum to maximum until we find the gap. That would require building a set of IDs to check each value in constant time. And it would be the most efficient approach (linear time to build the set, get minimum and maximum, and then traverse the range). The latest code does this with set operations. The resulting set should contain just one element, per the problem statement.

In the first commit for the day, I did it differently, in O(n log(n)),  by sorting the IDs, the traversing the sorted array looking at each value and the next. When the difference is greater than one, that's our gap.