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!