By Eric Burden | December 3, 2021

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 3 - Binary Diagnostic

Find the problem description HERE.

## The Input - Here We Go Again

When I committed to discussing the input parsing (on Day One) only when I found it to be sufficiently different and interesting, I did not assume that I would find input parsing to be sufficiently different and interesting for three days in a row. Man, I don’t know myself at all…

```
process(s::AbstractString)::Vector{Bool} = split(s, "") .== "1"
inputdir = normpath(joinpath(@__FILE__,"..","..","..","inputs"))
inputpath = joinpath(inputdir, "Day03", "input.txt")
input = open(inputpath) do f
# Get a Vector of Boolean vectors, convert to a BitMatrix,
# then transpose it such that the first column contains the
# first bit of every number, the second column contains the
# second bit, etc.
bitvecs = [process(s) for s in readlines(f)]
bitmatrix = reduce(hcat, bitvecs)
transpose(bitmatrix)
end
```

The fun bit here is converting the `Vector{Bool}`

s into a `BitMatrix`

by reducing
using the `hcat()`

function. This was particularly fun for me because (a) it
took me way too long to realize that was the right way to do it, in light of
the fact that (b) this is almost EXACTLY how I do this same thing all the time
in R (just with `purrr::reduce()`

and `cbind`

/`rbind`

). *sigh* It is nice to
know that some of the R idioms transfer over, though, so I’ll be on the lookout
for more of that in future.

## Part One - To Be or Not To Be

Part one of the puzzle asks us to calculate the most common bit value at each
position for all of the binary numbers in the input. This is the reason we
transposed the `BitMatrix`

when parsing our input, so that each column in
the `BitArray`

represents the values from all the inputs for a single position.
Because I happen to know (or at least I think I know) that Julia stores matrix
columns as arrays in memory, I hope that this will lead to faster run times as
I was sure I’d be iterating over these columns. With all the data in, solving
part one is really just a matter of finding the most common value in each
matrix column. And, since there are only two possible values, this turns out
not to be too difficult.

```
# Given a boolean vector, return true if more values are true
# Breaks ties in favor of true
function mostcommon(arr)::Bool
trues = count(arr)
trues >= (length(arr) - trues)
end
# Convert a Boolean vector into a decimal number
function convert(t::Type{Int}, bv::BitVector)
# Generate a vector of the powers of 2 represented in
# the BitVector.
(powers
= (length(bv)-1:-1:0)
|> collect
|> (x -> x[bv]))
# Raise 2 to each of the powers and sum the result
sum(2 .^ powers)
end
function part1(input)
# For each column in the input, identify the most common value and
# collect these most common values into a BitVector
(gamma
= eachcol(input)
|> (x -> map(mostcommon, x))
|> BitVector)
# Since `gamma` is the most common values in each column, `epsilon`
# is the least common values, and there are only two values, `epsilon`
# is just the inverse of `gamma`.
epsilon = .!gamma
convert(Int, gamma) * convert(Int, epsilon)
end
```

I couldn’t find a convenient function in the standard library to convert a
`BitVector`

to an integer, which may be more a failure in my Googling than a
shortcoming of the language. So, I wrote one. I haven’t mentioned `epsilon`

, but
since it’s really just the opposite of `gamma`

, you can get it `epsilon`

from
reversing all the bits in `gamma`

.

## Part Two - Gas Exchange Filter

Part two is a bit of a tricky variation on part one. Now, instead of finding the
most common bit value at each position, it’s a cumulative filter at each
position, keeping only the binary numbers with the most common value in the
first position in the first pass, numbers with the most common value in the
second position in the second pass, and so on until only one binary number
remains. Then, of course, you need to do it again with the *least* common
value at each position.

```
# Given a Matrix as `input` and a `discriminator` function, repeatedly
# evaluate columns of `input` from left to right, keeping only rows where
# `discriminator` is satisfied. Repeat until only one row remains and
# return that row as a BitVector
function find_first_match(input, discriminator)
mask = trues(size(input, 1))
for col in eachcol(input)
common_value = discriminator(col[mask])
# Carry forward only mask indices where the common value
# is found in each column
mask = mask .& (col .== common_value)
# Stop looking if mask contains only one `true`.
sum(mask) == 1 && break
end
# Convert n x 1 BitMatrix to BitVector
(input[mask,:]
|> Iterators.flatten
|> BitVector)
end
# Dispatch to `find_first_match` with different `discriminator`s
find_oxygen_generator_rating(x) = find_first_match(x, mostcommon)
find_co2_scrubber_rating(x) = find_first_match(x, !mostcommon)
function part2(input)
oxygen_generator_rating = find_oxygen_generator_rating(input)
co2_scrubber_rating = find_co2_scrubber_rating(input)
convert(Int, oxygen_generator_rating) * convert(Int, co2_scrubber_rating)
end
```

This is a problem where array-indexing really shines. Instead of *actually*
removing numbers on each pass, we just build up a boolean vector and use it
to index the rows in the `BitMatrix`

containing our binary numbers. We know
we’ve finished building up the `mask`

when there’s only one `true`

value left
in it.

# Wrap Up

Coming from R, I absolutely *love* that some of the idioms I’m used to transfer
over, and array-indexing is one of my favorites. Between native support for
matrices and array-indexing (and a pretty smart JIT compiler), I was able to
find a solution that really cut down on the number of allocations and runs
pretty efficiently.

```
❯ julia bench/Benchmark.jl -d 3
Julia Advent of Code 2021 Benchmarks:
Day 03:
├─ Part 01: 12.758 μs (12 allocations: 1.23 KiB)
└─ Part 02: 65.930 μs (103 allocations: 108.83 KiB)
```

This was a fun day, and I got to use some familiar strategies, along with
learning a lot about type casting in Julia and the differences between
`Vector{Bool}`

, `Matrix{Bool}`

, and `BitArray`

/`BitMatrix`

. A good time,
indeed!

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!