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.

https://github.com/bjorng/advent-of-code/blob/main/2024/day06/lib/day06.ex