defmodule Day23 do
  defmodule Graph do
    @derive Inspect
    @enforce_keys [:nodes, :edges, :adj, :deg]
    defstruct @enforce_keys

    def from_data(data) do
      edges = data
      |> String.split("\n", trim: true)
      |> Enum.map(&String.split(&1, "-", trim: true))
      |> Enum.map(fn [a,b] -> if a < b do [a, b] else [b, a] end end)

      nodes = edges
      |> List.flatten()
      |> Enum.sort()
      |> Enum.dedup()

      adj =
        for [a, b] <- edges, reduce: %{} do
          acc ->
            add_adj(acc, a, b)
            |> add_adj(b, a)
        end
        |> Enum.map(fn {k, v} -> {k, MapSet.new(v)} end)
        |> Map.new()

      deg = Enum.map(adj, fn {k, v} -> {k, Enum.count(v)} end) |> Map.new()

      %Graph{edges: edges, nodes: nodes, adj: adj, deg: deg}
    end

    defp add_adj(adj, a, b) do
      Map.get_and_update(adj, a, fn v ->
        case v do
          nil -> {v, [b]}
          lst -> {v, [b | lst]}
        end
      end)
      |> elem(1)
    end

    def cliques(graph, n) do
      cliques([], graph.adj, [], MapSet.new(graph.nodes), n)
      |> Enum.map(&Enum.sort/1)
      |> Enum.sort()
      |> Enum.dedup()
    end

    # Could be improved, but this is fast enough
    defp cliques(acc, adj, nodes, possible, n) do
      if n == 0 do
        [nodes | acc]
      else
        for v <- possible, reduce: acc do
          acc ->
            cliques(acc, adj, [v | nodes], MapSet.intersection(Map.get(adj, v), possible), n-1)
        end
      end
    end

    def maxclique(graph) do
      bk([], graph.adj, graph.deg, [], MapSet.new(graph.nodes), MapSet.new())
      |> Enum.max_by(&Enum.count/1)
    end

    defp bk(acc, adj, deg, r, p, x) do
      if Enum.empty?(p) && Enum.empty?(x) do
        [r | acc]
      else
        u = Enum.max_by(MapSet.union(p, x), fn u -> Map.get(deg, u) end)
        nu = Map.get(adj, u)
        np = MapSet.difference(p, nu)
        for v <- np, reduce: {acc, p, x} do
          {acc, p, x} ->
            {
              bk(
                acc,
                adj,
                deg,
                [v | r],
                MapSet.intersection(p, Map.get(adj, v)),
                MapSet.intersection(x, Map.get(adj, v))
              ),
              MapSet.delete(p, v),
              MapSet.put(x, v)
            }
        end
        |> elem(0)
      end
    end
  end
  
  def part1(data) do
    data
    |> Graph.from_data()
    |> Graph.cliques(3)
    |> Enum.filter(fn nodes -> Enum.any?(nodes, fn v -> String.starts_with?(v, "t") end) end)
    |> Enum.count()
  end

  def part2(data) do
    data
    |> Graph.from_data()
    |> Graph.maxclique()
    |> Enum.sort()
    |> Enum.join(",")
  end
end

data = IO.read(:stdio, :eof)

{time1, ans1} = :timer.tc(fn -> Day23.part1(data) end)
IO.puts("Time  : #{time1 / 1000000}")
IO.puts("Answer: #{ans1}") # 1046

{time2, ans2} = :timer.tc(fn -> Day23.part2(data) end)
IO.puts("Time  : #{time2 / 1000000}")
IO.puts("Answer: #{ans2}") # de,id,ke,ls,po,sn,tf,tl,tm,uj,un,xw,yz