Today is a brute-force day: advent-of-code-2024/lib/advent_of_code2024/day6.ex at main · ibarakaiev/advent-of-code-2024 · GitHub
Takes around 15 seconds to solve my input.
2 Likes
Basically the same. Parallelized Part 2.
2 Likes
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.
3 Likes
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 
.
2 Likes
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.
3 Likes
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.
1 Like
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.
4 Likes
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.
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
3 Likes
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"
1 Like
My first defeat.
I implemented part 2 by doing this:
- Keep track of all visited spaces and the direction.
- For each step, look right and check if we would join any previously visited path in the same direction
It works on the sample input, but says it’s too low on the real one. Must be a bug somewhere, but time’s up.
1 Like
“Look right”?
Yes, the guard only turns right. So my thinking is if there is already a travelled path to the right of the current position, putting a boulder immediately ahead will create a cycle.
From the sample:
....#.....
....+---+#
....|...|.
..#.|...|.
....|..#|.
....|...|.
.#.O^---+.
........#.
#.........
......#...
When we “look right” after reaching the start position a 2nd time, we see the already travelled path in the same direction, put obstacle.
edit:
I think I forgot to account for cases where the guard could walk backwards along the same path: like this:
.#.
->#
#..
.O.
Anyway…
finally got time to complete Part1 <3
its pretty simple to do, IF you have the hunch early to create a tile formatter … which I didn’t and made much later than I should have … this can easily display the grid back in the terminal … much easier to see offset errors
1 Like
Hey there, I completed Part 1 & 2, but I’m not proud of my code 
so I keep it for myself 
Part2 runs in 3.5 sec, with Task.async_stream 
1 Like
Haha. One thing ive learned in 16 years as developer. Never keep things for your self. Always something to learn, and some «bad code» can even look good to others 
but good job. I almost never think about speed. Unless i see its slow
1 Like
3 Likes
impressive cod … I mean cuP <3 but seriously i see no issues with code 
how is this Mac mini going btw. and m1 model ? niiice clean desktop (for the picture I guess)
now ill shut up with the Segways
1 Like
I’m weird. My desktop is always clean and tidy, otherwise I can’t work.
It’s a Mac Studio I bought almost 3 years ago, still so powerful I think I will keep it for years
1 Like
