No, it is the call byte_size_remaining_at(string, position) in do_at/2 for calculating the number of bytes to the left of the character to be extracted that makes it slower.

This is calculation is necessary to correctly handle Unicode characters in the string, since the size of each code point varies from one to four bytes. For example, emoji characters are four bytes, and in order to skip over two emoji characters in the following example, it is necessary to skip over eight bytes:

iex> String.at("😀😃😎🥸", 2)
"😎"

If a string is known to only contain US ASCII characters (as is the case for all text from the Advent of Code web site), the faster :binary.at/2 BIF can safely be used instead of String.at/2. That will usually be slightly faster than using a map.

Is that really 23 seconds? Or did you mis-type 2.3 seconds?

If I paste all of your code into a function (not using LiveBook), it runs in 1.5 seconds on my computer, compared to 0.2 seconds for my fastest version.

I managed to reduce the runtime of your version to 1.1 seconds by doing the following changes:

           obstacles = MapSet.put(obstacles, new_obstacle)
 
+         tid = :ets.new(:seen, [:private])
+
          {guard, {-1, 0}}
          |> Stream.iterate(fn {{i, j}, {di, dj}} ->
-           if {i + di, j + dj} in obstacles do
+           if MapSet.member?(obstacles, {i + di, j + dj}) do
              {{i, j}, {dj, -di}}
            else
              {{i + di, j + dj}, {di, dj}}
            end
          end)
-         |> Enum.reduce_while(MapSet.new(), fn {{i, j}, _dir} = state, seen ->
+         |> Enum.reduce_while(tid, fn {{i, j}, _dir} = state, tid ->
            cond do
              i == 0 -> {:halt, 0}
              i > imax -> {:halt, 0}
              j == 0 -> {:halt, 0}
              j > jmax -> {:halt, 0}
-             state in seen -> {:halt, 1}
-             true -> {:cont, MapSet.put(seen, state)}
+             :ets.member(tid, state) -> {:halt, 1}
+             true ->
+               :ets.insert(tid, {state})
+               {:cont, tid}
            end
          end)
        end, ordered: false)

That is, I used an ETS table instead of a MapSet. That reduced the time by 0.3 seconds. Replacing in with MapSet.member?/2 reduced the time with another 0.1 seconds.

I would not say that maps are slow. What is happening when constantly adding new terms to a map is that the process heap frequently needs to grow. The way to grow the heap is by doing a garbage collection, which will need to copy all live data.

ETS tables are stored outside the process heaps, so adding an entry to an ETS table will not cause a garbage collection. That can make ETS tables more performant, depending on the size of the data and how frequently it is updated. The disadvantage of using an ETS table is that they are not functional data structures. I personally avoid ETS table unless they will give me a substantial performance gain.

I solved part 2 by brute force, that is by putting an obstacle on every free square and test whether that forced a loop.

My initial approach to finding a cycle was counting steps and consider it a loop if the number of steps exceeded twice the number of squares. That worked but the runtime was a little bit more than 5 seconds.

When the runtime exceeds one second, I usually start looking for possible optimizations.

My first approach was to lower the limit for the number steps. Using the number of squares worked but only reduced the time to about 4.5 seconds. While I still think that limit is safe, I still felt a little bit uneasy for doing that.

Next I looked at cycle detection algorithms. Floyd’s algorithm was a little bit slower than my previous solution. Brent’s algorithm was about as fast as my previous solution.

Having found an algoritm that should work for all possible grids, I used Task.async_stream/3 to parallelize the search. My first attempt was almost three times slower at about 12 seconds. The reason for the slowdown was the copying of the map holding the contents of each square to each spawned process. I then put the input into a persistent term to eliminate the copying.

That reduced the runtime to about 1 second.

Run on an M1 MacBook Pro with 8 cores.

Looking at @igorb’s solution, I realized that I had missed a fairly obvious optimization, namely putting obstacles only in the path actually walked by the guard.

Adding this optimization reduces the runtime to 0.2 seconds.

This was a fun one! The first one that really benefited from some optimization. My solution for part 2 runs in about 850ms.

Main points:

• Parse the input into a list of “wall” (obstacle) coordinates, the guard coordinate, and the size of the grid (to know when we leave the grid)
• Plot the initial path the guard takes in a naive way - step, check, maybe turn, etc. to build up a list
• For each point in the initial, stick an obstacle there, replot the path, and see if it now makes a loop. Keep track of all (coordinate + direction) combos when building a path, a revisited value means we have a loop

I had a few iterations -

• First iteration - used my PathGrid module that used a graph to keep track of possible paths/walls/etc. Way too much unnecessary overhead. It worked, but it took a minute.
• Second iteration - used my Grid module that uses a map to keep track of what’s stored at each coordinate in the grid. Also worked, but there’s so many floor spaces that we don’t care about that made a massive map. It took about 3.6 seconds.
• Third iteration - keeping only the wall coordinates in a much smaller map. This is this solution