defmodule Day18 do defmodule Game do @derive Inspect @enforce_keys [:obj, :source, :target, :w, :h] defstruct @enforce_keys def from_data(data, source, target) do obj = data |> String.split("\n", trim: true) |> Enum.map(&integer_list/1) |> Enum.map(&List.to_tuple/1) {w, h} = target %Game{obj: obj, source: source, target: target, w: w, h: h} end defp integer_list(s), do: String.split(s, ",") |> Enum.map(&String.to_integer/1) def shortest(game, count_obj \\ nil) do obj = if count_obj == nil do game.obj else Enum.take(game.obj, count_obj) end %Game{game | obj: MapSet.new(obj)} |> shortest(0, [game.source], MapSet.new([game.source])) end defp shortest(game, i, q, v) do case q do [] -> :none q -> if Enum.member?(q, game.target) do i else for n <- q, reduce: {[], v} do {q, v} -> neighbors(game, n) |> Enum.reject(&MapSet.member?(v, &1)) |> Enum.reduce({q, v}, fn n, {q, v} -> {[n | q], MapSet.put(v, n)} end) end |> then(fn {q, v} -> shortest(game, i+1, q, v) end) end end end defp neighbors(game, {x, y}) do [{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}] |> Enum.filter(fn {x, y} -> x >= 0 and x <= game.w and y >= 0 and y <= game.h end) |> Enum.reject(&MapSet.member?(game.obj, &1)) end end def part1(data) do data |> Game.from_data({0, 0}, {70, 70}) |> Game.shortest(1024) end def part2(data) do game = data |> Game.from_data({0, 0}, {70, 70}) part2(game, 1, Enum.count(game.obj)) end defp part2(game, l, r) do if l == r do Enum.at(game.obj, l-1) |> then(fn {x, y} -> "#{x},#{y}" end) else m = div(l + r, 2) if Game.shortest(game, m) != :none do part2(game, m+1, r) else part2(game, l, m) end end end end data = IO.read(:stdio, :eof) {time1, ans1} = :timer.tc(fn -> Day18.part1(data) end) IO.puts("Time : #{time1 / 1000000}") IO.puts("Answer: #{ans1}") {time2, ans2} = :timer.tc(fn -> Day18.part2(data) end) IO.puts("Time : #{time2 / 1000000}") IO.puts("Answer: #{ans2}")