igorb

igorb

Advent of Code 2024 - Day 6

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.

Most Liked

bjorng

bjorng

Erlang Core Team

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.

bjorng

bjorng

Erlang Core Team

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.

bjorng

bjorng

Erlang Core Team

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

Where Next?

Popular in Challenges Top

sb8244
Note: This topic is to talk about Day 10 of the Advent of Code 2019 . There is a private leaderboard for elixirforum members. You can jo...
New
Aetherus
Today’s problem is really tense. I don’t think I can do it without libgraph.
New
gangstead
This is my second year doing AoC in Elixir and my first year doing it with Livebook. When I was doing just plain Elixir I usually set up...
New
Aetherus
This topic is about Day 15 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/l...
New
shritesh
I mapped both the cards and every possible hand to numeric values and sorted them. In part 2 I could only think of replacing the jokers w...
New
New
bjorng
My solution finishes both parts in 5 seconds on my computer. That time should be possible to reduce by optimizing my rather naive tilt/2 ...
New
seeplusplus
Hello all, hopefully I post this before someone else does and I don’t dupe. IMO Day 4 was much easier than Day 3 (yay, I can sleep befor...
New
New
rvnash
Anyone have a solution to Part 2 today? Part 1 was straight forward, but I can’t figure out a programatic way to do part 2. I understand ...
New

Other popular topics Top

aadeshere1
I have a another noob question about loop. Since elixir is immutable, while loop is not directly possible. total = 10 while total != 0 ...
New
chrismccord
Phoenix 1.4.0 released Phoenix 1.4 is out! This release ships with exciting new features, most notably with HTTP2 support, improved deve...
688 31013 112
New
minhajuddin
I have seen a lot of code which picks the first element from a list using Enum.at(0) instead of List.first. Is there a reason why people ...
New
stefanchrobot
What’s the safe way to decode a JSON string into a struct? I want to avoid calling String.to_atom. Jason.decode can give me a map with st...
New
jay1
Why is it that the mnesia database isn’t the most preferred database for use in Elixir/Phoenix?
New
joeerl
Hello again - after a longish gap I’ve decided I really must dig into Elixir and see what’s been happening here - so I have a few questio...
New
RisingFromAshes
I’ve read in another post that it may be possible with a router helper - but I couldn’t find an appropriate one, and tbh, I’m still just ...
New
sergio_101
I am VERY much an elixir newbie. I have taken one elixir course and one phoenix course on Udemy. During that course, I saw the instructor...
New
KronicDeth
Elixir plugin for JetBrain’s IntelliJ Platform (including Rubymine) This is a plugin that adds support for Elixir to JetBrains IntelliJ...
289 36352 110
New
shijith.k
I am trying to start a new phoenix project with elixir 1.9, but mix phx.new does not work. It says that ** (Mix) The task "phx.new" could...
New

Latest on Elixir Forum

Elixir Forum

We're in Beta

About us Mission Statement