Advent of Code 2023 - Day 10

I spent most of the time struggling with basic bugs in the flood fill routine. I would have saved a lot of time if I had implemented a routine to print out the pipes sooner rather than later.

My solution:

https://github.com/bjorng/advent-of-code-2023/blob/main/day10/lib/day10.ex

Lost so much time with a wrong algorithm for part 1 …

And same for part 2

Anyway, it takes 200ms on average, so I am satisfied, but I feel it could be better.

https://github.com/lud/adventofcode/blob/main/lib/solutions/2023/day10.ex

My solution, runs in 8-10 ms: advent-of-code-2023/lib/advent_of_code/day_10.ex at main · ibarakaiev/advent-of-code-2023 · GitHub

The logic is as follows (spoilers incoming):

1. Find S
2. Choose an adjacent point to start with, since we don’t know what S is, based on whether it’s connected to S (note: I suppose there could be an edge case where one has “-” on left and right and “|” on top and bottom, in which case it might choose the wrong one, but it worked fine on my input and all examples).
3. Iterate through the loop based on where a symbol could lead, until you reach S.

For part 1, just calculate how many steps it took to reach S again and divide by 2.

Part 2 was obviously a lot trickier, so I did the following:

1. Same steps as above, but while iterating I was saving what symbols are actually part of the loop, and the rest I filled with “.”. At the last step, I could also now infer what S actually is based on the starting point I chose and the last step before S. Using immutable data structures here felt very wasteful, because a) for lists, we would have to iterate through each element each time since it’s a linked list b) for tuples, lookup is faster, but filling in the symbols on an empty canvas requires to copy the entire 2D array each time. I ended up choosing tuples because I hypothesized that fast lookups and memory colocation would speed up things, but I don’t have any evidence to back up this claim. Having a mutable 2D array here would certainly speed up things.
2. Once we have a “cleaned up” version (the only symbols present are part of the loop and and S is replaced with its actual value), we can cast a horizontal ray for each row and at each step maintain three variables: how many inner points we found so far, are we inside the loop or outside, and what was the previous “opener”. With these three variables, depending on the symbol, you can infer whether you’re at an inner point or not.

The “opener” part was the tricky part for me to figure out: suppose you start from outside and you find “L-J”, then at the end of it you end up outside again. However, if you find “L-7” then you end up inside. If you find “|” then it’s just trivially flipping the value of whether you’re inside or outside.

I did the exact same horizontal casting ray for part 2. Where it is slow is because I used the map as if the symbols could be wrong. Like if you could see -|, and just the loop would be correct.

When I understood all the pipes are properly connected I refactored a bit but it was too late to change everything.

But now you make me want to fix it XD

For part 2, I added a space between every existing space in the grid and filled it in with either an empty space or a path segment. Then I did a flood fill from the top-left and counted the even coordinates that weren’t discovered.

defmodule Part1 do
  def parse(input) do
    lines = String.split(input, "\n", trim: true)
    height = length(lines)
    width = String.length(hd(lines))
    padding = String.duplicate(".", width)
    lines = ([padding] ++ lines ++ [padding]) |> Enum.map(&("." <> &1 <> "."))

    map =
      for {line, y} <- Enum.with_index(lines),
          {char, x} <- line |> String.graphemes() |> Enum.with_index(),
          into: %{} do
        {{y, x}, char}
      end

    {map, {height + 2, width + 2}}
  end

  @connections %{
    "S" => [{-1, 0}, {1, 0}, {0, -1}, {0, 1}],
    "|" => [{-1, 0}, {1, 0}],
    "-" => [{0, -1}, {0, 1}],
    "L" => [{-1, 0}, {0, 1}],
    "J" => [{-1, 0}, {0, -1}],
    "7" => [{1, 0}, {0, -1}],
    "F" => [{1, 0}, {0, 1}],
    "." => []
  }

  def loop(pipes) do
    {{y, x} = start, _} = Enum.find(pipes, fn {_, char} -> char == "S" end)

    {dy, dx} =
      delta =
      Enum.find(@connections[pipes[start]], fn {dy, dx} ->
        {-dy, -dx} in @connections[pipes[{y + dy, x + dx}]]
      end)

    loop(pipes, start, {y + dy, x + dx}, delta, [start])
  end

  def loop(_, start, curr, _, path) when start == curr, do: Enum.reverse(path)

  def loop(pipes, start, {y, x} = curr, {dy0, dx0}, path) do
    [{dy1, dx1} = delta] = @connections[pipes[curr]] -- [{-dy0, -dx0}]
    loop(pipes, start, {y + dy1, x + dx1}, delta, [curr | path])
  end
end

{map, _} = Part1.parse(input)
map |> Part1.loop() |> length() |> div(2)

defmodule Part2 do
  def enhance(map, {height, width}, path) do
    map =
      map
      |> Enum.flat_map(fn {{y0, x0}, c} ->
        {y1, x1} = {2 * y0, 2 * x0}

        [
          {{y1, x1}, c},
          {{y1 - 1, x1}, "."},
          {{y1 - 1, x1 - 1}, "."},
          {{y1, x1 - 1}, "."}
        ]
        |> Enum.filter(fn {{y1, x1}, _} -> y1 >= 0 and x1 >= 0 end)
      end)
      |> Map.new()

    {path, map} =
      path
      |> Enum.chunk_every(2, 1, Enum.take(path, 1))
      |> Enum.flat_map_reduce(map, fn [{y0, x0}, {y1, x1}], acc ->
        {dy, dx} = {y1 - y0, x1 - x0}
        {y2, x2} = {2 * y0, 2 * x0}
        gap = {y2 + dy, x2 + dx}
        char = if abs(dy) == 1, do: "|", else: "-"
        acc = %{acc | gap => char}

        {[{y2, x2}, gap], acc}
      end)

    {map, {2 * height - 1, 2 * width - 1}, path}
  end

  def fill(map, size, path) do
    path = MapSet.new(path)
    frontier = [{0, 0}]
    explored = MapSet.new(frontier) |> MapSet.union(path)
    fill(map, size, frontier, explored)
  end

  defp fill(_, _, [], explored), do: explored

  defp fill(map, {height, width} = size, [{y0, x0} | rest], explored) do
    neighbors =
      [{y0 - 1, x0}, {y0, x0 - 1}, {y0 + 1, x0}, {y0, x0 + 1}]
      |> Enum.filter(fn {y1, x1} = coord ->
        y1 >= 0 and
          y1 < height and
          x1 >= 0 and
          x1 < width and
          not MapSet.member?(explored, coord)
      end)

    frontier = neighbors ++ rest
    explored = MapSet.new(neighbors) |> MapSet.union(explored)
    fill(map, size, frontier, explored)
  end
end

{map, size} = Part1.parse(input)
path = Part1.loop(map)
{map, size, path} = Part2.enhance(map, size, path)

outside = Part2.fill(map, size, path)

map
|> Map.keys()
|> MapSet.new()
|> MapSet.difference(outside)
|> Enum.filter(fn {y, x} -> rem(y, 2) == 0 and rem(x, 2) == 0 end)
|> length()

EDIT: For part 1, I also remembered the Kernel.--/2 trick from earlier this month.

EDITEDIT: Part 2 took 0.1 seconds according to Livebook.

Alright so now that I know that the pipes connections are always valid, I can just select one and go straight for the answers.

This is much more clear and indeed runs in 10ms (11 on my machine )

https://github.com/lud/adventofcode/blob/main/lib/solutions/2023/day10.ex

@midouest Nice one ! Expanding the map is fun

Nice, very clean! And I like how others approach it with a flood fill, which I learned about thanks to their solutions.

My beginner’s solution, Day 10 part 1. Pipe Maze

My first attempt was a mess so I decided to start from scratch using :digraph module.
I already attempted to use it in a previous day (forgot which one lol) until I realized a handcrafted solution would be more straightforward.
This time it felt very suited for the part 1 of the problem.
It was very satisfying to seamlessly integrate Erlang Standard Library successfully.

defmodule Day10 do

  def part1(input) do
    digraph = process(input)
    [starting_position] = :digraph_utils.loop_vertices(digraph)
    :digraph.del_path(digraph, starting_position, starting_position)
    for vertix <- :digraph.in_neighbours(digraph, starting_position) do
      :digraph.add_edge(digraph, starting_position, vertix)
    end
    :digraph_utils.reachable_neighbours([starting_position], digraph)
    |> length
    |> then(&floor(&1/2))    
  end

  def process(raw_sketch) do
    raw_lines = raw_sketch
      |> String.split("\n")
    
    height = raw_lines
      |> Enum.count

    width = raw_lines
      |> List.first
      |> String.length
    
    digraph = :digraph.new 

    for h <- 0..height+1, w <- 0..width+1 do
      :digraph.add_vertex(digraph, {h, w})
    end 

    for {raw_line, h} <- Enum.with_index(raw_lines, 1) do
      
      for {raw_char, w} <- Enum.with_index(String.graphemes(raw_line), 1) do 

        case raw_char do
          "|" -> [{h-1, w}, {h+1, w}]
          "-" -> [{h, w-1}, {h, w+1}]
          "L" -> [{h-1, w}, {h, w+1}]
          "J" -> [{h-1, w}, {h, w-1}]
          "7" -> [{h+1, w}, {h, w-1}]
          "F" -> [{h+1, w}, {h, w+1}]
          "." -> []
          "S" -> [{h, w}]
        end |> Enum.map(&:digraph.add_edge(digraph, {h,w}, &1))        
      end      
    end

    digraph
  end

end

Part 1: Used libgraph to construct the loop.

Part 2: Went the lazy route and used topo to count all coordinates that are contained inside the loop. Runs around 7-8 seconds in Livebook… but worked on first try.

https://github.com/pehbehbeh/adventofcode/blob/main/2023/10.livemd

Haven’t tried pt 2 yet. Not even sure how I would start, but here’s part 1 with a gratuitous use of :digraph b/c I thought that would be useful even though any number of better models would have been easier.

defmodule Part1 do
    @direction %{0 => :north, 1 => :south, 2 => :east, 3 => :west}

    def solve(input) do
      input
      |> parse()
      |> find_loop()
      |> furthest_distance()
    end

    defp parse(input) do
      input
      |> Input.lines()
      |> Enum.with_index()
      |> Enum.flat_map(fn {line, ndx} ->
        line
        |> String.graphemes()
        |> Enum.with_index()
        |> Enum.map(fn {char, ndx2} -> {ndx, {ndx2, char}} end)
      end)
      |> Enum.reduce({:digraph.new(), {}}, fn {k1, {k2, v}}, {g, start} = acc ->
        case v do
          "." ->
            acc

          "S" ->
            :digraph.add_vertex(g, {k1, k2}, v)
            {g, {k1, k2}}

          _ ->
            :digraph.add_vertex(g, {k1, k2}, v)
            {g, start}
        end
      end)
    end

    defp find_loop({graph, start}) do
      start
      |> neighbors()
      |> Enum.map(&:digraph.vertex(graph, &1))
      |> Enum.with_index()
      |> Enum.filter(fn {v, _} -> v end)
      |> Enum.map(fn {v, i} -> {v, @direction[i]} end)
      |> Task.async_stream(fn {v, direction} ->
        conn(graph, v, direction)
      end)
      |> Stream.filter(fn res ->
        res != {:ok, {:err, :dead_end}}
      end)
      |> Enum.at(0)
    end

    def conn(graph, {coord, label}, incoming_direction, count \\ 1) do
      case {label, incoming_direction} do
        {"-", :east} -> next_step(graph, east(coord), count + 1, :east)
        {"-", :west} -> next_step(graph, west(coord), count + 1, :west)
        {"|", :north} -> next_step(graph, north(coord), count + 1, :north)
        {"|", :south} -> next_step(graph, south(coord), count + 1, :south)
        {"J", :east} -> next_step(graph, north(coord), count + 1, :north)
        {"J", :south} -> next_step(graph, west(coord), count + 1, :west)
        {"L", :west} -> next_step(graph, north(coord), count + 1, :north)
        {"L", :south} -> next_step(graph, east(coord), count + 1, :east)
        {"F", :west} -> next_step(graph, south(coord), count + 1, :south)
        {"F", :north} -> next_step(graph, east(coord), count + 1, :east)
        {"7", :east} -> next_step(graph, south(coord), count + 1, :south)
        {"7", :north} -> next_step(graph, west(coord), count + 1, :west)
        _ -> {:err, :dead_end}
      end
    end

    def next_step(graph, curr, count, dir) do
      case {:digraph.vertex(graph, curr), dir} do
        {false, _} -> {:err, :dead_end}
        {{^curr, "."}, _} -> {:err, :dead_end}
        {{^curr, "S"}, _} -> {:ok, count}
        {{coord, label}, dir} -> conn(graph, {coord, label}, dir, count)
      end
    end

    def neighbors({{r, c}, _}), do: neighbors({r, c})

    def neighbors(coord) do
      [north(coord), south(coord), east(coord), west(coord)]
    end

    defp north({r, c}), do: {r - 1, c}
    defp south({r, c}), do: {r + 1, c}
    defp east({r, c}), do: {r, c + 1}
    defp west({r, c}), do: {r, c - 1}

    defp furthest_distance({_, {_, n}}), do: ceil(n / 2)
  end