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 5 - Hydrothermal Venture

Find the problem description HERE.

The Input - Basic Geometry

For this puzzle, we’re tasked with identifying points on lines, given the endpoints of the lines. I’ll admit, I didn’t read the instructions for part one terribly well and missed that I didn’t need the diagonals at first, so my first pass at parsing the data included functionality to find points on diagonal lines, including those with slopes other than 45 degrees. It turned out to be useful for part two, though, so I didn’t mind. My approach here, and for as many days as it makes sense, is to try to use structs as much as I can. This helps me get a better handle on all the options that Julia provides. It often means a lot of searching/reading the docs, but I find it to be well worth the effort.

# Types and Structs -----------------------------------------------------------

# Type alias for `Point`
const Point = NamedTuple{(:x, :y), Tuple{Int, Int}}
topoint(x, y) = (x = x, y = y)

# Type alias and constructors for `Slope`
const Slope = NamedTuple{(:dx, :dy), Tuple{Int, Int}}
toslope(dx, dy) = (dx = dx, dy = dy)

function getslope(a::Point, b::Point)::Slope
    (xdiff, ydiff) = (b.x - a.x, b.y - a.y)
    xygcd = gcd(xdiff, ydiff)
    (dx, dy) = (xdiff ÷ xygcd, ydiff ÷ xygcd)
    toslope(dx, dy)
end

# Represents a line from point `a` to point `b`
struct Line
    a::Point
    b::Point
    slope::Slope
end

Line(a::Point, b::Point) = Line(a, b, getslope(a, b))

function Line(s::AbstractString)::Line
    re = r"(\d+),(\d+) -> (\d+),(\d+)"
    rematch = match(re, s)
    (x1, y1, x2, y2) = parse.(Int, rematch.captures)
    pointa = topoint(x1, y1)
    pointb = topoint(x2, y2)
    Line(pointa, pointb)
end

# Ingestion -------------------------------------------------------------------

# Read input from a file path
function ingest(path)
    open(inputpath) do f
        [Line(s) for s in readlines(f)]
    end
end

I’ve found that, for simple data types like Point, Julia tends to perform faster when using a type alias to something like a NamedTuple instead of creating a struct or mutable struct.

Part One - Criss Cross

I’m betting it’s the hydrothermal vents, and not our “dismal” Bingo performance, that got rid of yesterday’s giant squid. Looks like there’s a lot of these things! Our task here is to find all the points where at least two lines of vents cross, but only the horizontal and vertical lines. There are diagonals in the input, but we’re ignoring them for now.

# Iterator Implementation -----------------------------------------------------

# Iterator interface implementations for `Line`
Base.iterate(line::Line) = (line.a, line.a)
Base.eltype(::Type{Line}) = Point

function Base.iterate(line::Line, lastpoint::Point)
    lastpoint == line.b && return nothing
    nextpoint = lastpoint + line.slope
    (nextpoint, nextpoint)
end

function Base.length(line::Line) 
    (a, b) = (line.a, line.b)
    return max(abs(b.x - a.x), abs(b.y - a.y)) + 1
end

# Operator Overloads ----------------------------------------------------------

# Operator overloading for adding a `Slope` to a `Point`
function Base.:+(point::Point, slope::Slope)::Point
    (x, y) = (point.x + slope.dx, point.y + slope.dy)
    topoint(x, y)
end

# Operator overloading for comparing `Points`
function Base.:(==)(a::Point, b::Point)
    a.x == b.x && a.y == b.y
end

# Solve Part One --------------------------------------------------------------

# Fill out a `Matrix` by indicating the number of lines that 
# cross each `Point`/index. Skip the diagonal lines. Once filled out,
# count the indices containing a value greater than 1, indicating
# an overlap.
function part1(input)
    pointsmap = zeros(Int64, 1000, 1000)
    for line in input
        (isvertical(line) || ishorizontal(line)) || continue
        points = collect(line)
        for (x, y) in points
            pointsmap[x, y] += 1
        end
    end

    count(x -> x > 1, pointsmap)
end

Here I’ve implemented my very ~first~ second iterator in Julia (I actually came back and refactored this one in after finishing Day 6, more on that later.) The iterator leverages Julia’s iterator interface to pretty efficiently generate a list of points on the line. We do this by finding the “slope”, which is really just the change in the x/y coordinates per ‘step’ along the line, then repeatedly adding the slope to point a until we get to point b. Implementing both versions of iterate(), eltype(), and length() means we can use collect()on a Line to get all the Points in that line. Neat! I also figured out how to overload the operators to make adding the Slope to a Point and comparingPoints more ergonomic. Now, on to the hard part.

Part Two - The Hard Part?

Oh. Nevermind.

# Exactly the same as Part 1, just without skipping the 
# diagonal `Line`s.
function part2(input)
    pointsmap = zeros(Int64, 1000, 1000)
    for line in input
        points = collect(line)
        for (x, y) in points
            pointsmap[x, y] += 1
        end
    end

    count(x -> x > 1, pointsmap)
end

Wrap Up

Today was a very productive day. I got to explore implementing iterators (which is something I really like doing in Rust as well) as well as overloading operators to ease basic math with my own Types. I went through a couple of variations and refactors on this code, but the current version shown here was the fastest (on my machine) by far, finishing both parts in under 5ms. That’s a good bit slower than previous days, but it seems like calculating all those Points adds up. I have a sneaking suspicion that there’s some bit of efficiency I’m missing, but I can’t really see what it would be. Maybe after spending some more time with Julia this month, I’ll be able to come back to this one and give it a boost. Even if not, I was able to add a couple of new tools to by toolbelt today, and that is a win!

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