In part one of this post, I talked about my tribulations trying to solve 2024’s Advent of Code using Elixer. I ended with my solution to part 1 of day 6, which was too inefficient to re-use for part 2. This article details how I re-wrote my day 6 solution more efficiently and, I hope, more elegantly.

Transforming the input data

This time, instead of working with a flattened grid (an optimisation in languages with array-based lists that doesn’t apply to Elixer’s linked lists) I’ve created a list of tuples comprising 2D coordinates and values.

{:ok, input} = File.read("../input/06-input.txt")

grid = input
|> String.trim
|> String.split("\n")
|> Enum.reverse
|> Enum.map(&String.graphemes/1)
|> Enum.with_index
|> Enum.map(fn {row, y} ->
  row
  |> Enum.with_index
  |> Enum.map(fn {val, x} -> {{x, y}, val} end)
end)
|> Enum.concat

cells = Map.new(grid)

{start_pos, start_dir} =  grid
|> Enum.find(fn {_pos, val} -> val in ["^", ">", "v", "<"] end)

Part 1 Solution

Again I’ve used reduce_while/3 but this time my accumulator is a MapSet, rather than a linked list based on the entire grid as the input. The advantages of a MapSet are

• that lookups happen in constant time (O(1)) compared to linear time (O(n)) with linked lists

• and that unless all cells are traversed, the set will have fewer members than elements in the flat grid list.

visited = Stream.iterate(40, & &1 + 1)
|> Enum.reduce_while(
{start_pos, start_dir, MapSet.new([start_pos])},
fn _i, {pos, dir, visited} ->
  case Gallivant.update_position(pos, dir, cells) do
    {new_pos, new_dir} ->
      {:cont, {new_pos, new_dir, visited |> MapSet.put(new_pos)}}
    :out_of_bounds ->
      {:halt, visited}
    end
end)

path_length = MapSet.size(visited)
IO.puts("Part 1 result: #{path_length}")

The business logic is far simpler than in my first attempt. I’ve used mappings to deal with transformations of the “guard” grapheme. The rest is a bit of basic vector maths and pattern matching.

defmodule Gallivant do
  @offsets %{"^" => {0, 1}, ">" => {1, 0}, "v" => {0, -1}, "<" => {-1, 0}}
  @clockwise %{"^" => ">", ">" => "v", "v" => "<", "<" => "^"}

  def update_position(pos, dir, cells) do
    {x, y} = pos
    {x_offset, y_offset} = @offsets[dir]
    new_pos = {x+x_offset, y+y_offset}
    case cells[new_pos] do
      "#" ->
        {pos, @clockwise[dir]}
      nil ->
        :out_of_bounds
      _ ->
        {new_pos, dir}
    end
  end
end

Part 2 Solution

To speed things up a bit, I’ve used the set of visited cell positions as input for part 2. This works because part 2 only requires changing a single cell at a time, and one that the “guard” will traverse.

While I’ve re-used the same business logic that solved part 1, the reduce_while code is undoubtedly more complex to account for the task of determining whether the traversal is cyclic — whether there’s a loop. In this case, both the direction and position need to be stored in the set because a cycle only occurs when the same position and direction are encountered twice.

loop_count = visited
|> Enum.map(fn pos -> cells |> Map.put(pos, "#") end)
|> Enum.map(fn updated_cells ->
  Stream.iterate(0, & &1 + 1)
  |> Enum.reduce_while(
  {start_pos, start_dir, MapSet.new([{start_pos, start_dir}])},
  fn _i, {pos, dir, visited} ->
    case Gallivant.update_position(pos, dir, updated_cells) do
      {new_pos, new_dir} -> 
        if MapSet.member?(visited, {new_pos, new_dir}) do
          {:halt, :loop}
        else
          {:cont, {new_pos, new_dir, visited |> MapSet.put({new_pos, new_dir})}}
        end
      :out_of_bounds ->
        {:halt, :no_loop}
    end
  end)
end)
|> Enum.filter(fn result -> result == :loop end)
|> Enum.count

IO.puts("Part 2 result: #{loop_count}")

Conclusion

Hopefully, this little foray into my recreational coding was interesting.

I certainly find Advent of Code valuable, because it gives me exposure to “computer science” coding-interview-style problems I wouldn't otherwise get. Many of the problems I encounter in my day-to-day work are with databases, cloud infrastructure and large and old codebases; the fine algorithmic details that AoC focuses on have already been dealt with by many of the tools I use.