# Advent of Code 2023 - Day 10

I spent 3 hours struggling in part 2, until I noticed a very basic mistake

Here’s my code:

By the way, the starting position in my puzzle input is adjacent to up and down pipes, so in Part 2 I just treat it as a `|`.

1 Like

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:

2 Likes

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.

1 Like

My solution, runs in 8-10 ms: https://github.com/ibarakaiev/advent-of-code-2023/blob/main/lib/advent_of_code/day_10.ex

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.

3 Likes

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

1 Like

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.

Part 1
``````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)
``````
Part 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.

4 Likes

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 )

@midouest Nice one ! Expanding the map is fun

2 Likes

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

1 Like

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
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
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
``````
2 Likes

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.

1 Like

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
``````

Too slow to edit my last post. Once I had the thought of getting the area of an irregular polygon it was just a matter of realizing you have to subtract the nodes on the perimeter from that area. Re-wrote my pt 1 to make it reusable for pt 2.

``````defmodule Day10 do
@moduledoc """
Day10 AoC Solutions
"""

alias AocToolbox.Input

def input(:test),
do: """
.....
.S-7.
.|.|.
.L-J.
.....
"""

def input(:test2),
do: """
..F7.
.FJ|.
SJ.L7
|F--J
LJ...
"""

def input(:test3),
do: """
...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........
"""

def input(:test4),
do: """
.F----7F7F7F7F-7....
.|F--7||||||||FJ....
.||.FJ||||||||L7....
FJL7L7LJLJ||LJ.L-7..
L--J.L7...LJS7F-7L7.
....F-J..F7FJ|L7L7L7
....L7.F7||L7|.L7L7|
.....|FJLJ|FJ|F7|.LJ
....FJL-7.||.||||...
....L---J.LJ.LJLJ...
"""

def input(:test5),
do: """
FF7FSF7F7F7F7F7F---7
L|LJ||||||||||||F--J
FL-7LJLJ||||||LJL-77
F--JF--7||LJLJ7F7FJ-
L---JF-JLJ.||-FJLJJ7
|F|F-JF---7F7-L7L|7|
|FFJF7L7F-JF7|JL---7
7-L-JL7||F7|L7F-7F7|
L.L7LFJ|||||FJL7||LJ
L7JLJL-JLJLJL--JLJ.L
"""

def input(:real), do: Input.load(__DIR__ <> "/input.txt")

def solve(1, mode) do
__MODULE__.Part1.solve(input(mode))
end

def solve(2, mode) do
__MODULE__.Part2.solve(input(mode))
end

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

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

def 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

def 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, 1, [start])
end)
|> Stream.filter(fn res ->
res != {:ok, {:err, :dead_end}}
end)
|> Enum.at(0)
end

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

def next_step(graph, curr, count, dir, path) do
case {:digraph.vertex(graph, curr), dir} do
{false, _} -> {:err, :dead_end}
{{^curr, "."}, _} -> {:err, :dead_end}
{{^curr, "S"}, _} -> {:ok, count, path}
{{coord, label}, dir} -> conn(graph, {coord, label}, dir, count, path)
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, _path}}), do: ceil(n / 2)
end

defmodule Part2 do
@moduledoc """
Do part 1, building the path for the loop. Use the shoelace formula to get the area bounded by the loop.
Subtract the length of the loop to get the number of blocks enclosed by the loop.
"""
def solve(input) do
input
|> parse()
|> Day10.Part1.find_loop()
|> elem(1)
|> elem(2)
|> calc_interior_points()
end

defp calc_interior_points(path) do
perimeter = length(path)
area = AocToolbox.Math.shoelace_formula(path)
area - perimeter / 2 + 1
end

defp parse(input) do
Day10.Part1.parse(input)
end
end
end
#########
defmodule AocToolbox.Math do
defp do_shoelace([[r1 | r_tl] = rows, [c1 | c_tl] = cols]) do
blue = Enum.zip(rows, c_tl ++ [c1]) |> Enum.reduce(0, fn {r, c}, sum -> sum + r * c end)

red = Enum.zip(cols, r_tl ++ [r1]) |> Enum.reduce(0, fn {c, r}, sum -> sum + c * r end)
(abs(blue - red) / 2) |> floor()
end
end
``````

Would have been cool to try it with Nx but now I’m too far behind to keep tinkering.

1 Like

I was close to giving up on Part 2, because I couldn’t get the logic quite right for determining whether a given coordinate was inside or outside the loop. Whenever I would fix one case, a different one would start failing. Then I realized - I was only looking at the current symbol in isolation. But in fact, a corner pipe (e.g. “L” or “J”) means something different depending on the previous corner pipe. Once I started keeping a buffer of the last seen corner pipe, I could finally know for sure whether we were “opening” or “closing” the loop. If it goes back in the same direction it came, the `inside?` flag is unchanged. But if the pair of corners send the pipes in opposite directions, then it works the same as a `"-"` symbol, flipping the flag to `!inside?`

Example, scanning columns vertically:

``````defp area_in_col([{{_, y}, "J"} | next], inside?, {_prev_y, prev_symbol}, total) do
now_inside? = if prev_symbol == "7", do: inside?, else: !inside?
area_in_col(next, now_inside?, {y, "J"}, total)
end
``````

Full solution here on Github

1 Like

Part 2 I only was able to solve after watching this video where it was introduced to the Ray Casting Algorithm Day 10: Pipe Maze | Advent of Code 2023

So first it traverses the sketch map by keeping track of the pipes of the loop by adding them to a MapSet, then to count the points inside the loop it traverses the whole sketch map by checking if a point is not in the pipes loop and if not it applies the Ray Casting to count the intersections with the pipes in the loop.

So here’s my code following what was suggested there:

``````# "F" and "7" are not edge pipes because let's say a line passes
# through an "L" and a "7", which means the line only intersects the edge of the polygon once.
# This video explains it: https://www.youtube.com/watch?v=zhmzPQwgPg0&t=425s
@edge_pipes ["L", "J", "|"]

def part_two(input, {row_dir, col_dir} = start_direction, pipe_of_s) do
{sketch_map, {start_row, start_col}} =
input
|> parse_sketch_to_map_finding_start_position()

pipes_in_loop =
move_keeping_track_of_pipes(
Map.get(sketch_map, {start_row + row_dir, start_col + col_dir}),
{start_row + row_dir, start_col + col_dir},
start_direction,
sketch_map,
MapSet.new() |> MapSet.put({start_row, start_col})
)

{row_length, col_length} = get_sketch_dimensions(input)

sketch_map = Map.update(sketch_map, {start_row, start_col}, pipe_of_s, fn _ -> pipe_of_s end)

1..(row_length - 2)
|> Enum.reduce(0, fn row, acc ->
1..(col_length - 2)
|> Enum.reduce(acc, fn col, acc ->
if MapSet.member?(pipes_in_loop, {row, col}) do
acc
else
# traverse row applying the ray casting algorithm
# https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
col + 1..col_length - 1
|> Enum.reduce(0, fn col_inner_loop, ray_casting_acc ->
if MapSet.member?(pipes_in_loop, {row, col_inner_loop}) && sketch_map[{row, col_inner_loop}] in @edge_pipes do
ray_casting_acc + 1
else
ray_casting_acc
end
end)
|> then(&(if rem(&1, 2) == 1, do: acc + 1, else: acc))
end
end)
end)
end
``````

The full code is here: advent_of_code_2023/lib/day_ten.ex at main · tiagoavila/advent_of_code_2023 · GitHub