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!