Advent of Code 2021 - Day 1

By Eric Burden | December 1, 2021

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 1 - Sonar Sweep

Find the problem description HERE.

Part One - Find the Bumps

For this first day, I’ll share my code to read the input. Since I expect most days to be variations on this theme, I predict that I’ll only share this “parsing” code when it’s sufficiently interesting and different for future puzzles.

inputpath = normpath(joinpath(@__FILE__,"..","..","..","inputs"))
input = open("$inputpath/Day01/Input01.txt") do f
    [parse(Int, s) for s in readlines(f)]
end

The strategy for getting files from absolute paths in projects in Julia is a bit…odd, but it works. Otherwise, I’m just using a list comprehension to read each line, parse it into an integer, and return an array of the input numbers.

As for the actual puzzle part, the first day is generally a pretty gentle introduction to AoC, and 2021 is no exception. The first puzzle gives us a list of numbers (in the form of a line-separated text file) and asks us to count each number that is greater than the number immediately before it.

The code for solving the first part looks like:

function part1(input)
    # Returns an array of `1`s and `0`s, where a `1` indicates an increase
    increases(x) = diff(x) .> 0

    # Given the input, find the increases, then sum them
    (input
    |> increases
    |> sum)
end

I absolutely love the syntax for defining small utility functions in Julia (increases(x)), and for chaining operations like this. I find it allows the language to be both very concise and very expressive at the same time. I tend to prefer the syntax with the pipe operators at the beginning of the line, but in order to do that I need to ‘trick’ Julia into thinking it’s all one ‘line’ with the parentheses. Otherwise, Julia would prefer I add the pipes to the end of the previous line. That works, but I like having the operator at the front of the line better, I find it easier to read.

Part Two - Smooth(er) Sailing

As is customary, part two is a bit of a difficulty bump from part one, but nothing major here. Now, instead of comparing single numbers, we need to compare a rolling three-number window to the next three-number window. This is the sort of thing that Julia’s view()1 function was made for.

function part2(input)
    # Creates an array of views into `x` representing a sliding window of width `w`
    windows(x, w) = [view(x, i:(i+w-1)) for i in 1:(length(x)-w+1)]

    # Returns an array of `1`s and `0`s, where a `1` indicates an increase
    increases(x) = diff(x) .> 0

    # Create an array of three-number views into `input`, sum each window,
    # then compare that sum to the next sum with `increaeses`. Finally, sum
    # the number of increases.
    (windows(input, 3)
    |> x -> map(sum, x)
    |> increases
    |> sum)
end

That windows function is a bit dense, but otherwise I’m pleased as punch with this code.

Update

After a bit of additional consideration, it occurred to me that there is a simpler way to handle part two. Consider the first part of the example:

199  A      
200  A B    
208  A B  
210    B

Now, you could determine that 199 + 200 + 208 = 607 and 200 + 208 + 210 = 618, and that since 618 > 607, there is an increase from the first window to the second. Or, you could realize (as I belatedly did) that both windows share 200 and 208, and that the only comparison that matters is 210 > 199. Which led to the following optimization:

function part2(input)
    # Compare each number to the number 4 indices prior and return a
    # boolean array. This works because two overlapping three-wide 
    # windows into an array only differ by a single value, the first
    # number of the first window and the last value of the second
    # window.
    increases(x) = x[4:end] .> x[1:(end-3)]

    (input
    |> increases
    |> sum)
end

This is, of course, much more efficient that my previous solution using view(), although it doesn’t feel as nifty… As for how much more efficient…

Part 01:   2.897 μs (5 allocations: 20.31 KiB)
Part 02a: 28.081 μs (8 allocations: 114.20 KiB) < first version
Part 02b:  4.566 μs (6 allocations: 36.06 KiB)  < second version

Wrap-Up

Day 1 felt like a bit of a softball, which I heartily approve of! I definitely spent more time Googling for function names than coming up with an approach to a solution, but in a new(ish) language, I don’t really mind. I do like the way that Julia’s syntax and disposition towards both functional-style programming and vectorized operations makes me think a bit differently about my approach to solving these puzzles. Sometimes, this leads to being distracted by some of the new shiny toys in a new language, but that’s part of the fun.I can’t wait to see how the rest of the puzzles turn out!

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


  1. https://docs.julialang.org/en/v1/base/arrays/#Base.view ↩︎

comments powered by Disqus