Advent of Code 2021 - Day 2
Tags: julia, adventofcode, coding
Published: 2021-12-03 02:35:19

---
title: Advent of Code 2021 - Day 2
published: true
date: 2021-12-02 00:00:00 UTC
tags:  julia, adventofcode, coding
canonical_url: https://www.ericburden.work/blog/2021/12/02/advent-of-code-2021-day-2/
series: Advent of Code 2021
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Julia](https://julialang.org). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2021) 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](https://adventofcode.com/2021/day/2).

## 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:

```julia
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 `AbstractDirection`s, 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:

```julia
# 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](https://docs.julialang.org/en/v1/manual/types/#Mutable-Composite-Types) 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 `AbstractDirection`s.

```julia
# 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.

```julia
# 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:

```julia
# 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!