Day 16
Input
sample = File.read!("#{__DIR__}/day16_sample.txt")
input = File.read!("#{__DIR__}/day16_input.txt")
Part 1
defmodule Aoc2023.Day16.Part1 do
def trace(map, heads, traces) do
width = map |> List.first() |> Enum.count()
height = map |> Enum.count()
next_heads =
heads
|> Enum.flat_map(fn {x, y, dir} ->
case {map |> Enum.at(y) |> Enum.at(x), dir} do
{".", :left} ->
[{x - 1, y, :left}]
{".", :right} ->
[{x + 1, y, :right}]
{".", :up} ->
[{x, y - 1, :up}]
{".", :down} ->
[{x, y + 1, :down}]
{"\\", :left} ->
[{x, y - 1, :up}]
{"\\", :right} ->
[{x, y + 1, :down}]
{"\\", :up} ->
[{x - 1, y, :left}]
{"\\", :down} ->
[{x + 1, y, :right}]
{"/", :left} ->
[{x, y + 1, :down}]
{"/", :right} ->
[{x, y - 1, :up}]
{"/", :up} ->
[{x + 1, y, :right}]
{"/", :down} ->
[{x - 1, y, :left}]
{"-", dir} when dir in [:left, :right] ->
[{x + if(dir == :left, do: -1, else: 1), y, dir}]
{"-", dir} when dir in [:up, :down] ->
[{x - 1, y, :left}, {x + 1, y, :right}]
{"|", dir} when dir in [:left, :right] ->
[{x, y - 1, :up}, {x, y + 1, :down}]
{"|", dir} when dir in [:up, :down] ->
[{x, y + if(dir == :up, do: -1, else: 1), dir}]
end
end)
|> Enum.filter(fn {x, y, _} = head ->
valid = x >= 0 and x < width and y >= 0 and y < height
new = head not in heads and head not in traces
valid and new
end)
|> MapSet.new()
new_heads = heads |> MapSet.union(next_heads)
new_traces = traces |> MapSet.union(next_heads)
if heads == new_heads and traces == new_traces do
{map, traces}
else
trace(map, new_heads, new_traces)
end
end
def energize(map, traces) do
width = map |> List.first() |> Enum.count()
height = map |> Enum.count()
0..(height - 1)
|> Enum.map(fn y ->
0..(width - 1)
|> Enum.map(fn x ->
if traces
|> Enum.any?(fn
{^x, ^y, _} -> true
_ -> false
end) do
"#"
else
"."
end
end)
end)
end
def run(input) do
{map, traces} =
input
|> String.split("\n", trim: true)
|> Enum.map(fn row -> String.split(row, "", trim: true) end)
|> trace(MapSet.new([{0, 0, :right}]), MapSet.new([{0, 0, :right}]))
energize(map, traces)
|> Enum.map(fn row -> row |> Enum.count(fn v -> v == "#" end) end)
|> Enum.sum()
end
end
Aoc2023.Day16.Part1.run(sample)
Aoc2023.Day16.Part1.run(input)
Part 2
defmodule Aoc2023.Day16.Part2 do
def get({map, w, h} = map_info, {x, y}) do
if x >= 0 and x < w and y >= 0 and y < h do
map |> Enum.at(y) |> Enum.at(x)
else
:outside
end
end
def split(dir, splitter) do
case {dir, splitter} do
{dir, "."} -> [dir]
{hori, "-"} when hori in [:left, :right] -> [hori]
{hori, "|"} when hori in [:left, :right] -> [:up, :down]
{vert, "-"} when vert in [:up, :down] -> [:left, :right]
{vert, "|"} when vert in [:up, :down] -> [vert]
{:left, "\\"} -> [:up]
{:right, "\\"} -> [:down]
{:up, "\\"} -> [:left]
{:down, "\\"} -> [:right]
{:left, "/"} -> [:down]
{:right, "/"} -> [:up]
{:up, "/"} -> [:right]
{:down, "/"} -> [:left]
end
end
def side_vectors({map, w, h}) do
[
0..(h - 1) |> Enum.map(fn y -> {0, y, :right} end),
0..(h - 1) |> Enum.map(fn y -> {w - 1, y, :left} end),
0..(w - 1) |> Enum.map(fn x -> {x, 0, :down} end),
0..(w - 1) |> Enum.map(fn x -> {x, h - 1, :up} end)
]
|> Enum.flat_map(& &1)
|> Enum.flat_map(fn {x, y, dir} ->
splitter = map |> Enum.at(y) |> Enum.at(x)
split(dir, splitter) |> Enum.map(fn dir -> {x, y, dir} end)
end)
end
def splitter_vectors({map, w, h}) do
0..(h - 1)
|> Enum.flat_map(fn y ->
0..(w - 1)
|> Enum.flat_map(fn x ->
case map |> Enum.at(y) |> Enum.at(x) do
"." ->
[]
"-" ->
[:left, :right] |> Enum.map(fn dir -> {x, y, dir} end)
"|" ->
[:up, :down] |> Enum.map(fn dir -> {x, y, dir} end)
d when d in ["\\", "/"] ->
[:left, :right, :up, :down] |> Enum.map(fn dir -> {x, y, dir} end)
end
end)
end)
|> Enum.filter(fn {x, y, _} -> x >= 0 and x < w and y >= 0 and y < h end)
end
def unit_vectors(map_info) do
MapSet.new(side_vectors(map_info) ++ splitter_vectors(map_info))
end
def advance(x, y, dir) do
case dir do
:left -> {x - 1, y}
:right -> {x + 1, y}
:up -> {x, y - 1}
:down -> {x, y + 1}
end
end
def find_endpoint({map, w, h} = map_info, {x, y} = point, dir) do
next_point = advance(x, y, dir)
next_tile = get(map_info, next_point)
case next_tile do
"." -> find_endpoint(map_info, next_point, dir)
:outside -> {point, []}
splitter -> {next_point, split(dir, splitter)}
end
end
def line({sx, sy}, {sx, ey}) do
sy..ey//if(sy < ey, do: 1, else: -1) |> Enum.map(fn y -> {sx, y} end) |> MapSet.new()
end
def line({sx, sy}, {ex, sy}) do
sx..ex//if(sx < ex, do: 1, else: -1) |> Enum.map(fn x -> {x, sy} end) |> MapSet.new()
end
def unit_paths({map, w, h} = map_info, vectors) do
vectors
|> Enum.map(fn {sx, sy, sdir} = starting_vector ->
{{ex, ey} = ep, edirs} = find_endpoint(map_info, {sx, sy}, sdir)
ending_vectors = edirs |> Enum.map(fn edir -> {ex, ey, edir} end)
{{sx, sy, sdir}, line({sx, sy}, {ex, ey}), ending_vectors, [starting_vector]}
end)
|> MapSet.new()
end
def merge_paths({map, w, h} = map_info, paths, i \\ 0) do
new_paths =
paths
|> Enum.map(fn {sv, line, evs, pvs} ->
{line, evs, pvs} =
evs
|> Enum.reduce({line, [], pvs}, fn ev, {line, evs, pvs} ->
paths
|> Enum.find(fn
{^ev, new_line, new_evs, new_pvs} -> true
{_sv, _line, _evs, _pvs} -> false
end)
|> case do
nil ->
{line, evs, pvs}
{^ev, new_line, new_evs, new_pvs} ->
{MapSet.union(new_line, line), new_evs ++ evs, new_pvs}
end
end)
evs = evs |> Enum.uniq() |> Enum.filter(fn ev -> ev not in pvs end)
{sv, line, evs, pvs |> Enum.uniq()}
end)
|> MapSet.new()
# if new_paths |> Enum.all?(fn {_, _, evs, _} -> evs == [] end) do
# new_paths
# else
# merge_paths(map_info, new_paths)
# end
if i == 10 do
new_paths
else
merge_paths(map_info, new_paths, i + 1)
end
# if new_paths == paths do
# new_paths
# else
# merge_paths(map_info, new_paths)
# end
end
def run(input) do
map =
input
|> String.split("\n", trim: true)
|> Enum.map(fn row -> String.split(row, "", trim: true) end)
w = map |> List.first() |> Enum.count()
h = map |> Enum.count()
map_info = {map, w, h}
unit_vectors = unit_vectors(map_info)
unit_paths = unit_paths(map_info, unit_vectors)
merge_paths(map_info, unit_paths)
|> Enum.map(fn {sv, line, evs, pvs} ->
{sv, line |> Enum.sort(), evs, pvs}
end)
|> Enum.sort()
|> Enum.take(2)
end
end
Aoc2023.Day16.Part2.run(sample)
