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.

`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.

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.

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.

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.

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

Post Copyright © 2021 Bryan Fink