# Advent of Code 2021: A Julia Journal - Part 1

Advent of Code is an advent calendar for programming puzzles. I decided to tackle this year’s set of 50 puzzles in Julia and journal my experiences along the way. I’m a beginner in Julia so I thought this would help me improve my skills.

This post covers days 1 through 8. All of my solutions are available on GitHub.

## Day 1: Increasing sequences

Count the number of times a depth measurement increases from the previous measurement

What a great little puzzle to start on. I went very functional and array-focused here, using the `lag`

function from the `ShiftedArrays`

package:

```
function part1()
@chain input begin
parse.(Int32, _) # convert strings to integers
_ .- lag(_) # compute difference with previous value
_[2:end] # remove first element, which will be missing
filter(x -> x > 0, _) # filter to the increases in value
length # now count
end
end
```

I like it but the underscores are hard to read. The `@chain`

macro here is equivalent to piping each line into the next, with the underscore indicating where the result of the previous line should go. Where there is no underscore, such as with `length`

, then the previous result is piped into the first argument.

One annoyance I do have with Julia is that the `map`

and `filter`

functions take the function first and data second, which makes them harder to use with pipes. A consistent principle of the tidyverse in R is that the first argument of a function should, wherever possible, be the “data” argument. I wish that were followed in Julia.

My coding style seems to default to “use arrays, `map`

and `filter`

”. I don’t know if this is a bad thing, as long as my toolset isn’t limited by it.

One option I didn’t know about at the time was the `diff`

difference operator. It could have made my solution a bit simpler:

```
julia> diff([1, 4, 5, 5, 1])
4-element Vector{Int64}:
3
1
0
-4
```

## Day 2: Submarine manoeuvres

Calculate the horizontal position and depth you would have after following the planned course.

Both parts of this puzzle were about calculating the position of a submarine after a long sequence of commands like `up 5`

, `forward 6`

, or `down 7`

. I made a point of using Julia’s structs and multiple dispatch here. The location of the submarine stood out to me as a `mutable struct`

and the manoeuvres could be functions.

The functions I needed to implement here were `up!`

, `forward!`

, `down!`

. The exclamation mark is a Julia convention for functions that modify their inputs. Parts 1 and 2 use different logic, so implemented structs `Location1`

and `Location2`

. This means that I could have a `forward!`

function that behaved differently for `Location1`

and `Location2`

, using Julia’s multiple dispatch.

```
function forward!(loc::Location1, x::Int64)
loc.horizontal += x
end
function forward!(loc::Location2, x::Int64)
loc.horizontal += x
loc.depth += loc.aim * x
end
```

The final step was a bit of hacky code to convert a string like “forward 5” into a function `forward!(location, 5)`

. The `manouevre!`

function, the same for both parts 1 and 2, took care of this:

```
function manoeuvre!(loc::Location, command::String)
command_split = split(command, " ")
manoeuvre_direction = command_split[1]
manoeuvre_function = getfield(@__MODULE__, Symbol(manoeuvre_direction * "!"))
manoeuvre_amount = parse(Int64, command_split[2])
manoeuvre_function(loc, manoeuvre_amount)
end
```

That `getfield`

function takes a string like “forward”, suffixes it with “!”, and then looks for something named “forward!” in the namespace of the module. This made the actual solution straightforward, and similar for both parts:

```
function part2()
l2 = Location2()
for command in input
manoeuvre!(l2, command)
end
aoc_answer(l2)
end
```

## Intermission: A little refactoring

Between days 2 and 3 I decided to clean up the entire project. I refactored everything into a proper Julia package with separate modules like `Day01`

, `Day02`

, and so on. I also implemented the `solve`

function:

```
function solve(day::Int64, part::Int64)
module_string = "Day" * lpad(day, 2, "0")
part_string = string(part)
module_and_part_string = module_string * ".part" * part_string * "()"
eval(Meta.parse(module_and_part_string))
end
```

Here `solve(2, 1)`

will evaluate `Day02.part1()`

. So for each day/module, I need to provide `part1`

and `part2`

functions, and `export`

them.

Refactoring into a package also lets me take advantage of Julia’s *excellent* package manager. It captures the exact versions of any dependencies in my project in case I decide to revisit this code later on.

## Day 3: Most frequent bits

You need to use the binary numbers in the diagnostic report to generate two new binary numbers (called the gamma rate and the epsilon rate)

This was the first puzzle that stumped me. 1000 binary numbers, each 12 bits long, and I had to calculate the most popular bit in each *column*.

For part 2 my array-based approach simply failed. I have a reluctance to use mutable state, which was fine for part 1 because I don’t modify the input. For part 2, where I had to remove rows from the input, it just didn’t work. Once I let myself use a `while`

loop with a mutable state it started to click. The key component was this `while`

loop:

```
while size(gas_matrix)[1] > 1
average_value = mean(gas_matrix[:, column])
target_bit = rounding_function(average_value)
row_indices_to_keep = filter(i -> gas_matrix[i, column] == target_bit, 1:size(gas_matrix)[1])
gas_matrix = gas_matrix[row_indices_to_keep, :]
column += 1
end
```

The `gas_matrix = gas_matrix[row_indices_to_keep, :]`

line removes rows from the input if they have the target bit in the column under investigation. The above code meant that I could use a different rounding function for O2 and CO2 and it would still work:

```
oxygen = gas_rate(
input,
x -> round(Int, x, RoundNearestTiesUp)
)
co2 = gas_rate(
input,
x -> round(Int, (1 - x), RoundNearest) # will round down
)
```

I like how explicit Julia is with rounding here. Straight away I know what `RoundNearestTiesUp`

means.

## Intermission: I’m fighting with Julia’s matrix creation

An initial point of difficulty for me was getting the input into a format that I can easily work with — a matrix. But converting a vector of vectors into a matrix in Julia is tricky. The `vcat`

function looks right at first glance, but it returns a vector of vectors rather than a matrix. The code that works is:

```
Matrix(transpose(hcat(vectors...)))
```

Weird, right? `hcat`

, presumably short for horizontal concatenation, is the starting point (`...`

splats the arguments) but then the matrix needed to be transposed to treat every vector as a row. Transposing a matrix changes the type to `LinearAlgebra.Transpose`

, so I need to wrap it with `Matrix`

to fix that. I found the whole thing bizarre, since interpreting a vector of equally-sized vectors as a matrix *should* be easy. In fact, I half-expected `Matrix(vector_of_vectors)`

to just work.

## Day 4: Bingo

What you can see, however, is a giant squid that has attached itself to the outside of your submarine. Maybe it wants to play bingo?

I went overboard with structs. I didn’t need to create a special `BingoBoard`

struct but I did. And the custom print method was totally unnecessary but fun:

The structs did let me define some neat functions, like `update!`

:

```
function update!(game::BingoGame, number::Int64)
match_coords = findfirst(x -> x == number, game.board.definition)
if !isnothing(match_coords)
game.state[match_coords] = true
end
end
```

Both parts of the solution then involved playing each number and checking for winning games. The first part looked for the first winning game.I encountered an off-by-one error here. I had to move the `number_index += 1`

line to the top of the `while`

loop. Otherwise I was using the bingo number that came *after* the number that triggered the win.

Part 2 was a bit quicker, arguably because I had the `has_won(game::BingoGame)`

function ready-to-go. The key component was this snippet that removed winning games from consideration after each number was called:

```
games = games[(!has_won).(games)]
```

Note that I’m negating `has_won`

, and then vectorising it with the period so that `(!has_won).(games)`

returns a Boolean array that I can then use to filter `games`

to include only the games that are yet to win. Then, when there are no games left to consider, the last game to have won is returned.

A handy function here was `score(game::BingoGame, number::Int64)`

, which scores a winning game:

```
function score(game::BingoGame, number::Int64)
negated_state = ones(Bool, size(game.state)...) - game.state
unmarked_numbers_only = negated_state .* game.board.definition # Hadamard product
sum_unmarked_numbers = sum(unmarked_numbers_only)
number * sum_unmarked_numbers
end
```

## Day 05 - Finding points on a line

You come across a field of hydrothermal vents on the ocean floor! These vents constantly produce large, opaque clouds, so it would be best to avoid them if possible.

This puzzle was just fun. The core task was determining the points on a line in 2-dimensional space.

I didn’t struggle much with this one, apart from discovering that `5:1`

in Julia yields no points. I implemented a `sequence`

function that automatically used a `-1`

step for this case:

```
function sequence(i, j)
if i > j
range(i, j, step = -1)
else
range(i, j, step = 1)
end
end
```

One of the patterns I’m falling into to help with parsing the Advent of Code input is to implement a `struct`

and bespoke function designed for the input format. The idea here is that if a line is represented in the input as “1,5 -> 3,8” then I should be able to turn it into a `Line`

with `Line("1,5 -> 3,8")`

.

To do this, I start with the points, which are represented like “1,5”:

```
struct Point
x::Int64
y::Int64
end
function Point(point_defn::AbstractString)
x_string, y_string = split(point_defn, ",")
x, y = parse(Int64, x_string), parse(Int64, y_string)
Point(x, y)
end
```

So now `Point(1, 5)`

gives me a point, but so does `Point("1,5")`

. I can extend this to a concept of `Line`

:

```
struct Line
a::Point
b::Point
end
function Line(line_defn::AbstractString)
point_defns = split(line_defn, " -> ")
a_string, b_string = point_defns[1], point_defns[2]
a, b = Point(a_string), Point(b_string)
Line(a, b)
end
```

Initially I was asking `point_defn`

and `line_defn`

to be of type `String`

rather than `AbstractString`

. This was messy because `split`

yields a vector of type `SubString`

, which I had to convert. In line with the Julia style guide it’s better to use abstract types rather than be overly specific, and both `String <: AbstractString`

and `SubString <: AbstractString`

.

## Day 6 - Counting lanternfish

A massive school of glowing lanternfish swims past. They must spawn quickly to reach such large numbers - maybe exponentially quickly? You should model their growth rate to be sure.

Exponential growth is a hint here that the number of fish is going to get very large very quickly and — perhaps — large enough for computational complexity to matter. If I were to model each fish individually it would likely be a very slow and memory-intensive count. However, the only distinguishing feature it the fish’s age, which is one of seven values.

In my first attempt I modelled the number of fish as a dictionary, specifically a `Dict{Int8, Int64}`

, and used an `age`

function with some messy logic. It gave me the correct answer and — since I don’t have 6 terabytes of RAM in my laptop — I assume that the code was efficient enough.

I later realised that this was a matrix problem! This allowed me to simplify my code substantially:

```
const age_matrix = [
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0]
function age(days_to_spawn::Vector{Int64}, days::Int64 = 1)
age_matrix^days * days_to_spawn
end
```

## Intermission: unit tests

It was also on day 6 that I decided to implement unit tests, and to go back to days 1 – 5 and do the same. Advent of Code provides a short example for every problem, and these make *perfect* unit tests.

```
Testing Running tests...
Test Summary: | Pass Total
Day 01 | 2 2
Test Summary: | Pass Total
Day 02 | 2 2
Test Summary: | Pass Total
Day 03 | 2 2
Test Summary: | Pass Total
Day 04 | 2 2
Test Summary: | Pass Total
Day 05 | 2 2
Test Summary: | Pass Total
Day 06 | 2 2
Testing AOC2021 tests passed
```

I couldn’t get these to work in GitHub Actions. My workflow couldn’t find the `Day01`

, `Day02`

, etc. submodules I set up to separate the code for each day. I was stumped, so I reached out to the Julia Discourse forum for help. Someone named “Rikh” not only answered my question but submitted a pull request to fix the issue! The Julia community is pretty great.

## Day 7 - Crab submarines

The crab submarines all need to be aligned before they’ll have enough power to blast a large enough hole for your submarine to get through… There’s one major catch - crab submarines can only move horizontally.

I was so sure that my first attempt for this problem would never finish processing that I even named my search function `brute_force`

. It searched through all possible positions that the crab could align to, from the minimum position to the maximum, and evaluated the fuel cost for each. Hardly elegant.

It turns out that the median position is optimal for part 1 and either ⌈mean⌉ or ⌊mean⌋ is optimal for part 2. I never implemented this because the brute force approach ended up working just fine, even for part 2.

It was for the second part that I added a `fuel_cost_function`

, which translates a positive movement value to a fuel cost. Part 1 used a `fuel_cost_function`

of `identity`

, such that the fuel cost was equal to the movement. I solved part 2 with what I called an *arithmetic* fuel cost — so called because it sums an arithmetic sequence `1:movement`

:

```
arithmetic_fuel_cost(movement::Int64) = movement(movement + 1) / 2
```

I use one of my favourite features of Julia in my implementation of `fuel_to_align`

, which calculates the fuel required to move all crab submarines to a given position. The dots in my code below represent Julia’s loop fusion, which allows me to vectorise arbitrary functions. I vectorise `abs`

, subtraction, and even the arbitrary `fuel_cost_function`

.

```
function fuel_to_align(
positions::Vector{Int64},
target::Integer,
fuel_cost_function::Function = identity
)
absolute_movements = abs.(positions .- target)
fuel_costs = fuel_cost_function.(absolute_movements)
sum(fuel_costs)
end
```

## Day 8: 7-segment displays

the signals which control the segments have been mixed up on each display… the wire/segment connections are mixed up separately for each four-digit display!

This puzzle had a cryptography feel to it and I loved that. In my first attempt I identified which segments mapped to which. It worked, but it made my code much more complicated than it needed to be. I only need to be able to identify the digits represented by each display, and realising that allowed me to simplify my code.

A true gems of Julia syntax shone through here: mathematical notation as function names. I represented my symbols as sets of segments, and so I was able to use set operations such as ⊆ and ⊈. Note also the use of ∉ as “not in”:

```
# There are three 6-segment elements: six, nine, zero
patterns_of_length_6 = patterns_of_length(patterns, 6)
# four is a subset of nine but not six or zero
nine = filter(s -> four ⊆ s, patterns_of_length_6) |> first
# six is the only 6-segment digit that is not a superset of one
six = filter(s -> one ⊈ s, patterns_of_length_6) |> first
# and by process of elimination
zero = filter(s -> s ∉ [six, nine], patterns_of_length_6) |> first
```

There’s some subjectivity here. Some people despise seeing mathematical notation in their code. But as a former mathematician it makes me happy. All of this is base Julia as well — I didn’t have to define any of the set functions. And in VSCode I can type `\subseteq`

and it will autocomplete to ⊆.

Strangely enough, `⊂`

isn’t defined in base Julia. The distinction between proper and non-proper subsetting isn’t relevant for my code, though.

I’m also piping into the `first`

function which takes the first element of these sets (they’re all singletons, so the first element is also the only element). Julia’s native pipe is fairly basic, supporting only unary functions. More complicated piping can be achieved with the `Pipe`

package, or the `Chain`

package I used in day 1.

The image at the top of this page is by Jessica Lynn Lewis and is used under the terms of the the Pexels License.