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!

By: Julia on Eric Burden

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

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/02/advent-of-code-2021-day-2/

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 2 – Dive!

Find the problem description HERE.

Prelude – Reading Directions

Time to follow directions! I promised yesterday to share my input parsing
strategy whenever it was interesting. Well, today it was interesting! Because
our directions are one of three distinct types (forward, down, up), it just
made sense to parse them into three distinct Types. That’s what the
code below does:

abstract type AbstractDirection end

struct Forward <: AbstractDirection mag::Integer end
struct Down    <: AbstractDirection mag::Integer end
struct Up      <: AbstractDirection mag::Integer end

function todirection(s::AbstractString)::AbstractDirection
    (dirstr, magstr) = split(s)
    mag = parse(Int, magstr)
    dirstr == "forward" && return Forward(mag)
    dirstr == "down"    && return Down(mag)
    dirstr == "up"      && return Up(mag)
    DomainError(s, "cannot be converted to Direction") |> throw
end

inputdir = normpath(joinpath(@__FILE__,"..","..","..","inputs"))
inputpath = joinpath(inputdir, "Day02", "Input01.txt")
input = open(inputpath) do f
    [todirection(s) for s in readlines(f)]
end

This is at least partially an excuse to muck about with Julia’s type system for
my own edification. Here, I’ve created an abstract type AbstractDirection and
had three new composite types (structs) inherit from AbstractDirection, one
for each of the different ‘direction’s. The todirection() function does the
heavy lifting of converting a line in the input to either Forward, Down, or
Up, and then it’s just a matter of reading lines from the input file and
parsing them into ‘direction’ structs. This means that the input for our
puzzle-solving functions will be an array of AbstractDirections, a collection
of Forward, Down, and Up structs.

Part One – Steering the Submersible

On to the puzzle itself. I really hope we’re heading in the right direction,
because apparently this submarine only goes up, down, and forward. With my
input in place, I thought it would be fun to explore the performance
implications of a couple of different approaches to this problem. For the first
stab, I created another struct Position to house the distance and depth of
our submarine and implemented three move!() methods, one for each sub-type of
AbstractDirection. Each method takes the Position and an AbstractDirection
and modifies the Position in place according to whether the second argument
is a Forward, Down, or Up, like so:

# Strategy 1 ----------

# Keeps track of the current position of the submarine
mutable struct Position
    horizontal::Integer
    depth::Integer
end

# Constructor method to allow creating a new `Position` with 
# a single argument for both `horizontal` and `depth`
Position(x) = Position(x, x)

# Each `move!()` implementation modifies the `Position` in accordance with
# the puzzle directions.
function move!(p::Position, d::Forward)
    p.horizontal += d.mag
end

function move!(p::Position, d::Down)
    p.depth += d.mag
end

function move!(p::Position, d::Up)
    p.depth -= d.mag
end


# Loop over the input `AbstractDirection`s and move the `Position`
# for each one.
function part1_strategy1(input)
    position = Position(0, 0)
    foreach(x -> move!(position, x), input)
    position.horizontal * position.depth
end

A bit of light reading in the Julia Docs
indicated that using a mutable struct this way would necessarily mean allocating
the Position on the heap to ensure a stable memory address. This could also
indicate a potential performance penalty, so I decided to try a different
approach using a simpler (hopefully stack-allocated) type to keep track of
my position, and treat it as immutable in a more ‘functional’ style of producing
a new value each iteration and ‘reducing’ the list of AbstractDirections.

# Strategy 2 ----------

# Now we're using a Tuple instead of a mutable struct
const PositionTuple = Tuple{Int64, Int64}

# Still have three different methods, but now they all return
# a `PositionTuple` instead of modifying `p` in place
function move(p::PositionTuple , d::Forward)::PositionTuple
    (p[1] + d.mag, p[2])
end

function move(p::PositionTuple, d::Down)::PositionTuple
    (p[1], p[2] + d.mag)
end

function move(p::PositionTuple, d::Up)::PositionTuple
    (p[1], p[2] - d.mag)
end


# Now each trip through the loop produces a new `PositionTuple`. Use
# `foldl` so that the function will be called as `move(p, d)` instead
# of `move(d, p)`.
function part1_strategy2(input)
    position = foldl(move, input, init = (0, 0))
    position[1] * position[2]
end

This way was a bit faster, but it seemed like further efficiency could be gained
by just modifying the horizontal and depth values directly. We do lose
some clarity and readability (and nifty uses of the type system) in the
process, in my opinion.

# Strategy 3 ----------

function part1_strategy3(input)
    (horizontal, depth) = (0, 0)
    for direction in input
        if typeof(direction) == Forward
            horizontal += direction.mag
        end
        if typeof(direction) == Down
            depth += direction.mag
        end
        if typeof(direction) == Up
            depth -= direction.mag
        end
    end
    horizontal * depth
end

This way, we’re just looping over input and modifying a primitive value that
lives inside the function. We’re using multiple if statements on the type of
the AbstractDirection, which feels a bit clunky, but there’s no switch
statements or pattern-matching in Julia.

Part Two – Read Carefully

Huh, turns out we misread the manual (or more likely just skimmed it and ignored
most of it). Who could have guessed? Probably anyone who’s done previous years’
AoC, but hey, we needed a part two! This second part is a slight variation on
part one, adding an additional component of our current position to keep track
of. We also changed the impact of the different ‘direction’s slightly, but it’s
nothing we can’t handle. The biggest changes are to the move!()/move() logic,
shown below:

# Strategy 1 ----------
mutable struct Position
    horizontal::Integer
    depth::Integer
    aim::Integer
end
Position(x) = Position(x, x, x)

function move!(p::Position, d::Forward)
    p.horizontal += d.mag
    p.depth += (p.aim * d.mag)
end

function move!(p::Position, d::Down)
    p.aim += d.mag
end

function move!(p::Position, d::Up)
    p.aim -= d.mag
end


function part2_strategy1(input)
    position = Position(0)
    foreach(x -> move!(position, x), input)
    position.horizontal * position.depth
end


# Strategy 2 ----------

# (horizontal, depth, aim)
const PositionTriple = Tuple{Int64, Int64, Int64}

function move(p::PositionTriple, d::Forward)::PositionTriple
    (p[1] + d.mag, p[2] + (p[3] * d.mag), p[3])
end

function move(p::PositionTriple, d::Down)::PositionTriple
    (p[1], p[2], p[3] + d.mag)
end

function move(p::PositionTriple, d::Up)::PositionTriple
    (p[1], p[2], p[3] - d.mag)
end


function part2_strategy2(input)
    position = foldl(move, input, init = (0, 0, 0))
    position[1] * position[2]
end


# Strategy 3 ----------

function part2_strategy3(input)
    (horizontal, depth, aim) = (0, 0, 0)
    for direction in input
        if typeof(direction) == Forward
            horizontal += direction.mag
            depth += (aim * direction.mag)
        end
        if typeof(direction) == Down
            aim += direction.mag
        end
        if typeof(direction) == Up
            aim -= direction.mag
        end
    end
    horizontal*depth
end

Wrap-Up

I mentioned being interested in the three different strategies because I thought
there might be performance implications, and boy are there!

Julia Advent of Code 2021 Benchmarks:

Day 02:
├─ Part 01:
│  ├─ Strategy 01:   95.243 μs (2802 allocations: 43.80 KiB)
│  ├─ Strategy 02:   56.639 μs (2235 allocations: 50.55 KiB)
│  └─ Strategy 03:   47.693 μs (601 allocations: 9.39 KiB)
└─ Part 02:
   ├─ Strategy 01:  130.611 μs (4267 allocations: 66.69 KiB)
   ├─ Strategy 02:   78.942 μs (3923 allocations: 76.92 KiB)
   └─ Strategy 03:   63.827 μs (1308 allocations: 20.44 KiB)

I’m a bit torn, to be honest. I vastly prefer either Strategy 1 or 2 for
reasons I can’t quite put my finger on, probably because they feel a bit more
clever and don’t rely on stacked if statements, but those performance gains on
Strategy 3 are not insignificant, and likely to get more serious as the size of
the input increases. I think I’d probably settle on Strategy 2 as my preference,
though, the small performance sacrifice is definitely worth it just to avoid
those serial if statements, in my book. All in all, though, this is part of
the reason I enjoy AoC so much. It gives me an excuse and a direction to really
explore a language and I find I learn a ton by participating.

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