defmodule Part1 do
  def parse(input) do
    for line <- String.split(input, "\n", trim: true),
        reduce: %{} do
      acc ->
        [a | rest] = String.split(line, [":", " "], trim: true)

        for b <- rest,
            reduce: acc do
          acc ->
            acc
            |> Map.update(a, MapSet.new([b]), &MapSet.put(&1, b))
            |> Map.update(b, MapSet.new([a]), &MapSet.put(&1, a))
        end
    end
  end

  def group_product(graph) do
    Map.keys(graph)
    |> Enum.map(&String.length/1)
    |> Enum.map(&div(&1, 3))
    |> Enum.product()
  end

  def cut_size(g1, g0) do
    [as, bs] =
      for key <- Map.keys(g1) do
        key
        |> String.to_charlist()
        |> Enum.chunk_every(3)
        |> Enum.map(&to_string/1)
      end

    bs = MapSet.new(bs)

    for a <- as,
        _ <- MapSet.intersection(g0[a], bs),
        reduce: 0 do
      acc -> acc + 1
    end
  end

  def contract(graph) when map_size(graph) == 2, do: graph

  def contract(graph) do
    {a, ea} = Enum.random(graph)
    b = Enum.random(ea)
    eb = graph[b]

    ab = a <> b

    ea = MapSet.delete(ea, b)
    eb = MapSet.delete(eb, a)

    eab = MapSet.union(ea, eb)

    graph =
      Enum.reduce(ea, graph, fn c, graph ->
        Map.update!(graph, c, fn ec ->
          ec
          |> MapSet.delete(a)
          |> MapSet.put(ab)
        end)
      end)

    graph =
      Enum.reduce(eb, graph, fn c, graph ->
        Map.update!(graph, c, fn ec ->
          ec
          |> MapSet.delete(b)
          |> MapSet.put(ab)
        end)
      end)

    graph =
      graph
      |> Map.delete(a)
      |> Map.delete(b)
      |> Map.put(ab, eab)

    contract(graph)
  end
end

g0 = Part1.parse(input)

Stream.repeatedly(fn -> Part1.contract(g0) end)
|> Enum.find(fn g1 -> Part1.cut_size(g1, g0) == 3 end)
|> Part1.group_product()