Day 18HEADmaster

1 files changed, 94 insertions, 0 deletions

diff --git a/src/day18.exs b/src/day18.exs
new file mode 100644
index 0000000..e97da36
--- /dev/null
+++ b/src/day18.exs
@@ -0,0 +1,94 @@
+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}")