diff options
| -rw-r--r-- | src/day15.exs | 224 |
1 files changed, 224 insertions, 0 deletions
diff --git a/src/day15.exs b/src/day15.exs new file mode 100644 index 0000000..f176918 --- /dev/null +++ b/src/day15.exs @@ -0,0 +1,224 @@ +defmodule Day15 do + defmodule Game do + @derive Inspect + defstruct [:grid, :robot, :moves] + + def from_data(data) do + [grid, moves] = data + |> String.split("\n\n", trim: true) + + grid = grid + |> String.split("\n", trim: true) + |> Enum.with_index() + |> Enum.flat_map(fn {s, i} -> + String.codepoints(s) + |> Enum.with_index() + |> Enum.map(fn {c, j} -> {{i, j}, c} end) + end) + |> Map.new() + + robot = grid + |> Enum.find_value(fn {pos, c} -> c == "@" and pos end) + + moves = moves + |> String.split("\n", trim: true) + |> Enum.flat_map(&String.codepoints/1) + + %Game{grid: grid, robot: robot, moves: moves} + end + + def expand(game) do + grid = game.grid + |> Enum.flat_map(fn {{i, j}, v} -> + case v do + "." -> [{{i, j*2}, "."}, {{i, j*2+1}, "."}] + "@" -> [{{i, j*2}, "@"}, {{i, j*2+1}, "."}] + "O" -> [{{i, j*2}, "["}, {{i, j*2+1}, "]"}] + "#" -> [{{i, j*2}, "#"}, {{i, j*2+1}, "#"}] + end + end) + |> Map.new() + + robot = {elem(game.robot, 0), elem(game.robot, 1)*2} + + %Game{grid: grid, robot: robot, moves: game.moves} + end + + def do_moves(game) do + if game.moves == [] do + game + else + move(game) + |> do_moves() + end + end + + defp move(game) do + [move | moves] = game.moves + + moved? = check_moves(game.grid, move, game.robot) |> elem(0) + + grid = + if moved? do + apply_move(game.grid, move, queue_new(game.robot)) + else + game.grid + end + + robot = if moved? do next_pos(game.robot, move) else game.robot end + + %Game{grid: grid, robot: robot, moves: moves} + end + + defp check_moves(grid, move, k, vis \\ MapSet.new()) do + if MapSet.member?(vis, k) do + {true, vis} + else + vis = MapSet.put(vis, k) + v = Map.fetch!(grid, k) + case v do + "." -> + {true, vis} + "#" -> + {false, vis} + "@" -> + check_moves(grid, move, next_pos(k, move), vis) + "O" -> + check_moves(grid, move, next_pos(k, move), vis) + "[" -> + nk = next_pos(k, move) + if move == "^" or move == "v" do + {oi, _} = k + {_, nj} = nk + {a1, vis} = check_moves(grid, move, nk, vis) + {a2, vis} = check_moves(grid, move, {oi, nj+1}, vis) + {a1 and a2, vis} + else + check_moves(grid, move, nk, vis) + end + "]" -> + nk = next_pos(k, move) + if move == "^" or move == "v" do + {oi, _} = k + {_, nj} = nk + {a1, vis} = check_moves(grid, move, nk, vis) + {a2, vis} = check_moves(grid, move, {oi, nj-1}, vis) + {a1 and a2, vis} + else + check_moves(grid, move, nk, vis) + end + end + end + end + + defp apply_move(grid, move, queue) do + if queue_empty(queue) do + grid + else + {pos, nv, queue} = queue_pop(queue, move) + v = Map.fetch!(grid, pos) + case v do + "#" -> + raise "Unexpected" + "." -> + apply_move(Map.put(grid, pos, nv), move, queue) + v -> + grid = Map.put(grid, pos, nv) + npos = next_pos(pos, move) + nv = Map.fetch!(grid, npos) + queue = + if (move == "^" or move == "v") and (nv == "[" or nv == "]") do + {i, j} = npos + j = if nv == "[" do j+1 else j-1 end + queue = queue_add(queue, npos, v) + queue_add(queue, {i, j}, ".") + else + queue_add(queue, npos, v) + end + apply_move(grid, move, queue) + end + end + end + + defp queue_add(queue, pos, v) do + case :gb_trees.lookup(pos, queue) do + :none -> + :gb_trees.insert(pos, v, queue) + {_, "."} -> + :gb_trees.update(pos, v, queue) + _ -> + queue + end + end + + defp queue_pop(queue, move) do + if move == "^" do + :gb_trees.take_largest(queue) + else + :gb_trees.take_smallest(queue) + end + end + + defp queue_new(robot) do + :gb_trees.insert(robot, ".", :gb_trees.empty()) + end + + defp queue_empty(queue) do + :gb_trees.is_empty(queue) + end + + defp next_pos({i, j}, move) do + case move do + ">" -> {i, j+1} + "^" -> {i-1, j} + "<" -> {i, j-1} + "v" -> {i+1, j} + end + end + + def print(game) do + w = game.grid |> Enum.map(fn {{_, j}, _} -> j end) |> Enum.max() + h = game.grid |> Enum.map(fn {{i, _}, _} -> i end) |> Enum.max() + for i <- 0..h do + for j <- 0..w, reduce: [] do + acc -> [Map.fetch!(game.grid, {i, j}) | acc] + end + |> Enum.reverse() + |> Enum.join("") + |> IO.puts() + end + game + end + end + + def part1(data) do + data + |> Game.from_data() + |> Game.do_moves() + |> then(& &1.grid) + |> Enum.filter(fn {_, v} -> v == "O" end) + |> Enum.map(fn {{i, j}, _} -> i*100 + j end) + |> Enum.sum() + end + + def part2(data) do + data + |> Game.from_data() + |> Game.expand() + |> Game.do_moves() + |> then(& &1.grid) + |> Enum.filter(fn {_, v} -> v == "[" end) + |> Enum.map(fn {{i, j}, _} -> i*100 + j end) + |> Enum.sum() + end +end + +data = IO.read(:stdio, :eof) + +{time1, ans1} = :timer.tc(fn -> Day15.part1(data) end) +IO.puts("Time : #{time1 / 1000000}") +IO.puts("Answer: #{ans1}") + +{time2, ans2} = :timer.tc(fn -> Day15.part2(data) end) +IO.puts("Time : #{time2 / 1000000}") +IO.puts("Answer: #{ans2}") |