Day23

Mix.install([
  {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"},
  {:libgraph, "~> 0.16.0"}
])

Setup

{:ok, data} = KinoAOC.download_puzzle("2024", "23", System.fetch_env!("LB_AOC_SECRET"))

Solve

defmodule Day23 do
  def parse(data) do
    data
    |> String.trim()
    |> String.split("\n", trim: true)
    |> Enum.map(fn row ->
      String.split(row, "-", trim: true) |> List.to_tuple()
    end)
    |> to_graph()
  end

  def to_graph(data) do
    g = Graph.new(type: :undirected)
    Enum.reduce(data, g, fn {from ,to}, g ->
      Graph.add_edge(g, from, to)
    end)
  end

  def solve(data) do
    g = parse(data)
    {t1(g), t2(g)}
  end

  # Clique is a subgraph where all vertices are interconnected
  # Bron-Kerbosch is used for finding all maximal cliques
  # https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
  def t2(g) do
    g
    |>Graph.cliques()
    |> Enum.max_by(fn cl -> length(cl) end)
    |> Enum.sort()
    |> Enum.join(",")
  end

  def t1(g) do
    nets =
      for a <- Graph.vertices(g),
          b <- Graph.neighbors(g, a),
          c <- Graph.neighbors(g, b),
          is_connected(g, a, c) and is_t_net([a, b, c]),
          reduce: MapSet.new() do
        acc ->
          el = MapSet.new([a, b, c])
          MapSet.put(acc, el)
      end

    Enum.count(nets)
  end

  def is_connected(g, a, c) do
    a != c and a in Graph.neighbors(g, c)
  end

  def is_t_net(net), do: Enum.any?(net, &amp;String.starts_with?(&amp;1, "t"))
end

t1 = """
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
"""

Day23.solve(t1) |> IO.inspect(label: "t1")
Day23.solve(data) # {893, "cw,dy,ef,iw,ji,jv,ka,ob,qv,ry,ua,wt,xz"}