Advent of Code 2024 - Day 18

Yes!

Having quickly solved both parts, I had time to experiment with different ways of managing the queue. My initial implementation used gb_sets; I ended up using queue.

The combined runtime for both parts is 4.5 seconds.

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

Same here, solved easily, the brute force took something like 6 seconds.

Then I used binary search:

• First drop 1024 items from the walls points
• Create a base grid (with grid module) with those 1024 walls
• Then do a binary search for n between 1 and length(rest_of_walls). For each try:
  • take with Enum.take(rest_of_walls, n) and add those walls to the grid.
  • return “search reasult is greater” if the path is possible
  • return “…is lower” if the path is not possible

Of course there is no answer for “search result is equal” so I had to modify my binary search algorithm to detect ties and return them.

Part two is 13ms on my machine.

https://github.com/lud/adventofcode/blob/main/lib/solutions/2024/day18.ex

I thought that was long until I saw you are brute forcing part 2, no binary search.

I timed my first implementation without binary search and got 213 seconds (2013 MBP). Switched the pathfinding to use :queue like yours and got 42 seconds so much faster. Re-added binary search and it’s now 3 seconds including compilation.

https://github.com/liamcmitchell/advent-of-code/blob/main/2024/18/1.exs

Part 1 I solved using a simplified version of the path finding algorithm from Day 16.

Part 2: I guess there is probably some way to trim all possible paths as the bytes fall and cut them off, until the link to the end is severed. But I just brute forced it, checking all bytes sequentially until it failed to find a path, and it finished in 4.5 seconds.

https://github.com/rvnash/aoc2024/blob/main/lib/d18.ex

My solution. I used Erlang’s queue data type for part 1. For part 2, I implemented a binary search, too.

https://github.com/Flo0807/adventofcode/blob/main/2024/18.livemd

Ok, switched mine to using a binary search instead of brute force, and times dropped to the ms range. Thanks for the idea.

Part 1: 268 in 2.246ms
Part 2: 64,11 in 8.696ms

For part 1, I thought I will use libgraph and A*. But the code below does not find a path. I cannot figure out what is the problem here. I could solve it differently but I liked the idea of using a graph library, mentioned previously by @Aetherus I think.

#!/usr/bin/env elixir

# AoC 2024. day 18.

Mix.install([
  {:libgraph, "~> 0.16.0"}
])

defmodule M do
  @size 71
  def divrem(x, y), do: {div(x, y), rem(x, y)}
  def rc2i(row, col), do: row*@size+col
  def i2rc(i), do: ({r,c}=divrem(i,@size) ; {r,c})
end

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

start = System.monotonic_time(:microsecond)

g = for row <- 1..69, col <- 1..69, reduce: Graph.new(type: :undirected, vertex_identifier: &Function.identity/1) do
  g -> (g |> Graph.add_edge(M.rc2i(row,col),M.rc2i(row-1,col)) |> Graph.add_edge(M.rc2i(row,col),M.rc2i(row,col+1)) |> Graph.add_edge(M.rc2i(row,col),M.rc2i(row+1,col)) |> Graph.add_edge(M.rc2i(row,col),M.rc2i(row,col-1)))
end
|> Graph.add_edge(M.rc2i(0,0), M.rc2i(1,0)) |> Graph.add_edge(M.rc2i(0,0), M.rc2i(0,1))
|> Graph.add_edge(M.rc2i(70,0), M.rc2i(69,0)) |> Graph.add_edge(M.rc2i(70,0), M.rc2i(70,1))
|> Graph.add_edge(M.rc2i(0,70), M.rc2i(0,69)) |> Graph.add_edge(M.rc2i(0,70), M.rc2i(1,70))
|> Graph.add_edge(M.rc2i(70,70), M.rc2i(69,70)) |> Graph.add_edge(M.rc2i(70,70), M.rc2i(70,69))
|> IO.inspect(label: "graph")

# Graph.vertices(g) |> Enum.sort() |> Enum.map(&M.i2rc/1) |> IO.inspect(label: "vertices")
# Graph.edges(g) |> Enum.map(fn %{v1: v1, v2: v2} -> {M.i2rc(v1), M.i2rc(v2)} end) |> Enum.sort() |> Enum.map(fn {{r1,c1},{r2,c2}} -> "(#{r1},#{c1}) - (#{r2},#{c2})" end) |> IO.inspect(label: "edges")

File.stream!("../day18.txt")
|> Stream.map(fn line ->
  case Regex.run(~r/^(\d+),(\d+)$/, line, capture: :all_but_first) do
    [row,col] -> {String.to_integer(row), String.to_integer(col)}
  end
end)
|> Stream.take(1024)
|> Enum.reduce(g, fn {row, col}, g -> Graph.delete_vertex(g, M.rc2i(row,col)) end)
# |> Graph.Pathfinding.a_star(M.rc2i(0,0), M.rc2i(70,70), fn _vertex -> 0 end)
|> Graph.Pathfinding.dijkstra(M.rc2i(0,0), M.rc2i(70,70))
|> IO.inspect(label: "Part 1")

elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

I used libgraph for a challenge back in 2021 thinking I would be done with it quickly instead of implementing a custom algorithm. There was an issue with a hashing function for nodes creating a lot of collisions, so while the example worked fine, the graph for the actual input was missing a few nodes.

There was a fix that allowed for a custom hashing function to be supplied, but the old one was still hardcoded in one place. So I ended up spending a lot of time figuring this out and patching the local copy of libgraph to use my “hashing” function, which was really just the identity function.

I don’t know if this problem is still present, but I recommend checking whether the number of nodes in your graph seems correct.

Man, this was a nice change of pace from yesterday.

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

This builds up an empty graph of the correct size with edges pointing back and forth between coordinates, and then adds “walls” for the falling bytes.

Part 1 is pretty straightforward - add 1024 walls, get the shortest path.

Part 2 uses a binary search over the length of the byte list to see where the first error happens. There’s probably still room for optimization there, but I’m happy enough with it.

Name                     ips        average  deviation         median         99th %
day 18, part 1         22.53       44.38 ms     ±5.11%       44.48 ms       48.54 ms
day 18, part 2          4.04      247.58 ms     ±3.18%      247.68 ms      260.90 ms

It looks like there is a problem with path finding in general with undirected graphs. get_shortest_path doesn't work correctly on undirected graphs · Issue #37 · bitwalker/libgraph · GitHub and Incorrect A* pathfinding with undirected graph · Issue #11 · bitwalker/libgraph · GitHub