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 :)