Advent of Code 2024 - Day 6

Basically the same. Parallelized Part 2.

https://github.com/Aetherus/advent-of-code/blob/6e828436847c1ee6e9f5ab1848af4b652c3d5155/2024/day-06.livemd

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

This one was weird for me personally. I tried about four or five different approaches to solving the problem, totaling about 2.5 hrs, before I turned to here/Reddit for ideas. I was generated different answers and in the order of ten minutes per run. Once I saw the discussions about times going on here I started looking at the solutions here to figure out what was up. Strings. Strings were what was up.

I didn’t convert my board into a map at first (like @igorb does in his solution), and apparently this makes a difference. It reduced runtime from several minutes to 3.6s. I’m not really sure I understand why this is the case. Even stranger is that it also seems to have affected my answers, because immediately after I changed my code to convert the input to a map, I got the right answer. I don’t want to convert it back to the string version to sanity check that I didn’t change something else, because I don’t feel like waiting ten minutes for it to run.

Edit: And for a further optimization - I stole @bjorng’s :persistent_term trick to avoid copying the maze to each worker task. This reduced my runtime to ~700ms. I will share my code in the morning. It’s 3 a.m. EST .

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.

https://github.com/bjorng/advent-of-code/commit/152b2d284063f10f49e82aab749bd252e096d277

Your unoptimized version takes 0.9s to run on my computer, which beats my map-based solution (23s). Why Erlang maps are that slow?

I was trying to be smart until I found out I was not

So I ended up brute forcing as well. I’ll try to optimize it a bit if I have time tonight before posting it. Currently it’s like 6 seconds and it’s very ugly

And yes, I think you can just collect the floor that are faced during the initial walk for obstacle candidates.

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.

Used C for storing the grid like for day 4. Second part is slow because I test every possible obstacle position of the path taken in part 1. Using a Macbook Air M2 I get 1.5 ms for part 1 and 4.3 s for part 2.

Number of rows/cols: 130
Set up the grid in 4524 µs
Starting position of guard is (94,73)
Part 1. Number of positions: 5242. Job done in 1568 µs
Part 2. Number of obstacle positions: 1424. Job done in 4385926 µs

day06.exs:

#!/usr/bin/env elixir

# AoC 2024. day 6.

###########################################################
# Setup

%File.Stat{size: bytes} = File.stat!("../day06.txt")
# same number of rows and columns + 1 \n per row
size = trunc((-1 + :math.sqrt(1+4*bytes)) / 2) # positive solution of quadratic equation
IO.puts "Number of rows/cols: #{size}"

grid = Day06Array.new(size, size)
start = System.monotonic_time(:microsecond)
{row, col} = File.stream!("../day06.txt")
  |> Stream.with_index()
  |> Enum.reduce(nil, fn {line, row}, starting_pos ->
    line
    |> String.trim_trailing()
    |> String.to_charlist()
    |> Enum.with_index()
    |> Enum.reduce(starting_pos, fn {c, col}, starting_pos ->
      Day06Array.set(grid, row, col, c)
      if c == ?^, do: {row, col}, else: starting_pos
    end)
  end)
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Set up the grid in #{elapsed} µs"
IO.puts "Starting position of guard is (#{row},#{col})"

###########################################################
# Part 1

defmodule Part1 do
  def move_up(_grid, _size, 0, _col, positions), do: positions
  def move_up(grid, size, row, col, positions) do
    case Day06Array.get(grid, row-1, col) do
      ?# -> move_right(grid, size, row, col, positions)
      c when c in [?., ?^] -> move_up(grid, size, row-1, col, MapSet.put(positions, {row-1, col}))
    end
  end
  def move_right(_grid, size, _row, col, positions) when col == size-1, do: positions
  def move_right(grid, size, row, col, positions) do
    case Day06Array.get(grid, row, col+1) do
      ?# -> move_down(grid, size, row, col, positions)
      c when c in [?., ?^] -> move_right(grid, size, row, col+1, MapSet.put(positions, {row, col+1}))
    end
  end
  def move_down(_grid, size, row, _col, positions) when row == size-1, do: positions
  def move_down(grid, size, row, col, positions) do
    case Day06Array.get(grid, row+1, col) do
      ?# -> move_left(grid, size, row, col, positions)
      c when c in [?., ?^] -> move_down(grid, size, row+1, col, MapSet.put(positions, {row+1, col}))
    end
  end
  def move_left(_grid, _size, _row, 0, positions), do: positions
  def move_left(grid, size, row, col, positions) do
    case Day06Array.get(grid, row, col-1) do
      ?# -> move_up(grid, size, row, col, positions)
      c when c in [?., ?^] -> move_left(grid, size, row, col-1, MapSet.put(positions, {row, col-1}))
    end
  end
end

start = System.monotonic_time(:microsecond)
positions = Part1.move_up(grid, size, row, col, MapSet.new([{row,col}]))
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 1. Number of positions: #{MapSet.size(positions)}. Job done in #{elapsed} µs"

###########################################################
# Part 2

defmodule Part2 do
  def move_up(_grid, _size, 0, _col, _positions), do: false
  def move_up(grid, size, row, col, positions) do
    case Day06Array.get(grid, row-1, col) do
      ?# -> move_right(grid, size, row, col, positions)
      c when c in [?., ?^] ->
        if !MapSet.member?(positions, {row-1, col, :up}),
          do: move_up(grid, size, row-1, col, MapSet.put(positions, {row-1, col, :up})),
          else: true
    end
  end
  def move_right(_grid, size, _row, col, _positions) when col == size-1, do: false
  def move_right(grid, size, row, col, positions) do
    case Day06Array.get(grid, row, col+1) do
      ?# -> move_down(grid, size, row, col, positions)
      c when c in [?., ?^] ->
        if !MapSet.member?(positions, {row, col+1, :right}),
          do: move_right(grid, size, row, col+1, MapSet.put(positions, {row, col+1, :right})),
          else: true
    end
  end
  def move_down(_grid, size, row, _col, _positions) when row == size-1, do: false
  def move_down(grid, size, row, col, positions) do
    case Day06Array.get(grid, row+1, col) do
      ?# -> move_left(grid, size, row, col, positions)
      c when c in [?., ?^] ->
        if !MapSet.member?(positions, {row+1, col, :down}),
          do: move_down(grid, size, row+1, col, MapSet.put(positions, {row+1, col, :down})),
          else: true
    end
  end
  def move_left(_grid, _size, _row, 0, _positions), do: false
  def move_left(grid, size, row, col, positions) do
    case Day06Array.get(grid, row, col-1) do
      ?# -> move_up(grid, size, row, col, positions)
      c when c in [?., ?^] ->
        if !MapSet.member?(positions, {row, col-1, :left}),
          do: move_left(grid, size, row, col-1, MapSet.put(positions, {row, col-1, :left})),
          else: true
    end
  end

  def test_obstacles(_grid, _size, _start_row, _start_col, [], n), do: n
  def test_obstacles(grid, size, start_row, start_col, [{row,col} | positions_to_test], n) do
    Day06Array.set(grid, row, col, ?#)
    cycle = Part2.move_up(grid, size, start_row, start_col, MapSet.new([{start_row, start_col, :up}]))
    n = (if cycle, do: n+1, else: n)
    Day06Array.set(grid, row, col, ?.)
    test_obstacles(grid, size, start_row, start_col, positions_to_test, n)
  end
end

start = System.monotonic_time(:microsecond)
positions_to_test = positions |> MapSet.delete({row, col}) |> MapSet.to_list()
n = Part2.test_obstacles(grid, size, row, col, positions_to_test, 0)
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 2. Number of obstacle positions: #{n}. Job done in #{elapsed} µs"

day06_compile.sh:

#!/opt/homebrew/bin/bash

ERL_INCLUDE_PATH=/opt/homebrew/lib/erlang/usr/include

cc -fPIC -I $ERL_INCLUDE_PATH -dynamiclib -undefined dynamic_lookup -o day06_array.so day06_array.c
elixirc day06_array.ex

day06_array.ex:

defmodule Day06Array do
  @on_load :load_nifs

  def load_nifs do
    :erlang.load_nif(~c"./day06_array", 0)
  end

  def new(_size1, _size2) do
    raise "NIF new/2 not implemented"
  end

  def new(_size1, _size2, _value) do
    raise "NIF new/3 not implemented"
  end

  def get(_array, _index1, _index2) do
    raise "NIF get/3 not implemented"
  end

  def set(_array, _index1, _index2, _value) do
    raise "NIF set/4 not implemented"
  end
end

day06_array.c:

#include "erl_nif.h"
#include <limits.h>

ErlNifResourceType* RES_TYPE;

typedef struct {
  int* array;
  unsigned int size1;
  unsigned int size2;
} array_t;

void array_destructor(ErlNifEnv* env, void* res) { free(((array_t*)res)->array); }

int load(ErlNifEnv* env, void** priv_data, ERL_NIF_TERM load_info) {
  int flags = ERL_NIF_RT_CREATE | ERL_NIF_RT_TAKEOVER;
  RES_TYPE = enif_open_resource_type(env, NULL, "day06_array", array_destructor, flags, NULL);
  if (RES_TYPE == NULL) return -1;
  return 0;
}

static ERL_NIF_TERM new(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
  if (argc != 2) return enif_make_badarg(env);

  unsigned int size1, size2;
  if (!enif_get_uint(env, argv[0], &size1)) return enif_make_badarg(env);
  if (!enif_get_uint(env, argv[1], &size2)) return enif_make_badarg(env);

  array_t* res = enif_alloc_resource(RES_TYPE, sizeof(array_t));

  res->size1 = size1;
  res->size2 = size2;
  res->array = malloc(size1*size2*sizeof(int));
  if (res->array == NULL) return enif_make_badarg(env);

  ERL_NIF_TERM term = enif_make_resource(env, res);
  enif_release_resource(res);

  return term;
}

static ERL_NIF_TERM get(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
  if (argc != 3) return enif_make_badarg(env);
  unsigned int idx1, idx2;
  if (!enif_get_uint(env, argv[1], &idx1)) return enif_make_badarg(env);
  if (!enif_get_uint(env, argv[2], &idx2)) return enif_make_badarg(env);
  array_t* res;
  if (!enif_get_resource(env, argv[0], RES_TYPE, (void**) &res)) return enif_make_badarg(env);
  if (idx1 < 0 || idx1 >= res->size1 || idx2 < 0 || idx2 >= res->size2 ) return enif_make_badarg(env);
  return enif_make_int(env, *(res->array + idx1*res->size2 + idx2));
}

static ERL_NIF_TERM set(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) {
  if (argc != 4) return enif_make_badarg(env);
  unsigned int idx1, idx2;
  if (!enif_get_uint(env, argv[1], &idx1)) return enif_make_badarg(env);
  if (!enif_get_uint(env, argv[2], &idx2)) return enif_make_badarg(env);
  int value;
  if (!enif_get_int(env, argv[3], &value)) return enif_make_badarg(env);
  array_t* res;
  if (!enif_get_resource(env, argv[0], RES_TYPE, (void**) &res)) return enif_make_badarg(env);
  if (idx1 < 0 || idx1 >= res->size1 || idx2 < 0 || idx2 >= res->size2 ) return enif_make_badarg(env);
  *(res->array + idx1*res->size2 + idx2) = value;
  return argv[0];
}

static ErlNifFunc nif_funcs[] =
{
  {"new", 2, new},
  {"new", 3, new},
  {"get", 3, get},
  {"set", 4, set}
};

ERL_NIF_INIT(Elixir.Day06Array, nif_funcs, load, NULL, NULL, NULL);

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

https://github.com/sevenseacat/advent_of_code/blob/main/lib/y2024/day06.ex

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

I improved the running time with Task.async_stream/3 like @bjorng did. Going from +4s to 1.1s. But that means I had to give up setting the obstacle in the C array since multiple processes were going to use different obstacles and the C array is shared. Thus I added two arguments to my functions.

Part 2 bis. Number of obstacle positions: 1424. Job done in 1173602 µs

###########################################################
# Part 2 bis

defmodule Part2Bis do
  def move_up(_grid, _size, 0, _col, _positions, _obs_row, _obs_col), do: false
  def move_up(grid, size, row, col, positions, obs_row, obs_col) do
    object = Day06Array.get(grid, row-1, col)
    cond do
      object == ?# || (obs_row == row-1 && obs_col == col) ->
        move_right(grid, size, row, col, positions, obs_row, obs_col)
      !MapSet.member?(positions, {row-1, col, :up}) ->
        move_up(grid, size, row-1, col, MapSet.put(positions, {row-1, col, :up}), obs_row, obs_col)
      true -> true
    end
  end
  def move_right(_grid, size, _row, col, _positions, _obs_row, _obs_col) when col == size-1, do: false
  def move_right(grid, size, row, col, positions, obs_row, obs_col) do
    object = Day06Array.get(grid, row, col+1)
    cond do
      object == ?# || (obs_row == row && obs_col == col+1) ->
        move_down(grid, size, row, col, positions, obs_row, obs_col)
      !MapSet.member?(positions, {row, col+1, :right}) ->
        move_right(grid, size, row, col+1, MapSet.put(positions, {row, col+1, :right}), obs_row, obs_col)
      true -> true
    end
  end
  def move_down(_grid, size, row, _col, _positions, _obs_row, _obs_col) when row == size-1, do: false
  def move_down(grid, size, row, col, positions, obs_row, obs_col) do
    object = Day06Array.get(grid, row+1, col)
    cond do
      object == ?# || (obs_row == row+1 && obs_col == col) ->
        move_left(grid, size, row, col, positions, obs_row, obs_col)
      !MapSet.member?(positions, {row+1, col, :down}) ->
        move_down(grid, size, row+1, col, MapSet.put(positions, {row+1, col, :down}), obs_row, obs_col)
      true -> true
    end
  end
  def move_left(_grid, _size, _row, 0, _positions, _obs_row, _obs_col), do: false
  def move_left(grid, size, row, col, positions, obs_row, obs_col) do
    object = Day06Array.get(grid, row, col-1)
    cond do
      object == ?# || (obs_row == row && obs_col == col-1) ->
        move_up(grid, size, row, col, positions, obs_row, obs_col)
      !MapSet.member?(positions, {row, col-1, :left}) ->
        move_left(grid, size, row, col-1, MapSet.put(positions, {row, col-1, :left}), obs_row, obs_col)
      true -> true
    end
  end
end

start = System.monotonic_time(:microsecond)
positions_to_test = positions |> MapSet.delete({row, col}) |> MapSet.to_list()
stream = Task.async_stream(positions_to_test, fn {obs_row, obs_col} ->
  Part2Bis.move_up(grid, size, row, col, MapSet.new([{row, col, :up}]), obs_row, obs_col)
end)
n = Enum.reduce(stream, 0, fn {:ok, false}, n -> n ; {:ok, true}, n -> n+1 end)
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Part 2 bis. Number of obstacle positions: #{n}. Job done in #{elapsed} µs"