Advent of Code Day 6, in Elixir!

concurrent brute force > serial brute force

I did Day 6 in Elixir! (Previously: Day 1, Day 2, Day 3, Day 4, Day 5, all in Raku).

As usual, I won’t re-describe the puzzles: take a look on Advent of Code.

In this puzzle, both parts are pretty similar, so I’ll walk through my solution for both.

Before we get started, a few notes on Elixir:

• Elixir runs on the BEAM (the Erlang VM), and as such is excellent for distributed computing.¹
• It has pattern matching in functions. If the match does not succeed, it checks the next function definition, if any. If it exhausts all patterns and none of them match, we get an error.
• Elixir has a wonderfully simple syntax enhanced by a little bit of syntax sugar. If, like me, you are interested in langauge design, Elixir’s Syntax Reference is great reading.
• Elixir has a pipe operator |> that is used to pipe the expression on the left into the first argument of the function on the right. For example, set_of_things |> MapSet.put(thing) is equivalent to MapSet.put(set_of_things, thing).

Guards! Guards!

I defined a Guard module to move the guard and keep track of the guard position.

  defp next({gx, gy}, {dx, dy}), do: {gx + dx, gy + dy}
  defp turn({dx, dy}), do: {dy, -dx}
  defp in_bounds?({gx, gy}, {bx, by}), do: gx >= 0 and gy >= 0 and gx < bx and gy < by

I defined a few helpers. next gives the next guard location in the given direction. turn gives us the direction turned 90 degrees to the right. in_bounds?² tells us whether the guard is in the bounds of the map. The guard, the direction, and the upper bounds are all represented as 2-tuples.

  defp step(guard, dir, obstacles) do
    peek = next(guard, dir)
    if MapSet.member?(obstacles, peek) do
      step(guard, turn(dir), obstacles)
    else
      {peek, dir}
    end
  end

step moves the guard once. We check if the next location in the current direction is an obstacle; if so, we try stepping after turning. Otherwise, we return the new location and direction.

Note that Elixir doesn’t have loops, so we make heavy use of tail calls instead.

The walk/5 and walk/3 functions

  defp walk(guard, dir, obstacles, bounds, history) do
    cond do
      MapSet.member?(history, {guard, dir}) ->
        :loop
      in_bounds?(guard, bounds) ->
        history = MapSet.put(history, {guard, dir})
        {guard, dir} = step(guard, dir, obstacles)
        walk(guard, dir, obstacles, bounds, history)
      true ->
        locations =
          history
          |> Stream.map(fn {location, _} -> location end)
          |> Stream.uniq
        {:walked_out, locations}
    end

This is quite a large function. At first, the second branch in_bounds?(guard, bounds) is executed. In it, we add the guard’s position and direction to the set history, step, then call walk again.

This continues until the guard either:

• walks out of bounds (the third branch) at which point we return the atom :walked_out and just the locations (not the directions) from history, or
• the current guard position and direction are in our history (first branch), at which point we know we have started looping.

  def walk(guard, obstacles, bounds) do
    walk(guard, {-1, 0}, obstacles, bounds, MapSet.new)
  end

In Elixir, every function has a name and arity. So a function with 3 arguments is different from a function with the same name with 5 arguments, like here. These two functions are denoted walk/3 and walk/5 in the Elixir/Erlang world.

It’s easy to miss, but notice that this is the only function in the guard module that isn’t private (def vs defp).

Parsing the input (again)

Every day, I have to parse the input. It gets old after a while :) but at least we’re using a new language today so parsing is different!

floormap =
  File.stream!("data.txt")
  |> Enum.with_index
  |> Enum.map(fn {line, row} ->
    line
    |> String.to_charlist
    |> Enum.with_index
    |> Enum.map(fn {char, col} ->
      {{row, col}, char}
    end)
  end)

To construct floormap, we construct a 2D list of nested tuples {{row, col}, char}. We’ll flatten this after we get the bounds.

bounds_x = Enum.count(floormap)
bounds_y = floormap |> Enum.at(0) |> Enum.count
bounds = {bounds_x, bounds_y}

Pretty straightforward (and similar to previous days). We count the number of lines, and the number of characters in the first line.

floormap = Enum.concat(floormap)

Here we flatten the floormap, as promised!

obstacles =
  floormap
  |> Enum.filter(fn {_, char} -> char == ?# end)
  |> Enum.map(fn {pos, _} -> pos end)
  |> MapSet.new

Here, we filter the floormap for the ’#’ char. ?# is the syntax for getting the codepoint of a character, and our floormap actually contains the codepoints, not the characters. Then we make a set from the obstacle positions. This makes looking up whether a position has an obstacle quicker.

guard = floormap |> Enum.find(fn {_, char} -> char == ?^ end) |> elem(0)

Very similar to the obstacles. This time we use elem(0) to get the first element of the tuple (the position).

Putting it all together

Part 1

{:walked_out, locations} = Guard.walk(guard, obstacles, bounds)
locations |> Enum.count |> IO.inspect(label: "length of path (part 1)")

Here, we get the locations from the first pass around. We know that the guard will walk out, so we don’t need to pattern-match against the possibility that Guard.walk will return the atom :loop.

IO.inspect is a pretty cool function. It prints its argument and returns it, which means that, while debugging, you can just insert an IO.inspect into any pipeline.

Part 2

The solution for this part is just brute-force. We add an obstacle to each spot in locations; if walk/3 returns :loop for this new set of obstacles, then we count it.

Because this is Elixir, we can spawn one task for each check. However, our obstacles set is pretty big (I had around 800 obstacles in my input). That means that every task would have to copy the obstacles set… seems inefficient³.

We can use the :persistent_term module to avoid this copy. From the documentation:

it provides a storage for Erlang terms that can be accessed in constant time […] persistent_term has been highly optimized for reading terms at the expense of writing and updating terms.

That’s basically what we want, since we’re not going to be (globally) updating the set.

Let’s use it (we use the atom :obstacles as the key, because why not):

:persistent_term.put(:obstacles, obstacles)

Now we can brute-force:

locations
|> Task.async_stream(fn location ->
  obstacles = :persistent_term.get(:obstacles) |> MapSet.put(location)
  Guard.walk(guard, obstacles, bounds)
end, ordered: false)
|> Stream.filter(&match?({:ok, :loop}, &1))
|> Enum.count
|> IO.inspect(label: "obstacle positions causing loops (part 2)")

For each location, we spawn a Task that adds the location to the (task-local) set of obstacles, then walks the new floormap. We don’t need results to be in order.

We then count only the lines that match {:ok, :loop}. The & here is syntax sugar for writing a closure: the syntax above, &match?({:ok, :loop}, &1) is equivalent to fn arg -> match?({:ok, :loop}, arg).

And that’s it for Day 6!

Day 7 looks like more brute force, so we will probably use Elixir again.