Day 23HEADmaster

1 files changed, 118 insertions, 0 deletions

diff --git a/src/day23.exs b/src/day23.exs
new file mode 100644
index 0000000..04d60ce
--- /dev/null
+++ b/src/day23.exs
@@ -0,0 +1,118 @@
+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