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!