Advent of Code, in Erlang: Day 3

Wasn't I just talking about enjoying Erlang's binary/bit-level pattern matching? Today is full of it!

Advent of Code Day 3 asks us to count bits in binary numbers. These binary numbers are represented as byte-size ASCII "1"s and "0"s per bit, but we won't let that stop us.

count_digits([First|_]=Numbers) ->
    Init = lists:duplicate(size(First), 0),
    count_digits(Numbers, 0, Init).

count_digits([Number|Rest], Total, Counts) ->
    NewCounts = [ A+B ||
                    {A, B} <- lists:zip(Counts,
                                        [ C - $0 || <<C>> <= Number])],
    count_digits(Rest, Total+1, NewCounts);
count_digits([], Total, Init) ->
    {Total, Init}.

Counts is a list of integers, one for each digit in Number. We'll increment an integer every time we see a "1" bit in that position. Most of this should look familiar, if you've been following this blog series. We're recursing over the list of numbers, and accumulating the count in each one. Lots of new syntax here, though.

The <= operator is part of what's called "binary comprehension". It's like list comprehension, if you've seen that in other languages (or in Erlang), but it consumes bytes from the binary on its right, according to the pattern on its left. Here, I'm just taking one byte at a time. The encompasing [ C - $0 || … ] is taking that byte and shifting it from an ASCII "0" or "1" to an integer 0 or 1. Since we're trying to count occurences of 1, directly adding this shifted value to the Counts value in each position (via another list comprehension over a lists:zip to associate each bit with its counter), produces an updated count.

make_gamma(Total, Counts) ->
    Threshold = Total div 2,
    <<Int:(length(Counts))/integer>> =
        << <<(C div Threshold):1>> || C <- Counts >>,
    Int.

Once we have the counts, we need to produce a value that has a 1 bit in each position where there were more 1s than 0s, and a 0 bit in the other positions. In this code, I've done the opposite of count_digits where I used each byte of Number to produce an integer. Here, I'm using each integer of Counts to produce a bit of a new binary. I then use that Erlang bit-level pattern matching I've been so excited about to immediately upgrade that sequence of bits into a new integer, Int. An iterative bit-shift-left is how you might see this done in other languages.

{Total, Counts} = puzzle03:count_digits(Numbers).
Gamma = puzzle03:make_gamma(Total, Counts).
Epsilon = Gamma bxor (trunc(math:pow(2, length(Counts))) - 1).
{22,9} = {Gamma, Epsilon}.

Part 1 asked for a second number, Epsilon that is the bitwise inverse of Gamma. While a bitwise-NOT would have been more succinct, it also would have led to a negative number, as the bits above our highest one got flipped and the 2's compliment interpretation took over. So, we'll just bitwise-XOR exactly as many bits as we have.

Part 2 asks us to derive two more numbers from this mess of digits. This time, the selection process is a winnowing on the basis of the remaining values of each bit.

solveB(Numbers) ->
    {binary_to_integer(solveB(Numbers, {most, 1}, 0), 2),
     binary_to_integer(solveB(Numbers, {least, 0}, 0), 2)}.

solveB([], _, _) ->
    [];
solveB([Answer], _, _) ->
    Answer;
solveB(Numbers, Preference, Offset) ->
    {Zeros, Ones} = lists:partition(
                      fun(<<_:Offset/binary, Bit, _/binary>>) ->
                              Bit == $0
                      end,
                      Numbers),
    Selection = case {length(Zeros) > length(Ones), Preference} of
                    {true, {most, _}} ->
                        Zeros;
                    {true, {least, _}} ->
                        Ones;
                    {false, {_, 1}} ->
                        Ones;
                    {false, {_, 0}} ->
                        Zeros
                end,
    solveB(Selection, Preference, Offset+1).

Since I need all of the bits of two of the numbers at the end of the process, I'm not pulling a byte off the front of a binary, and then recursing on the "rest". I've written my matching pattern to ignore the part of the binary I've already looked at (Offset), and grab the byte (Bit) out of the middle that is relevant to this iteration.

I'm not overly wild about this implementation. It feels like there is a simplification that could be made in the case statement making the Selection. But, this is also the nice thing about matching tuples and atoms: I can write the code in a way that matches the description. "To find oxygen generator rating … most common value … equally common, keep … 1" becomes {most, 1}, and "To find CO2 scrubber rating … least common value … equally common … 0" becomes {least, 0}, and out falls the code.

{Oxygen,CO2} = puzzle03:solveB(Numbers).
230 = Oxygen*CO2.

Did you find a cleaner way to express the winnowing in Part 2? Let me know on Twitter (@hobbyist) or on Github (beerriot). And check back later for my write up of Day 14!

Categories: Development AdventOfCode