Aetherus
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:
https://github.com/Aetherus/advent-of-code/blob/master/2023/day-10.livemd
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 |.
Most Liked
midouest
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.
igorb
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):
- 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.
bjorng
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
Popular in Challenges
Other popular topics
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #advent-of-code
- #elixirconf-us
- #distillery
- #processes
- #forms
- #api
- #metaprogramming
- #security
- #performance








