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):
- Find S
- 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).
- 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:
- 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.
- 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
: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
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
