advent_of_code/elixir/livebook/2024/day23.livemd

AOC 2024 Day 23

Section

defmodule LANGraph do
  defstruct nodes: MapSet.new, edges: MapSet.new
  @doc """
  For a graph, counts the number of cycles of size `size` in the graph.
  """
  def cycles(graph, 3) do
    nodes = graph.nodes

    nodes
    |> Enum.flat_map(
      fn v -> find_cycle(graph, v, v, [], 3, 0) end
    )
  end

  def find_cycle(_, _, _, path, n, y) when y == n, do: [path]
  def find_cycle(graph, start, v, path, depth, curr) do
    is_next_node? = fn u -> 
      if curr == (depth - 1), do: u == start, else: Enum.all?(path, &(&1 != u))
    end
  
    outE(graph, v)
    |> Stream.map(fn {uu, vv} -> if uu == v, do: vv, else: uu end)
    |> Stream.filter(is_next_node?)
    |> Enum.flat_map(&find_cycle(graph, start, &1, [v | path], depth, curr + 1))
  end

  defp outE(graph, vertex) do
    graph.edges
    |> Enum.filter(&(elem(&1,0) == vertex or elem(&1,1) == vertex))
  end
  
  def add_edge(graph, {a, b} = edge) do
    %LANGraph{
      nodes: graph.nodes |> MapSet.put(a) |> MapSet.put(b),
      edges: graph.edges |> MapSet.put(edge)
    }
  end

  def neighbors(graph, vertex) do
    graph.edges 
    |> Stream.filter(&(elem(&1, 0) == vertex or elem(&1, 1) == vertex))
    |> Enum.map(fn 
      {^vertex, b} -> b 
      {b, ^vertex} -> b
    end)
  end
  
  @empty MapSet.new([])
  def bron_kerbosch(g) do
    neighbor_set = fn v ->
      neighbors(g, v)  |> MapSet.new()
    end
    bron_kerbosch(MapSet.new, g.nodes, MapSet.new, neighbor_set, [])
  end
  
  def bron_kerbosch(r,o,o,_,acc) when o == @empty, do: [r | acc]
  def bron_kerbosch(_,o,_,_,acc) when o == @empty, do: acc
  def bron_kerbosch(r,p,x,n,acc) do
    for v <- p,
      n_v = n.(v),
      reduce: {p, x, acc} do
      {p, x, acc} -> 
        acc = bron_kerbosch(MapSet.put(r, v), MapSet.intersection(p, n_v), MapSet.intersection(x, n_v), n, acc)
        {p |> MapSet.delete(v), x |> MapSet.put(v), acc}
      end |> elem(2)
  end

  def parse(input), do: input 
    |> String.split("\n", trim: true)
    |> Stream.map(fn <<a::binary-size(2)>> <> "-" <> <<b::binary-size(2)>> ->
      {a |> String.to_atom, b |> String.to_atom}
    end)
    |> Enum.reduce(%LANGraph{}, fn e, acc -> LANGraph.add_edge(acc, e) end)

  def part1(input) do
    connections = input |> parse()
      
    t_nodes = connections.nodes|> Stream.filter(&String.starts_with?(Atom.to_string(&1), "t")) |> Enum.into(MapSet.new)
    three_cycles = connections 
      |> LANGraph.cycles(3)
      |> Enum.map(&Enum.into(&1, MapSet.new())) 
      |> Enum.into(MapSet.new)
    three_cycles
      |> Stream.filter(&Enum.any?(t_nodes, fn t -> MapSet.member?(&1, t) end))
      |> Enum.count()
  end

  def part2(input) do
    input
    |> parse() 
    |> bron_kerbosch()
    |> Enum.max_by(&MapSet.size/1)
    |> Stream.map(&Atom.to_string/1)
    |> Enum.sort 
    |> Enum.join(",")
  end
end

Input

input = """
"""

connections = input |> String.split("\n", trim: true)
|> Stream.map(fn <<a::binary-size(2)>> <> "-" <> <<b::binary-size(2)>> ->
  {a |> String.to_atom, b |> String.to_atom}
end)
|> Enum.reduce(%LANGraph{}, fn e, acc -> LANGraph.add_edge(acc, e) end)

Solution

LANGraph.part1(input)

LANGraph.part2(input)