9.7 KiB
9.7 KiB
AOC 2024 Day 15
Section
defmodule Grid2D do
defstruct width: nil, height: nil
@directions %{
straight: [
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
],
diagonal: [
{1, 1},
{1, -1},
{-1, 1},
{-1, -1}
]
}
def new(width, height) do
%Grid2D{width: width, height: height}
end
@doc """
## Examples
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 0)
{0,0}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 5)
{0,1}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 6)
{1,1}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 3)
{3,0}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 24)
{4, 4}
"""
def index_to_coord(%Grid2D{width: w}, index) do
{rem(index, w), floor(index / w)}
end
@doc """
## Examples
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {0,0})
0
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {4,4})
24
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {2,2})
12
"""
def coord_to_index(%Grid2D{width: w}, {x, y}) do
y * w + x
end
@doc """
## Examples
iex> Grid2D.neighbors({0, 0}, Grid2D.new(5,5)) |> MapSet.new()
MapSet.new([{0, 1}, {1, 1}, {1,0}])
iex> Grid2D.neighbors({2, 2}, Grid2D.new(5,5)) |> MapSet.new()
[{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}] |> MapSet.new()
iex> Grid2D.neighbors({4, 4}, Grid2D.new(5,5)) |> MapSet.new
[{3, 3}, {3, 4}, {4, 3}] |> MapSet.new
"""
def neighbors(p, g, allowed_directions \\ :all) do
directions(allowed_directions)
|> Stream.map(&add(p, &1))
|> Stream.filter(&is_in_grid?(&1, g))
end
@doc """
Distance from two points in a grid
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {0,1}, :radial)
1
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,1}, :radial)
1
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,2}, :radial)
2
"""
def distance(grid, p1, p2, type)
def distance(_, {x, y}, {a, b}, :radial), do: max(abs(x - a), abs(y - b))
@doc """
Add two points together pairwise
iex> Grid2D.add({0,0}, {0,1})
{0,1}
iex> Grid2D.add({2,3}, {3,2})
{5,5}
"""
def add({x, y}, {j, k}), do: {x + j, y + k}
@doc """
Test if a point is in a grid
iex> Grid2D.is_in_grid?({1, 2}, %Grid2D{width: 3, height: 4})
true
iex> Grid2D.is_in_grid?({2, 2}, %Grid2D{width: 2, height: 4})
false
"""
def is_in_grid?({x, y}, %Grid2D{width: w, height: h}), do: x < w and y < h and x >= 0 and y >= 0
@spec directions(allowed :: :all | :straight | :diagonal) :: any()
def directions(allowed \\ :all)
def directions(:all), do: directions(:straight) ++ directions(:diagonal)
def directions(:straight), do: @directions |> Map.get(:straight)
def directions(:diagonal), do: @directions |> Map.get(:diagonal)
def mul({x, y}, n), do: {n*x, n*y}
end
input = """
"""
[map, instructions] = input |> String.trim() |> String.split("\n\n")
map = map
|> String.trim()
|> String.split("\n", trim: true)
|> Stream.with_index()
|> Stream.flat_map(fn {line, y_idx} ->
line
|> String.graphemes()
|> Stream.with_index()
|> Enum.map(fn {c, x_idx} -> {{x_idx, y_idx}, c} end)
end)
|> Enum.into(%{})
instructions = instructions |> String.trim() |> String.split("", trim: true) |> Stream.reject(&(&1 == "\n")) |> Enum.map(&(
case &1 do
"<" -> {-1, 0}
">" -> { 1, 0}
"^" -> { 0, -1}
"v" -> { 0, 1}
end
))
w = map |> Map.keys() |> Enum.max_by(&elem(&1, 0)) |> elem(0)
h = map |> Map.keys() |> Enum.max_by(&elem(&1, 1)) |> elem(1)
start = map |> Enum.find(fn {_, t} -> t == "@" end) |> elem(0)
grid = Grid2D.new(w, h)
defmodule WarehouseWoes do
def move(map, grid, direction) do
[{coord, _}] = map |> Enum.filter(&(elem(&1, 1) == "@"))
move(map, grid, coord, direction)
end
def move(map, _, _, []), do: map
def move(map, grid, coord, [dir | rest]) do
if can_move?(map, grid, coord, dir) do
next = coord |> Grid2D.add(dir)
tile = Map.get(map, next)
(if tile == "O" do
move(map, grid, next, [ dir ])
else
map
end)
|> Map.put(next, Map.get(map, coord))
|> Map.put(coord, ".")
|> move(grid, rest)
else
move(map, grid, coord, rest)
end
end
def can_move?(map, grid, coord, direction) do
next = coord |> Grid2D.add(direction)
in_grid? = next |> Grid2D.is_in_grid?(grid)
tile = Map.get(map, next)
in_grid? and tile != "#" and (tile != "O" or can_move?(map, grid, next, direction))
end
def print(map, grid) do
for y <- 0..(grid.height) do
for x <- 0..(grid.width) do
IO.write(Map.get(map, {x, y}))
if x == grid.width do
IO.write("\n")
end
end
end
:ok
end
end
defmodule WarehouseWoes2 do
def parse(input) do
[map, instructions] = input |> String.trim() |> String.split("\n\n")
map = map
|> String.trim()
|> String.split("\n", trim: true)
|> Stream.with_index()
|> Stream.flat_map(fn {line, y_idx} ->
line
|> String.graphemes()
|> Stream.with_index()
|> Enum.map(fn {c, x_idx} -> {{x_idx, y_idx}, c} end)
end)
|> Enum.reduce(%{}, fn {{x, y}, tile}, acc ->
case tile do
"O" -> acc |> Map.put({2*x, y}, "[") |> Map.put({2*x + 1, y}, "]")
"." -> acc |> Map.put({2*x, y}, ".") |> Map.put({2*x + 1, y}, ".")
"#" -> acc |> Map.put({2*x, y}, "#") |> Map.put({2*x + 1, y}, "#")
"@" -> acc |> Map.put({2*x, y}, "@") |> Map.put({2*x + 1, y}, ".")
end
end)
instructions = instructions |> String.trim() |> String.split("", trim: true) |> Stream.reject(&(&1 == "\n")) |> Enum.map(&(
case &1 do
"<" -> {-1, 0}
">" -> { 1, 0}
"^" -> { 0, -1}
"v" -> { 0, 1}
end
))
{map, instructions}
end
def solve(input) do
{map, instructions} = parse(input)
w = map |> Map.keys() |> Enum.max_by(&elem(&1, 0)) |> elem(0)
h = map |> Map.keys() |> Enum.max_by(&elem(&1, 1)) |> elem(1)
grid = Grid2D.new(w, h)
move(map, grid, instructions)
|> Stream.filter(&(elem(&1, 1) == "["))
|> Stream.map(&(elem(&1,0)))
|> Enum.reduce(0, fn {x, y},acc -> acc + 100*y + x end)
end
def move(map, grid, direction) do
[{coord, _}] = map |> Enum.filter(&(elem(&1, 1) == "@"))
move(map, grid, coord, direction)
end
@doc "
Recursively moves a coordinate on the map.
"
def move(map, _, _, []), do: map
# Only used when the turtle is pushing up on a block
# We gather all the coordinates for blocks being pushed in a direction,
# then try to move them up as a unit.
# The whole unit moves up if:
# - The space above all the blocks is empty (".")
# - The space above all the blocks is either empty or other blocks and those blocks can be move up.
# If the space above the blocks contains any walls ("#") or the blocks above them cannot be moved,
# the blocks will not move.
#
def move(map, grid, coords, [{0, n} = dir]) when is_list(coords) and (n == 1 or n == -1) do
nexts = coords |> Enum.flat_map(fn i ->
next = Grid2D.add(i, dir)
tile = Map.get(map, next)
case tile do
"[" -> [next, Grid2D.add(next, {1, 0})]
"]" -> [Grid2D.add(next, {-1, 0}), next]
_ -> [next]
end
end)
cond do
Enum.any?(nexts, &(Map.get(map, &1) == "#")) -> map
Enum.all?(nexts, &(Map.get(map, &1) == ".")) ->
coords
|> Enum.reduce(map, fn coord, acc ->
acc
|> Map.put(coord |> Grid2D.add(dir), Map.get(map, coord))
|> Map.put(coord, ".")
end)
true ->
moved = move(map, grid, nexts |> Enum.filter(fn c ->
tile = Map.get(map, c)
tile == "[" or tile == "]"
end), [dir])
if moved != map do
move(moved, grid, coords, [dir])
else
map
end
end
end
# This method is only ever actually called when `coord` represents the coord of robot (")
def move(map, grid, coord, [{0, n} = dir | rest]) when n == 1 or n == -1 do
next = Grid2D.add(coord, dir)
next_tile = Map.get(map, next)
map = case next_tile do
"." -> map
|> Map.put(next, Map.get(map, coord))
|> Map.put(coord, ".")
"#" -> map
"]" ->
next = [ Grid2D.add(next, {-1, 0}), next]
moved = move(map, grid, next, [dir])
if moved != map do
move(moved, grid, coord, [dir])
else
moved
end
"[" ->
next = [next, Grid2D.add(next, {1, 0})]
moved = move(map, grid, next, [dir])
if moved != map do
move(moved, grid, coord, [dir])
else
moved
end
end
map |> move(grid, rest)
end
def move(map, grid, coord, [dir | rest]) do
next = Grid2D.add(coord, dir)
next_tile = Map.get(map, next)
map = case next_tile do
"." -> map
|> Map.put(next, Map.get(map, coord))
|> Map.put(coord, ".")
"#" -> map
_ ->
moved = map |> move(grid, next, [dir])
if moved == map do
moved
else
move(moved, grid, coord, [dir])
end
end
map |> move(grid, rest)
end
@doc "
Prints the ASCII character for an instruction.
"
def instruction(i) do
case i do
{-1, 0} -> "<"
{1, 0} -> ">"
{0, -1} -> "^"
{0, 1} -> "v"
end
end
@doc "
Returns the current map as a string.
"
def print(map, grid) do
for y <- 0..(grid.height) do
for x <- 0..(grid.width) do
(Map.get(map, {x, y}) || ".") <>
(if x == grid.width do
"\n"
else
""
end)
end
end |> Enum.join("")
end
end
WarehouseWoes2.solve(input)