Advent of Code 2021 - Day 3

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.

Today we wrangle binary numbers. We will read each as a list of 0's and 1's, and keep a list of them, so we can look at it as a matrix, with one number per row.

To convert back to decimal, we will use the classical approach of iteratively adding a bit and multiplying by 2, going from the most significant bit towards the least significant one, avoiding the use of exponentiation.

Part 1

The first part consists on calculating two simple indicators: one where each digit is the most common in that position across all numbers (i.e. the most common in the corresponding column of the matrix), and the other with the least common. Which means the complement of the first.

Once we have the first, we get the second one by transforming each digit x into 1 - x. If we were using binary numbers as such, the obvious would be to just XOR the first with a number all ones, but it's not worth doing the transformations.

To find out which digit is more common, we can just add the digits along the column. If we get more than half the length, ones are more common, otherwise zeros. We can use the length divided by two checking for a strictly greater sum or the length plus one divided by two accepting also equality; in both cases using integer division. This ensures that it works properly for both odd and even lengths.

For odd lengths, we need to divide by two and round up, and there is no possibility of a tie. For even lengths, there is the possibility of a tie; it is ignored for now, but it will be relevant in the second part. In this case the length divided by two marks the exact threshold (the tie, which can be assigned any way for the moment).

Part 2

In the second part we need to calculate two other indicators, a little more complex in this case. For both indicators, it's a matter of filtering out rows in stages until only one is left. Starting with the leftmost bit, and moving rightwards, we keep the rows that have the most (least for the second indicator) common bit in that position among the remaining rows at each step.

The reasoning about the threshold for the sum is as above, taking care of the possibility of ties. By using the (length + 1) // 2 threshold and accepting equality manages exactly that: in the case of even length, this still returns the exact half, which includes the tie, and in the case of odd length it returns the half rounded up as expected.

As for the implementation, the main potentially sticking points are making sure to work on a copy of the matrix to avoid modifying it before passing it on to the calculation of the second indicator and iterating over the rows (to be selected) and the current column (to use as filter).