Warning: this post contains spoilers for Advent of Code 2021 Day 3, problem and solutions. Hence, I’m putting everything below the “Read More” tag – continue reading at your own risks.

In Day 3 of AoC, we’re hitting a category of problems that I’m begrudgingly coming to like: problems that have something to do with binary strings. Turns out, considering the amount of problems we’ve had in that area in the previous years, you can have a lot of fun with them 🙂 I used to suck at them far more than I do now, though, so practice helps in that regard.

We’re given a series of binary strings – about which I’ll talk in terms of numbers and (binary) digits. In the first part, we are asked to return the number that corresponds to the majority digit in these numbers: with numbers 001, 010 and 110, the result would be 010 because the first digit sof these three numbers are (0, 0, 1), and there’s more zeroes than ones, the second digits are (0, 1, 1), and there’s more ones than zeroes, and the last digits are (1, 0, 0) and there’s more zeroes than ones.

That’s a fairly straightforward implementation: count the number of ones and zeroes for each digit, compare these counts, emit the digits one by one. I’ve seen a cuter (in my view) approach to that, which is to sum all the digits, divide by the total count, and emit 0 if that division is less than 0.5 and 1 otherwise.

Now the problem doesn’t end there, even in the first part: it also demands the number corresponding to the minority digit with the same input of strings. There’s an observation there, which is that these two numbers are XOR of each other: a digit is either the majority, or the minority. Hence, there’s no need to go through two functions: do one, you have the other. Since there’s no mention of tie, the assumption is that it’s not an issue in the provided inputs: otherwise, there would be multiple solutions.

As a short side note, I briefly wondered if there was a better/more elegant way to do this – it wouldn’t have changed much because complexity-wise, I’d still need to read at least half of the digits before being able to reach a conclusion, but… just wondering. And I got a flashback from my studies (including where I was sitting in the room), remembering “I have no idea what the result is, but I know there’s a result in circuit complexity about majority functions, I’m pretty sure it says it’s non-trivial, it’s probably completely irrelevant, buuuuut…”. And indeed there is – “the majority function cannot be computed by AC0 circuits of subexponential size“. Which I used as a heuristic to the direction of “nah, there’s no pretty way of doing this”. I have literally no idea whether that heuristic is valid or not, because I’ve never been super competent at complexity theory, and it’s been a long while, but that’s my heuristic and I stand by it 😉 (If you have opinions, I’d be happy to hear about them!).

The second part of the puzzle built on the first part. Given the same binary strings, the goal was to sift repeatedly through them bit by bit until there’s only one string left, and to do that for two criteria, hence obtaining two different strings. The first sifting for a given digit is “if it’s the majority digit for that digit, keep it; if not, drop it. In case of ties, assume that the majority digit is 1.” The second sifting for a given digit was the same, except that the minority digit is kept, and in case of ties, assuming that the minority digit is 0.

This is where the observation about “a digit is either equal to the minority or to the majority” is very useful, especially since it also works with the extended version of minority/majority taking into account ties (and which so happened to be the way I implemented it in the first part – but that was lucky 🙂 ). However, here, the results are not XOR from one another: we’re filtering through a list, and already at the first step, the lists partition the whole space, and what happens in there is independent at the second digit. Hence, no magic there (… that I can see): we’ll need to sift twice through the list to get both numbers.

Implementation-wise, I went with the array_filter function of PHP, which allows to filter an array depending on a criteria. I looked into closures and parent scopes and the like, and I learnt a bunch of things:

• assigning an array to a new variable in PHP does copy the array (which is what I wanted, so, great)
• the use of array_filter in PHP
• how closures and fetching stuff from the parent scope work, which I had some idea about, but which is now clearer in my head
• when filtering through an array, PHP keeps the indices of the array! Hence, if what you end up getting was the third element of the list, it’ll be indexed at $foo[2] and not $foo[0] (with $foo[0] being undefined). This was puzzling, but I’m happy I encountered that one – it does make sense, but it’s not exactly intuitive, coming from another language.

In my view, a good third day problem – I found it relatively easy, but I still learnt and remembered many things, and I thought this was very satisfying 🙂 And, if you’re interested, my code is here: Day 3 solution.