Advent of Code 2023 Days 8, 9, and 10 Highlights

Travel disrupted my blogging a bit, but I mostly managed to keep up with the daily AoC challenges, just didn’t have time to write it down. This post is a bit of a catching up, so we’ll (briefly) look at 3 days :)

Day 8

I went for an Elixir solution here, and overall it worked very nicely, except for one thing - Elixir doesn’t have a good easily accessible implementation of one of the functions we needed and it’s a bit of a pain to implement it. But I found a little hack that solved that ;) Overall, it’s one of my favorite tasks so far.

The Livebook

Parsing was thankfully straightforward. I transformed input into a tuple of a list of moves and a map mapping each node to its left and right connections.

def parse_input(input) do
  [moves | network] = input |> String.trim() |> String.split("\n", trim: true)

  network =
    Enum.map(network, fn node ->
      [node, paths] = String.split(node, " = ")
      [left, right] = paths |> String.trim("(") |> String.trim(")") |> String.split(", ")
      {node, %{left: left, right: right}}
    end)
    |> Enum.into(%{})

  {String.graphemes(moves), network}
end

Then, the part 1 was just chaining Stream.cycle and Enum.reduce_while - lazy collections for the win! I also extracted a little helper for moving through the network:

def do_move(network, pos, "L"), do: network[pos][:left]
def do_move(network, pos, "R"), do: network[pos][:right]

def p1(moves, network) when is_list(moves) and is_map(network) do
  Stream.cycle(moves)
  |> Enum.reduce_while({"AAA", 0}, fn move, {pos, steps_taken} ->
    pos = do_move(network, pos, move)
    steps_taken = steps_taken + 1

    if pos == "ZZZ", do: {:halt, steps_taken}, else: {:cont, {pos, steps_taken}}
  end)
end

Soling part 2 requires two tricks:

• maintaining states of several ghosts at the same time to calculate how long it takes for each ghost to arrive at their terminal node (the period of the ghost, so to speak)
• since ghosts are looping with varying periods, we can figure out the earliest moment the loops will sync by using least common multiple.

Calculating those periods for each ghost is easy enough:

def ghost_steps(moves, network) do
  nodes = Map.keys(network)

  states =
    Enum.filter(nodes, &String.ends_with?(&1, "A"))
    |> Enum.map(fn node -> {node, {node, 0}} end)
    |> Enum.into(%{})

  z_nodes = Enum.filter(nodes, &String.ends_with?(&1, "Z")) |> MapSet.new()

  Stream.cycle(moves)
  |> Enum.reduce_while(
    {states, z_nodes, []},
    fn move, {states, z_nodes, steps} ->
      if map_size(states) == 0 do
        {:halt, steps}
      else
        states =
          Enum.map(states, fn {node, {pos, step}} ->
            pos = do_move(network, pos, move)
            {node, {pos, step + 1}}
          end)
          |> Enum.into(states)

        {states, steps} =
          Enum.filter(states, fn {_node, {pos, _}} -> pos in z_nodes end)
          |> Enum.reduce(
            {states, steps},
            fn {finished_node, {_pos, step}}, {states, steps} ->
              {Map.delete(states, finished_node), [step | steps]}
            end
          )

        {:cont, {states, z_nodes, steps}}
      end
    end
  )
end

We assume that we have the same number of ghosts as A nodes and each ghost starts from their own A node. So we name each ghost the same as the node where they start and we map that name to a tuple of the current node and steps taken. This is our states map. z_nodes is a set of all terminal nodes ending with Z.

We can now repeat the same Stream.cycle(moves) |> Enum.reduce_while(...) trick as in the part 1. We will progressively build up a list of steps ghosts needed to reach their Z-node. If the ghost reaches their Z-node, we put the number of steps associated with the ghost in the steps list and remove the ghost from the states map - we don’t need to track them anymore.

For my input, I got the following list: [19783, 19241, 16531, 14363, 12737, 11653].

Since I already got an idea that I will need to use LCM, I plugged those numbers in Julia’s REPL, got the answer 9_177_460_370_549, and validated that it’s indeed the right one. But now I needed to find or write an LCM function in Elixir. I tried to do it, it was too annoying to do, so I ended up just … calling Julia on the command line from Elixir xD So here’s the remaining pieces:

def lcm(nums) do
  expr = "x=lcm(#{inspect(nums)}); println(x)"
  {res, 0} = System.cmd("julia", ["--eval", expr], stderr_to_stdout: true)
  String.trim(res) |> String.to_integer()
end

def p2(moves, network) when is_list(moves) and is_map(network) do
  ghost_steps(moves, network) |> lcm()
end

True polyglot programming, isn’t it? :)

Day 9

I switched to Julia for days 9 and 10 because both tasks were looking like a good match for it.

Day 9’s solution code

There’s not much to say about it: we just literally follow the outlined steps and do some broadcasting to repeat them for each row. Thankfully, Julia’s arrays are very efficient, so we could easily implement part 2 with a simple if statement and a ternary operator:

using Pipe

parse_input(input) = @pipe strip(input) |> split(_, "\n") |> split.(_) |> map(x -> parse.(Int64, x), _)

function predict(value_history; forward=true)
  sequence = deepcopy(value_history)
  sequences = [sequence]

  while !all(x -> x == 0, sequence)
    sequence = @pipe [sequence[i+1] - sequence[i] for i in eachindex(sequence) if i < length(sequence)]
    push!(sequences, sequence)
  end

  for i in (length(sequences)-1):-1:1
    seq = sequences[i]

    if forward
      push!(seq, last(seq) + last(sequences[i+1]))
    else
      pushfirst!(seq, first(seq) - first(sequences[i+1]))
    end
  end

  forward ? last(sequences[1]) : first(sequences[1])
end

p1(history) = predict.(history) |> sum
p2(history) = predict.(history; forward=false) |> sum

Day 10

Day 10 was very interesting, but part 2 was quite challenging. In the end, I gave up trying to catch the edge-cases in my handy-made “flood fill + detect the parts we can squeeze through” logic and looked at the solutions mega thread. There were a lot of mentions of even-odd rule and that gave me an idea for the solution that after some painful debugging finally worked.

Full solution code

Part 1 though didn’t require cheating and was quite easy. This time, we better parse the input as a proper matrix:

parse_input(input) = @pipe input |> strip |> split(_, "\n") |> collect.(_) |> mapreduce(permutedims, vcat, _)

And we’ll need a couple of constants and a helper checking that we are not running out of bounds:

CONNECT_DELTAS = Dict(
  '.' => [],
  '|' => [CartesianIndex(-1, 0), CartesianIndex(1, 0)],
  '-' => [CartesianIndex(0, -1), CartesianIndex(0, 1)],
  'L' => [CartesianIndex(-1, 0), CartesianIndex(0, 1)],
  'J' => [CartesianIndex(-1, 0), CartesianIndex(0, -1)],
  '7' => [CartesianIndex(1, 0), CartesianIndex(0, -1)],
  'F' => [CartesianIndex(1, 0), CartesianIndex(0, 1)],
)
NEIGHBOUR_DELTAS = values(CONNECT_DELTAS) |> Iterators.flatten |> Set |> collect
PIPE_SHAPES = @pipe keys(CONNECT_DELTAS) |> filter(x -> x != '.', _) |> collect

isvalid(tiles, pos::CartesianIndex{2})::Bool =
  pos[1] >= 1 && pos[2] >= 1 && pos[1] <= size(tiles)[1] && pos[2] <= size(tiles)[2]

We can now write a function to find coordinates that a tile at a pos coordinates connects:

function connects(tiles, pos::CartesianIndex{2}; shape=nothing)::Vector{CartesianIndex{2}}
  shape = isnothing(shape) ? tiles[pos] : shape

  [pos + delta for delta in CONNECT_DELTAS[shape] if isvalid(tiles, pos + delta)]
end

And a function that checks if two neighbouring tiles have pipe pieces that are connected:

function isconnected(tiles, pos1::CartesianIndex{2}, pos2::CartesianIndex{2}; pos1_shape=Nothing)::Bool
  pos2 in connects(tiles, pos1; shape=pos1_shape) && pos1 in connects(tiles, pos2)
end

And a function that returns all neighbours of a given tile:

neighbours(tiles, pos) = [pos + delta for delta in NEIGHBOUR_DELTAS if isvalid(tiles, pos + delta)]

And a function that returns a tuple of the coordinates and shape of S:

function start_pos_and_shape(tiles)
  pos = findfirst(x -> x == 'S', tiles)

  for shape in PIPE_SHAPES
    if [isconnected(tiles, pos, n_pos; pos1_shape=shape) for n_pos in neighbours(tiles, pos)] |> sum == 2
      return (pos, shape)
    end
  end
end

In this case we just try all the shapes and find the one where it makes S connect with pipes located in exactly 2 of its neighbours - we know that this must happen since S is part of the loop.

We can now walk the loop and build a dictionary mapping the coordinates of a tile to its distance from the loop’s start in one of the directions:

function loop_steps(tiles; first_neighbour_idx=1)
  (s_pos, s_shape) = start_pos_and_shape(tiles)
  tiles = deepcopy(tiles)
  tiles[s_pos] = s_shape

  distances = Dict(s_pos => 0)
  pos = connects(tiles, s_pos)[first_neighbour_idx]
  steps = 1
  distances[pos] = steps

  while true
    next_pos = [next_pos for next_pos in connects(tiles, pos) if next_pos ∉ keys(distances)]
    if isempty(next_pos)
      return distances
    else
      pos = first(next_pos)
      steps += 1
      distances[pos] = steps
    end
  end
end

We don’t really care in which direction we are going. We know that there are 2 options, and we can make the first step selecting either one of the 2 tiles connected to the start. We accept the index of the option we choose as an optional argument with a default value of 1.

And running this in the opposite direction we can just find the tile where both forward and backward pass distances match, giving us the answer to the part 1:

function p1(tiles)
  distances = loop_steps(tiles)
  backward_distances = loop_steps(tiles; first_neighbour_idx=2)

  for (pos, dist) in distances
    if backward_distances[pos] == dist && dist != 0
      return dist
    end
  end
end

For the part 2, we’ll need to remove the non-loop pipes + it’ll be useful to know the tiles belonging to the loop:

function clean_tiles(tiles)
  tiles = deepcopy(tiles)
  loop_tiles = loop_steps(tiles) |> keys |> Set

  s_pos, s_shape = start_pos_and_shape(tiles)
  tiles[s_pos] = s_shape

  for pos in CartesianIndices(tiles)
    if pos ∉ loop_tiles
      tiles[pos] = '.'
    end
  end

  (loop_tiles, tiles)
end

After looking at my now cleaned input, I saw that the pipe maze is surrounded by empty space. We can safely assume that the leftmost part of our input is by default will be outside of the loop or the loop will be going through it in case of test examples, but those cells still won’t be inside anyways.

We can now consider each row by itself. For each tile, moving from the left, if we cross the loop once, we are now inside the loop. If we cross it twice, we are outside the loop. If we cross it three times, we are inside again, etc. This is the essence of the even-odd rule.

We need to add additional condition though: in case we encounter this shape └───┘ or this shape ┌───┐ we can squeeze through, so we don’t need to count / flip our inside/outside state. However, if we encounter this └───┐ or this ┌───┘ we cannot squeeze through anymore. We can track the previously encountered angle pipe direction (up or down) as a boolean setting it to nothing when we didn’t encounter an angle pipe or after we encountered the second angle pipe. We also know that the only tiles in between angle pipes are the loop pipes, so we don’t need to care about remembering them - we will just update the inside/outside state flag once we “exit” the squeeze or run into the crossing.

In the end, we can count create a bit array of the same size as tiles, mark the cells that we know are outside using the logic described above, mark the loop cells as “outside” as well (since we don’t want to count them), and then count the number of cells that are not marked as outside - this will give us the answer to the puzzle.

function p2(tiles)
  (loop_tiles, tiles) = clean_tiles(tiles)
  outside = fill(false, size(tiles))

  for row in 1:size(tiles)[1]
    angle_pipe_up = nothing
    inside = false

    for col in 1:size(tiles)[2]
      tile = tiles[row, col]

      if tile == '|'
        inside = !inside
      elseif tile == 'L'
        angle_pipe_up = true
      elseif tile == 'F'
        angle_pipe_up = false
      elseif tile == 'J'
        if !angle_pipe_up
          inside = !inside
        end

        angle_pipe_up = nothing
      elseif tile == '7'
        if angle_pipe_up
          inside = !inside
        end

        angle_pipe_up = nothing
      end

      if !inside
        outside[row, col] = true
      end
    end
  end

  for loop_tile in loop_tiles
    outside[loop_tile] = true
  end

  (size(tiles) |> prod) - sum(outside)
end

One somewhat surprising thing was that I didn’t need to do this for vertical squeezes. I thought I will need to do a similar scan flipping inside/outside for each column, going from the top, but it turned out to be unnecessary for the test cases, so I tried this with the input I’ve got and… it worked! Oh well.