Day 23

Solution

{:ok, contents} = File.read("#{__DIR__}/inputs/day23.txt")

adj =
  contents
  |> String.split("\n", trim: true)
  |> Enum.map(&String.split(&1, "-"))
  |> Enum.reduce(%{}, fn [a, b], acc ->
    acc
    |> Map.update(a, MapSet.new([b]), &MapSet.put(&1, b))
    |> Map.update(b, MapSet.new([a]), &MapSet.put(&1, a))
  end)

# Part 1
adj
|> Enum.filter(fn {k, _} -> String.starts_with?(k, "t") end)
|> Enum.flat_map(fn {k, v} ->
  for a <- v, b <- v, b in adj[a], do: MapSet.new([k, a, b])
end)
|> Enum.reduce(MapSet.new(), &amp;MapSet.put(&amp;2, &amp;1))
|> Enum.count()

greedy_clique = fn x ->
  adj[x]
  |> Enum.reduce(
    MapSet.new(),
    &if(MapSet.subset?(&2, adj[&1]), do: MapSet.put(&2, &1), else: &2)
  )
  |> MapSet.put(x)
end

maybe_answer =
  adj
  |> Map.keys()
  |> Enum.map(greedy_clique)
  |> Enum.max_by(&Enum.count/1)

max_degree = adj |> Map.values() |> Enum.map(&Enum.count/1) |> Enum.max()

if Enum.count(maybe_answer) >= max_degree do
  # Max clique size is (max_degree + 1) and must be found by the greedy algorithm.
  # If not, but there is a K-(max_degree), then that is the answer.
  maybe_answer |> Enum.sort() |> Enum.join(",")
end