Advent of Code 2024 - Day 18

igorb · December 18, 2024, 6:11am

This puzzle was a nice break after the difficult Day 17! For part 2, I implemented a binary search to find the necessary coordinate faster, but considering the input size this was definitely not necessary. advent-of-code-2024/lib/advent_of_code2024/day18.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

bjorng · December 18, 2024, 7:06am

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.

github.com

bjorng/advent-of-code/blob/main/2024/day18/lib/day18.ex

defmodule Day18 do
  def part1(input, max \\ 70, n \\ 1024) do
    grid = parse(input)
    |> Enum.take(n)
    |> MapSet.new
    grid = {grid, 0..max}
    start = {0, 0}
    goal = {max, max}
    q = q_new({0, start})
    seen = MapSet.new([start])
    walk(q, goal, grid, seen)
  end

  def part2(input, max \\ 70, n \\ 1024) do
    {first, rest} = Enum.split(parse(input), n)
    grid = {MapSet.new(first), 0..max}
    start = {0, 0}
    goal = {max, max}
    q = q_new({0, start})
    seen = MapSet.new([start])

This file has been truncated. show original

lud · December 18, 2024, 9:47am

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.

github.com

lud/adventofcode/blob/main/lib/solutions/2024/day18.ex

defmodule AdventOfCode.Solutions.Y24.Day18 do
  alias AdventOfCode.BinarySearch
  alias AdventOfCode.Grid
  alias AoC.Input

  def parse(input, _part) do
    input |> Input.stream!(trim: true) |> Enum.map(&parse_line/1)
  end

  defp parse_line(line) do
    {x, "," <> rest} = Integer.parse(line)
    {y, ""} = Integer.parse(rest)
    {x, y}
  end

  def part_one(problem, coord_range \\ 0..70, prefall \\ 1024) do
    grid = problem |> Enum.take(prefall) |> Map.new(fn xy -> {xy, :wall} end)
    xstart..xend//1 = ystart..yend//1 = coord_range

    start = {xstart, ystart}

This file has been truncated. show original

liamcmitchell · December 18, 2024, 10:58am

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.

github.com

liamcmitchell/advent-of-code/blob/main/2024/18/1.exs

defmodule Day18 do
  def parse(file) do
    text = File.read!(Path.join(Path.dirname(__ENV__.file), file))

    for line <- String.split(text, "\n") do
      [x, y] = String.split(line, ",")
      {String.to_integer(x), String.to_integer(y)}
    end
  end

  def part1(file, size, bytes) do
    parse(file) |> Enum.slice(0, bytes) |> shortest(size)
  end

  def shortest(bytes, size) do
    map = MapSet.new(bytes)
    start = {0, 0}
    goal = {size, size}
    unvisited = :queue.from_list([{0, start}])
    seen = MapSet.new([start])

This file has been truncated. show original

rvnash · December 18, 2024, 2:50pm

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.

github.com

rvnash/aoc2024/blob/main/lib/d18.ex

defmodule D18 do
  @aoc_year "2024"
  @aoc_day __MODULE__ |> to_string() |> String.slice(-2..-1)
  # 0 is the file itself
  @content 0

  # Live content: 1024
  # Example: 12
  @drops 1024

  def read_input do
    content = %{
      0 => File.read!("./lib/#{@aoc_day}.txt"),
      1 => """
      5,4
      4,2
      4,5
      3,0
      2,1
      6,3

This file has been truncated. show original

Flo0807 · December 18, 2024, 3:16pm

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

github.com

Flo0807/adventofcode/blob/main/2024/18.livemd

# Advent of Code 2024 - Day 18

```elixir
Mix.install([
  {:req, "~> 0.5"},
  {:benchee, "~> 1.3"}
])
```

## Input

```elixir
opts = [headers: [{"cookie", "session=#{System.fetch_env!("LB_AOC_SESSION")}"}]]
puzzle_input = Req.get!("https://adventofcode.com/2024/day/18/input", opts).body
```

```elixir
# inclusive
width = 70
# inclusive

This file has been truncated. show original

rvnash · December 18, 2024, 3:46pm

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

lkuty · December 18, 2024, 4:07pm

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"

Sorc96 · December 18, 2024, 4:47pm

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.

sevenseacat · December 18, 2024, 6:02pm

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

github.com

sevenseacat/advent_of_code/blob/main/lib/y2024/day18.ex

defmodule Y2024.Day18 do
  use Advent.Day, no: 18

  alias Advent.PathGrid

  def part1(bytes, size \\ 70, byte_num \\ 1024) do
    empty_grid({0, 0}, {size, size})
    |> get_path(bytes, byte_num, size)
    |> length()
    |> Kernel.-(1)
  end

  def part2(bytes, size \\ 70) do
    max_bytes = length(bytes)
    empty_grid = empty_grid({0, 0}, {size, size})

    # Binary search this thing.
    {row, col} = run_binary_search(empty_grid, bytes, 0, max_bytes, size)
    "#{row},#{col}"
  end

This file has been truncated. show original

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

lkuty · December 19, 2024, 5:56am

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

Aetherus · December 19, 2024, 6:05am

You can create a directed graph by replacing all edges A <-> B with A -> B and B -> A.

lkuty · December 19, 2024, 6:22am

It still does not work. I am wondering if I will implement it in C and then call a NIF. In the very specific case of an undirected unweighted graph. But then, it is not 100% Elixir anymore Or maybe I implement it directly in Elixir

sevenseacat · December 19, 2024, 7:08am

Yeah undirected graphs in libgraph are a bit iffy. Directed graphs are fine though, I’ve used them a lot in Advent of Code - your code might have a bug in it somewhere.

edit: I think your logic of turning coordinates into integers with rc2i may be buggy - does it distinguish between say {20, 70} and {21, 0} ?

Also you’re only counting rows and cols up to 69 - the problem states the grid goes up to {70,70}, counting from zero.

lkuty · December 19, 2024, 7:36am

I multiply the row number by 71. Thus {20,70} gives 20 * 71+70=1490 and {21,0} gives 21 * 71=1491. I count only from 1 to 69 to avoid getting out of the grid and then I add manually the edges for the four corners ({0,0}, {0,70}, {70,0} and {70,70}). When I go from 1 to 69 for row and col, I add the edges to {row-1,col}, {row,col+1}, {row+1,col} and {row,col-1} to make connections to its four neighbors.
However there might still be a bug lurking somewhere.

sevenseacat · December 19, 2024, 7:43am

Yeah it sounds like its overcomplicating things for sure! Bugs lurk when there is overcomplication… This is why I stick to using {row, col} as my graph vertices, it also helps me print out grids to see errors

lkuty · December 19, 2024, 7:46am

Ha I thought it was quite simple If I don’t place any obstacles, A* finds a path from {0,0} to {70,70} which looks good: [{0, 0}, {0, 1}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {1, 10}, {1, 11}, {1, 12}, {1, 13}, {1, 14}, {1, 15}, {1, 16}, {1, 17}, {1, 18}, {1, 19}, {1, 20}, {1, 21}, {1, 22}, {1, 23}, {1, 24}, {1, 25}, {1, 26}, {1, 27}, {1, 28}, {1, 29}, {1, 30}, {1, 31}, {1, 32}, {1, 33}, {1, 34}, {1, 35}, {1, 36}, {1, 37}, {1, 38}, {1, 39}, {1, 40}, {1, 41}, {1, 42}, {1, 43}, {1, 44}, {1, 45}, {1, 46}, {1, 47}, {1, 48}, {1, 49}, {1, 50}, {1, 51}, {1, 52}, {1, 53}, {1, 54}, {1, 55}, {1, 56}, {1, 57}, {1, 58}, {1, 59}, {1, 60}, {1, 61}, {1, 62}, {1, 63}, {1, 64}, {1, 65}, {1, 66}, {1, 67}, {1, 68}, {1, 69}, {2, 69}, {3, 69}, {4, 69}, {5, 69}, {6, 69}, {7, 69}, {8, 69}, {9, 69}, {10, 69}, {11, 69}, {12, 69}, {13, 69}, {14, 69}, {15, 69}, {16, 69}, {17, 69}, {18, 69}, {19, 69}, {20, 69}, {21, 69}, {22, 69}, {23, 69}, {24, 69}, {25, 69}, {26, 69}, {27, 69}, {28, 69}, {29, 69}, {30, 69}, {31, 69}, {32, 69}, {33, 69}, {34, 69}, {35, 69}, {36, 69}, {37, 69}, {38, 69}, {39, 69}, {40, 69}, {41, 69}, {42, 69}, {43, 69}, {44, 69}, {45, 69}, {46, 69}, {47, 69}, {48, 69}, {49, 69}, {50, 69}, {51, 69}, {52, 69}, {53, 69}, {54, 69}, {55, 69}, {56, 69}, {57, 69}, {58, 69}, {59, 69}, {60, 69}, {61, 69}, {62, 69}, {63, 69}, {64, 69}, {65, 69}, {66, 69}, {67, 69}, {68, 69}, {69, 69}, {69, 70}, {70, 70}]

EDIT 1: Well I thought it would go diagonally from {0,0} to {70,70}. Doesn’t look like the shortest path.
EDIT 2: Anyway it should go horizontally from 0 to 70 and vertically from 0 to 70 thus it looks ok in the end Diagonally it would be the same moves.
EDIT 3: OK, I think I forgot to link some vertices together e.g. {0,10} to {0,11} I will fix the code.

lkuty · December 19, 2024, 7:48am

Then you’re using the default hash function of the vertex based on :erlang.phash2/2 ?

sevenseacat · December 19, 2024, 8:04am

No - that really doesn’t work with a lot of vertices in a grid. See: Duplicate vertex ids when adding high number of vertices · Issue #44 · bitwalker/libgraph · GitHub

Aetherus · December 19, 2024, 8:18am

I implemented my own priority queue with no duplicate values and lazy decrease-key operation.
Part 1 I used that priority queue to implement Dijkstra.
Part 2 I used a totally different approach. For each “byte” dropped down, I check if there are byte chunks horizontally, vertically, or diagonally adjacent to that “byte”, and merge those chunks with the new byte to form a larger chunk. Then I just need to find the first chunk over time that horizontally or vertically crosses the whole “memory space”.

Here’s my approach:

github.com

Aetherus/advent-of-code/blob/6988c7f5534adefd3a6781fadc23638e8d916f2f/2024/day-18.livemd

# Advent of Code 2024 - Day 18

```elixir
Mix.install([
  {:kino_aoc, "~> 0.1.7"}
])
```

## Section

<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIxOCIsInNlc3Npb25fc2VjcmV0IjoiQU9DX1NFU1NJT04iLCJ5ZWFyIjoiMjAyNCJ9","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->

```elixir
{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2024", "18", System.fetch_env!("LB_AOC_SESSION"))
```

```elixir
input =
  puzzle_input

This file has been truncated. show original