Re-posted from: https://www.ericburden.work/blog/2021/12/06/advent-of-code-2021-day-5/
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.
Re-posted from: https://ericburden.work/blog/2021/12/06/advent-of-code-2021-day-5/
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!
Find the problem description HERE.
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.
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 comparing
Points more ergonomic. Now, on to 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
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!
Re-posted from: https://ericburden.work/blog/2021/12/06/advent-of-code-2021-day-6/
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!
Find the problem description HERE.
Today’s puzzle has us calculating the number of lanternfish over time, with a
given spawn rate. The key insight here is that there are 9 possible ages of fish
(0-8), and each fish gets ‘reset’ to age 6 after spawning a new fish. New fish
are spawned at age 8. Because we are interested in the total population of fish
at the end of some time period, there’s no need to track each fish individually.
So, for our input parsing, we count the number of fish who are initially at each
possible age and return a vector of length 9, where each index contains the
count of fish whose number of remaining days until spawning is
index - 1 (Julia is 1-indexed).
function ingest(path)
fish = open(inputpath) do f
readsplit(x) = split(readchomp(x), ",")
[parse(Int, s) for s in readsplit(f)]
end
# Instead of reporting back the fish individually, return a
# Vector of length `9` where each index represents the number
# of fish of age `idx - 1` . (Julia is 1-indexed)
groups = zeros(Int64, 9)
for f in fish
groups[f+1] += 1
end
return groups
end
For reasons that will become clear shortly, there’s really not a Part One and
Part Two to today’s puzzle. Because the fish are spawning at a constant rate,
we can keep track of groups of fish by the number of days they have before
spawning. Each day, every fish’s number of remaining days is reduce by one,
except for fish whose remaining days are 0. These fish will have their
remaining days reset to 6, and they will also each produce a fish with
remaining days of 8. So, we can essentially just rotate our array to the
left, and add the value of groups[9] (the new fish spawned) to groups[7]
(the number of fish who spawned).
# Create an Iterator over Generations of Fish Schools -------------------------
struct School
agegroups::Vector{Int64}
end
# This function is called for the first iteration
function Base.iterate(iter::School)
groups = copy(iter.agegroups)
(sum(groups), groups)
end
# This function is called for each subsequent iteration
# Instead of keeping track of each fish and its progeny, we group all
# the fish by age and calculate the size of the next generation. Each
# generation/iteration creates `groups[1]` new fish at age `8` and rotates
# the group counts one to the left (such that the fish that were age `2`
# are now age `1`)
function Base.iterate(iter::School, groups::Vector{Int64})
groups = circshift(groups, -1)
groups[7] += groups[9]
(sum(groups), groups)
end
# Used to get the `nth` generation of a school.
function Base.getindex(school::School, i::Int)
for (generation, groups) in enumerate(school)
generation > i && return groups
end
end
# Solve the puzzle ------------------------------------------------------------
# Solve the puzzle, creating an iterator over generations of a
# `School` and summing the values for a given day.
function solve(input, days)
school = School(input)
return sum(school[days])
end
Like yesterday, I found it handy to implement some of the iterator interface
for School, a struct containing only the agegroups array. I also discovered
I could implement getindex() as a method to get the nth element from the
School iterator, which could technically iterate forever (or until the values
overflowed). This works by iterating School forward the indicated number of
‘days’ and taking the last result.
Part one asks us to determine the count of fish at 80 days, and part two asks
for the same thing at 256 days, which means making no change other than the
second argument to solve().
I spent WAY too much time today trying to figure out how to get the nth value
from an iterator. I’m still not sure my result is the most idiomatic way of
handling this in Julia. In Rust, there’s an nth() function for iterators that
does this, and I was looking for something similar in Julia. I am very happy with
how this code came out, but I do find myself wishing the documentation were
organized differently. Or, maybe it’s just that I don’t understand Julia well
enough yet, which is probably it. Either way, I understand it a bit better today
that I did yesterday, which is really the point of all this. So, a win!
If you found a different solution (or spotted a mistake in one of mine),
please drop me a line!