Day 23: LAN Party

by @scarf005

Puzzle description

https://adventofcode.com/2024/day/23

Solution summary

The puzzle involves finding triangles and maximal cliques. The task is to determine:

• Part 1: Find the number of triangles in the graph.
• Part 2: Find the size of the largest clique in the graph.

Parsing the input

Both parts use undirected graphs, represented as:

type Connection = Map[String, Set[String]]

def parse(input: String): Connection = input
  .split('\n')
  .toSet
  .flatMap { case s"$a-$b" => Set(a -> b, b -> a) } // 1)
  .groupMap(_._1)(_._2)                             // 2)

• 1): both a -> b and b -> a are added to the graph so that the graph is undirected.
• 2): a fancier way to write groupBy(_._1).mapValues(_.map(_._2)), check the docs for details.

Part 1

The goal is to find triangles that have a computer whose name starts with t. This could be checked by simply checking whether all three vertices are connected to each other, like:

// connection: Connection

extension (a: String)
  inline infix def <->(b: String) =
    connection(a).contains(b) && connection(b).contains(a)

def isValidTriangle(vertices: Set[String]): Boolean = vertices.toList match
  case List(a, b, c) => a <-> b && b <-> c && c <-> a
  case _             => false

Then it's just a matter of getting all neighboring vertices of each vertex and checking if they form a triangle:

def part1(input: String) =
  val connection = parse(input)

  extension (a: String)
    inline infix def <->(b: String) =
      connection(a).contains(b) && connection(b).contains(a)

  def isValidTriangle(vertices: Set[String]): Boolean = vertices.toList match
    case List(a, b, c) => a <-> b && b <-> c && c <-> a
    case _             => false

  connection
    .flatMap { (vertex, neighbors) =>
      neighbors
        .subsets(2)                               // 1)
        .map(_ + vertex)                          // 2)
        .withFilter(_.exists(_.startsWith("t")))
        .filter(isValidTriangle)
    }
    .toSet
    .size

• 1): chooses two neighbors...
• 2) ...and adds the vertex itself to form a triangle.

Part 2

This part is more complex, but there's a generalization of the problem: finding the size of the largest clique in the graph. We'll skip the explanation of the algorithm, but here's the code:

def findMaximumCliqueBronKerbosch(connections: Connection): Set[String] =
  def bronKerbosch(
    potential: Set[String],
    excluded: Set[String] = Set.empty,
    result: Set[String] = Set.empty,
  ): Set[String] =
    if (potential.isEmpty && excluded.isEmpty) then result
    else
      // Choose pivot to minimize branching
      val pivot = (potential ++ excluded)
        .maxBy(vertex => potential.count(connections(vertex).contains))

      val remaining = potential -- connections(pivot)

      remaining.foldLeft(Set.empty[String]) { (currentMax, vertex) =>
        val neighbors = connections(vertex)
        val newClique = bronKerbosch(
          result = result + vertex,
          potential = potential & neighbors,
          excluded = excluded & neighbors,
        )
        if (newClique.size > currentMax.size) newClique else currentMax
      }

  bronKerbosch(potential = connections.keySet)

Then we could map them over to get the password:

def part2(input: String) =
  val connection = parse(input)
  findMaximumCliqueBronKerbosch(connection).toList.sorted.mkString(",")

Final code

type Connection = Map[String, Set[String]]

def parse(input: String): Connection = input
  .split('\n')
  .toSet
  .flatMap { case s"$a-$b" => Set(a -> b, b -> a) }
  .groupMap(_._1)(_._2)

def part1(input: String) =
  val connection = parse(input)

  extension (a: String)
    inline infix def <->(b: String) =
      connection(a).contains(b) && connection(b).contains(a)

  def isValidTriangle(vertices: Set[String]): Boolean = vertices.toList match
    case List(a, b, c) => a <-> b && b <-> c && c <-> a
    case _             => false

  connection
    .flatMap { (vertex, neighbors) =>
      neighbors
        .subsets(2)
        .map(_ + vertex)
        .withFilter(_.exists(_.startsWith("t")))
        .filter(isValidTriangle)
    }
    .toSet
    .size

def part2(input: String) =
  val connection = parse(input)
  findMaximumCliqueBronKerbosch(connection).toList.sorted.mkString(",")

def findMaximumCliqueBronKerbosch(connections: Connection): Set[String] =
  def bronKerbosch(
    potential: Set[String],
    excluded: Set[String] = Set.empty,
    result: Set[String] = Set.empty,
  ): Set[String] =
    if (potential.isEmpty && excluded.isEmpty) then result
    else
      // Choose pivot to minimize branching
      val pivot = (potential ++ excluded)
        .maxBy(vertex => potential.count(connections(vertex).contains))

      val remaining = potential -- connections(pivot)

      remaining.foldLeft(Set.empty[String]) { (currentMax, vertex) =>
        val neighbors = connections(vertex)
        val newClique = bronKerbosch(
          result = result + vertex,
          potential = potential & neighbors,
          excluded = excluded & neighbors,
        )
        if (newClique.size > currentMax.size) newClique else currentMax
      }

  bronKerbosch(potential = connections.keySet)

Solutions from the community

• Solution by Artem Nikiforov
• Solution by merlinorg
• Solution by Antoine Amiguet
• Solution by Raphaël Marbeck
• Writeup by Bulby
• Solution by Philippus Baalman
• Solution by Paweł Cembaluk

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format