Adam Millerchip
e8a87d4a9c
Remove need to duplicate first value of pushable_boxes Fail fast when left branch produces :wall in part 2
244 lines
7 KiB
Elixir
Executable file
244 lines
7 KiB
Elixir
Executable file
#!/usr/bin/env elixir
|
|
defmodule Day15 do
|
|
def part1({warehouse, robot, moves}) do
|
|
attempt_moves(moves, robot, warehouse)
|
|
|> Enum.filter(&match?({_, :box}, &1))
|
|
|> Enum.map(fn {{x, y}, :box} -> x + y * 100 end)
|
|
|> Enum.sum()
|
|
end
|
|
|
|
def attempt_moves([], _robot, warehouse), do: warehouse
|
|
|
|
def attempt_moves([move | next_moves], robot, warehouse) do
|
|
next = move.(robot)
|
|
|
|
case Map.fetch(warehouse, next) do
|
|
:error ->
|
|
attempt_moves(next_moves, next, warehouse)
|
|
|
|
{:ok, :wall} ->
|
|
attempt_moves(next_moves, robot, warehouse)
|
|
|
|
{:ok, :box} ->
|
|
case get_pushable_boxes(next, move, warehouse) do
|
|
:wall ->
|
|
attempt_moves(next_moves, robot, warehouse)
|
|
|
|
boxes ->
|
|
warehouse =
|
|
Enum.reduce(boxes, warehouse, fn box, warehouse ->
|
|
warehouse |> Map.delete(box) |> Map.put(move.(box), :box)
|
|
end)
|
|
|
|
attempt_moves(next_moves, next, warehouse)
|
|
end
|
|
end
|
|
end
|
|
|
|
def get_pushable_boxes(box, move, warehouse, pushable_boxes \\ []) do
|
|
next = move.(box)
|
|
pushable_boxes = [box | pushable_boxes]
|
|
|
|
case Map.fetch(warehouse, next) do
|
|
:error -> pushable_boxes
|
|
{:ok, :wall} -> :wall
|
|
{:ok, :box} -> get_pushable_boxes(next, move, warehouse, pushable_boxes)
|
|
end
|
|
end
|
|
|
|
def part2({warehouse, {x, y}, moves}) do
|
|
bigger_warehouse =
|
|
Enum.reduce(warehouse, %{}, fn {{x, y}, v}, bigger ->
|
|
{left, right} =
|
|
case v do
|
|
:box -> {{:box, :left}, {:box, :right}}
|
|
:wall -> {:wall, :wall}
|
|
end
|
|
|
|
bigger |> Map.put({x * 2, y}, left) |> Map.put({x * 2 + 1, y}, right)
|
|
end)
|
|
|
|
robot = {x * 2, y}
|
|
|
|
attempt_moves2(moves, robot, bigger_warehouse)
|
|
|> Enum.filter(&match?({_, {:box, :left}}, &1))
|
|
|> Enum.map(fn {{x, y}, {:box, :left}} -> x + y * 100 end)
|
|
|> Enum.sum()
|
|
end
|
|
|
|
def attempt_moves2([], _robot, warehouse), do: warehouse
|
|
|
|
def attempt_moves2([move | next_moves], robot, warehouse) do
|
|
next = move.(robot)
|
|
|
|
case Map.fetch(warehouse, next) do
|
|
:error ->
|
|
attempt_moves2(next_moves, next, warehouse)
|
|
|
|
{:ok, :wall} ->
|
|
attempt_moves2(next_moves, robot, warehouse)
|
|
|
|
{:ok, {:box, side}} ->
|
|
case get_pushable_boxes2(next, side, move, warehouse) do
|
|
:wall ->
|
|
attempt_moves2(next_moves, robot, warehouse)
|
|
|
|
boxes ->
|
|
new_boxes = Map.new(boxes, fn {box, side} -> {move.(box), {:box, side}} end)
|
|
|
|
warehouse =
|
|
warehouse
|
|
|> Map.drop(Enum.map(boxes, &elem(&1, 0)))
|
|
|> Map.merge(new_boxes)
|
|
|
|
attempt_moves2(next_moves, next, warehouse)
|
|
end
|
|
end
|
|
end
|
|
|
|
# need to account for 2-width boxes when pushing vertically
|
|
# @<--pushing down moves down all RHS of stack
|
|
# [][][][]
|
|
# [][][] @
|
|
# [][] []<--make sure RHS moves too
|
|
# []
|
|
# @<- pushing up pushes all
|
|
def get_pushable_boxes2(box, side, move, warehouse, pushable_boxes \\ []) do
|
|
next = move.(box)
|
|
pushable_boxes = [{box, side} | pushable_boxes]
|
|
|
|
case abs(elem(next, 1) - elem(box, 1)) do
|
|
# horizontal
|
|
0 ->
|
|
case Map.fetch(warehouse, next) do
|
|
:error ->
|
|
pushable_boxes
|
|
|
|
{:ok, :wall} ->
|
|
:wall
|
|
|
|
{:ok, {:box, next_side}} ->
|
|
get_pushable_boxes2(next, next_side, move, warehouse, pushable_boxes)
|
|
end
|
|
|
|
# vertical
|
|
1 ->
|
|
{x, y} = box
|
|
|
|
{other_box, other_side} =
|
|
case side do
|
|
:left -> {{x + 1, y}, :right}
|
|
:right -> {{x - 1, y}, :left}
|
|
end
|
|
|
|
other_next = move.(other_box)
|
|
|
|
pushable_boxes = [{other_box, other_side} | pushable_boxes]
|
|
|
|
side
|
|
|> case do
|
|
:left ->
|
|
{{Map.fetch(warehouse, next), Map.fetch(warehouse, other_next)}, next, other_next}
|
|
|
|
:right ->
|
|
{{Map.fetch(warehouse, other_next), Map.fetch(warehouse, next)}, other_next, next}
|
|
end
|
|
|> case do
|
|
{{:error, :error}, _, _} ->
|
|
pushable_boxes
|
|
|
|
{{{:ok, :wall}, _}, _, _} ->
|
|
:wall
|
|
|
|
{{_, {:ok, :wall}}, _, _} ->
|
|
:wall
|
|
|
|
{{{:ok, {:box, side}}, :error}, left, _right} ->
|
|
get_pushable_boxes2(left, side, move, warehouse, pushable_boxes)
|
|
|
|
{{:error, {:ok, {:box, side}}}, _left, right} ->
|
|
get_pushable_boxes2(right, side, move, warehouse, pushable_boxes)
|
|
|
|
{{{:ok, {:box, :left}}, {:ok, {:box, :right}}}, left, _} ->
|
|
# if left-right, just one box, only need to check one side
|
|
# []
|
|
# []
|
|
get_pushable_boxes2(left, :left, move, warehouse, pushable_boxes)
|
|
|
|
{{{:ok, {:box, :right}}, {:ok, {:box, :left}}}, left, right} ->
|
|
# if right-left, two boxes, so need to check both...
|
|
# [][]
|
|
# []
|
|
with left when left != :wall <- get_pushable_boxes2(left, :right, move, warehouse, []),
|
|
right when right != :wall <- get_pushable_boxes2(right, :left, move, warehouse, []) do
|
|
pushable_boxes ++ left ++ right
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
def input do
|
|
with [input_filename] <- System.argv(),
|
|
{:ok, input} <- File.read(input_filename) do
|
|
[raw_map, raw_moves] = String.split(input, "\n\n")
|
|
|
|
{_, _y, robot, map} =
|
|
for <<char::binary-1 <- raw_map <> "\n">>, reduce: {0, 0, nil, %{}} do
|
|
{x, y, robot, map} ->
|
|
case char do
|
|
"." -> {x + 1, y, robot, map}
|
|
"#" -> {x + 1, y, robot, Map.put(map, {x, y}, :wall)}
|
|
"O" -> {x + 1, y, robot, Map.put(map, {x, y}, :box)}
|
|
"@" -> {x + 1, y, {x, y}, map}
|
|
"\n" -> {0, y + 1, robot, map}
|
|
end
|
|
end
|
|
|
|
moves =
|
|
for <<char::binary-1 <- String.replace(raw_moves, "\n", "")>> do
|
|
case char do
|
|
"^" -> fn {x, y} -> {x, y - 1} end
|
|
"v" -> fn {x, y} -> {x, y + 1} end
|
|
"<" -> fn {x, y} -> {x - 1, y} end
|
|
">" -> fn {x, y} -> {x + 1, y} end
|
|
end
|
|
end
|
|
|
|
{map, robot, moves}
|
|
else
|
|
_ -> :error
|
|
end
|
|
end
|
|
|
|
#######################
|
|
# HERE BE BOILERPLATE #
|
|
#######################
|
|
|
|
def run do
|
|
case input() do
|
|
:error -> print_usage()
|
|
input -> run_parts_with_timer(input)
|
|
end
|
|
end
|
|
|
|
defp run_parts_with_timer(input) do
|
|
run_with_timer(1, fn -> part1(input) end)
|
|
run_with_timer(2, fn -> part2(input) end)
|
|
end
|
|
|
|
defp run_with_timer(part, fun) do
|
|
{time, result} = :timer.tc(fun)
|
|
IO.puts("Part #{part} (completed in #{format_time(time)}):\n")
|
|
IO.puts("#{inspect(result)}\n")
|
|
end
|
|
|
|
defp format_time(μsec) when μsec < 1_000, do: "#{μsec}μs"
|
|
defp format_time(μsec) when μsec < 1_000_000, do: "#{μsec / 1000}ms"
|
|
defp format_time(μsec), do: "#{μsec / 1_000_000}s"
|
|
|
|
defp print_usage do
|
|
IO.puts("Usage: elixir day15.exs input_filename")
|
|
end
|
|
end
|
|
|
|
Day15.run()
|