path: root/src/day18.exs

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}")