By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2021/12/03/advent-of-code-2021-day-3/

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.

By: Julia on Eric Burden

Re-posted from: https://ericburden.work/blog/2021/12/03/advent-of-code-2021-day-3/

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!