Advent of Code 2023 Day 3 Highlights
Day 3 was fun! I ended up re-writing my solution almost completely after the first part, because I figured that I can do it much better. That unlocked a couple more simplifications, and (mostly) trivialized part 2. This is also the first day I used Julia this year.
Here’s my (rewritten) solution. And here’s the first version of my approach for part 1 (which worked, but I didn’t like).
Julia, being a scientific computing/array language naturally is amazing for tasks where you need to do something with coordinates and 2/3/4/etc. dimensional grids. So I decided to use it today.
One very useful type to know for dealing with this kind of tasks in Julia is CartesianIndex. I knew that, so that’s how I modelled neighbour coordinate shifts from the get go:
neighbour_deltas = [
CartesianIndex(-1, 0), CartesianIndex(1, 0), CartesianIndex(0, -1), CartesianIndex(0, 1),
CartesianIndex(-1, -1), CartesianIndex(-1, 1), CartesianIndex(1, -1), CartesianIndex(1, 1)
]
You can sum cartesian indices and do a bunch of other useful things with them, including, naturally, using them to index into an array of matching dimensions.
When I do AoC in Julia, I allow myself using packages that don’t trivialize the task too much. One of my
go-tos is a package called Pipe. It provides a @pipe
macro
that allows using _
to specify in which position an argument should be piped into a function. Just a syntactic
sugar, but I like it.
Initially, I went through each row of the grid collecting numbers until they were broken by a symbol or a line break
and maintaining a boolean value that signified if I detected a neighbouring symbol. Even though it worked,
it was not very Julia-like and I didn’t like the solution too much. Mid-way through writing it, I figured that
I can do much better by doing some set intersections. Additionally, Julia provides some useful functions such as
findall
.
findall
in particular allows us to easily create vectors with all digit positions and all symbol positions:
symbol_positions = findall(issymbol, inp) |> Set
# sort them in a row-by-row order, so we can rely on digits of one number following each other
digit_positions = @pipe findall(isdigit, inp) |> sort(_, by=x -> (x[1], x[2]))
You can see that I also sort digit positions in such a way that adjacent digits will follow each other.
If I was writing this in Elixir, that would’ve been a point where I would’ve used Enum.reduce
, but sadly
fold in Julia is much less pleasant to use, so instead we extract a State
type:
mutable struct State
digits::Vector{Char}
positions::Vector{CartesianIndex{2}}
State() = new([], [])
end
function add_digit!(s::State, digit::Char, pos::CartesianIndex{2})
push!(s.digits, digit)
push!(s.positions, pos)
end
We also define an empty constructor for it and a method that allows us to add one digit character together with
its CartesianIndex
.
We also have the following helper function:
function push_if_part_number!(
part_numbers::Vector{Tuple{Int64,Set{CartesianIndex}}},
state::State,
symbol_positions::Set{CartesianIndex{2}}
)
candidate = @pipe String(state.digits) |> parse(Int64, _)
all_neighbour_positions = map(pos -> [pos] .+ neighbour_deltas, state.positions) |> Iterators.flatten
neighbouring_symbol_positions = intersect(symbol_positions, all_neighbour_positions)
if !isempty(neighbouring_symbol_positions)
push!(part_numbers, (candidate, neighbouring_symbol_positions))
end
end
This updates a part_numbers
vector of part number and the set of their neighbour symbol coordinates tuples with
the number we can parse from the state.digits
if we find that their neighbourhood contains symbols.
We don’t need that set of neighbour symbol coordinates yet, but we’ll need that for part 2 :)
You can also see some delightful features of Julia here: broadcasting and adding pos
cartesian index to all
neighbour_deltas
so that we get all neighbours for each position; the aforementioned @pipe
trick;
built-in set operators such as intersect
.
Anyhow, we can now put it all together and create a function that will return us all part numbers (and sets of their neighbouring symbol coordinates):
function part_numbers(inp)
part_numbers = Vector{Tuple{Int64,Set{CartesianIndex}}}()
symbol_positions = findall(issymbol, inp) |> Set
digit_positions = @pipe findall(isdigit, inp) |> sort(_, by=x -> (x[1], x[2]))
state = State()
for digit_position in digit_positions
# if we have digits and the current digit doesn't directly follow them, we can push the number and clear the state
if !isempty(state.digits) && (digit_position != last(state.positions) + CartesianIndex(0, 1))
push_if_part_number!(part_numbers, state, symbol_positions)
state = State()
end
add_digit!(state, inp[digit_position], digit_position)
end
if !isempty(state.digits)
push_if_part_number!(part_numbers, state, symbol_positions)
end
part_numbers
end
The if
condition inside the for
loop walking through all digit_positions
was initially this:
if isempty(state.digits) || (digit_position == last(state.positions) + CartesianIndex(0, 1))
add_digit!(state, inp[digit_position], digit_position)
else
push_if_part_number!(part_numbers, state, symbol_positions)
state = State()
add_digit!(state, inp[digit_position], digit_position)
end
It’s easy to see that we call add_digit!
no matter what here, so we can move it below the if
, and just do
push_if_part_number!
call followed by the state clear in case the reverse condition holds.
Then, the first part’s solution is straightforward:
p1(inp) = part_numbers(inp) .|> first |> sum
Part #2
Given a solution for the part 1 that didn’t originally track the set of neighbouring symbol coordinates, it was easy to adapt it to do it. Then, we can do this:
function gear_numbers(inp)
gear_symbol_positions = findall(ch -> ch == '*', inp)
candidate_gears = Dict{CartesianIndex{2},Vector{Int64}}()
for (part_number, adjacent_symbol_positions) = part_numbers(inp)
adjacent_gear_symbol_positions = intersect(adjacent_symbol_positions, gear_symbol_positions)
for candidate_gear_position = adjacent_gear_symbol_positions
pns = get(candidate_gears, candidate_gear_position, [])
push!(pns, part_number)
candidate_gears[candidate_gear_position] = pns
end
end
candidate_gears = values(candidate_gears) |> collect
filter(numbers -> length(numbers) == 2, candidate_gears)
end
Here, we again use findall
to find all *
symbol coordinates. Then for each part number, we find all its
adjacent *
symbol positions with the set intersection (we get all neighbouring symbol coords from the part_numbers
function), and create a dictionary candidate_gears
that maps each candidate gear position with a vector of its
part numbers. We know that valid gears will have 2 part numbers adjacent to it, so we can just filter
on this.
And then, the part 2 is solved easily:
p2(inp) = gear_numbers(inp) .|> prod |> sum
Finally, I like to use @show
macro for both debugging and for showing my answers. When I run this code
with julia d03.jl
, that’s what I see:
➜ aoc2023 git:(main) julia d03.jl
p1(input) == 540212 = true
p2(input) == 87605697 = true
Funny Stuff
So, I traveled through time and ended up naming my repo aoc2024
xD Fixed that, the new repo is located here now:
https://github.com/Lakret/aoc2023. Thanks, @Isti115 for pointing this out!
Also, I got a response from
the official Elixir language account for the
gripe I had with the Regex.scan
function during the first day.
So, here’s my first PR to Elixir, let’s see how that goes :)
If you enjoyed this content, you can sponsor me on Github to produce more videos / educational blog posts.
And if you're looking for consulting services, feel free to contact me .