Advent of Code 2024: Day 23

For day 23 we’re going to look for cliques in a graph. A clique is a subset of vertices in a graph such that every pair of vertices in the clique is connected by an edge. In other words, a clique is a complete subgraph of the graph.

The graph is given as a list of edges. The graph is undirected, so the edge (a, b) is the same as the edge (b, a). We represent the graph as a hash table mapping vertices to a list of adjacent vertices.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY23")

(defun get-input (input-pathname)
  (let ((neighbor-table (make-hash-table :test #’eql))
        (package (find-package "ADVENT2024/DAY23")))
    (iterate (((left right) (#2M(lambda (line) (values-list (str:split #\- line)))
                                (scan-file input-pathname #’read-line))))
      (let ((left*  (intern (string-upcase left)  package))
            (right* (intern (string-upcase right) package)))
        (push right* (gethash left* neighbor-table ’()))
        (push left* (gethash right* neighbor-table ’()))))
  neighbor-table))

Given a neighbor table, we can get a list of the two vertex cliques by looking at the keys and values of the hash table.

(defun two-vertex-cliques (neighbor-table)
  (collect-append
   (mapping (((vertex neighbors) (scan-hash neighbor-table)))
     (mappend (lambda (neighbor)
                (when (string-lessp (symbol-name vertex) (symbol-name neighbor))
                  (list (list vertex neighbor))))
              neighbors))))

Given a two vertex clique, we can find a three vertex clique by looking for a vertex that is connected to both vertices in the two vertex clique. We find the neighbors of each vertex in the clique and then take the intersection of the two lists of neighbors. We distribute this intersection over the two vertex clique to get the list of three vertex cliques. Note that each three vertex clique will appear three times in the list in different orders.

In Part 1, we count the number of three vertex cliques in the graph where one of the vertices begins with the letter ‘T’. We divide by three because we generate three vertex cliques in triplicate.

(defun part-1 ()
  (/ (count-if (lambda (clique)
                 (find-if (lambda (sym)
                            (char= #\T (char (symbol-name sym) 0)))
                          clique))
               (let ((neighbor-table (get-input (input-pathname))))
                 (mappend (lambda (clique)
                            (let ((left-neighbors (gethash (first clique) neighbor-table))
                                  (right-neighbors (gethash (second clique) neighbor-table)))
                              (map ’list (lambda (common-neighbor) (list* common-neighbor clique))
                                   (intersection left-neighbors right-neighbors))))
                          (two-vertex-cliques neighbor-table))))
     3))

For Part 2, we are to find the largest maximal clique. We use the Bron-Kerbosch algorithm to find the maximal cliques.

(defun bron-kerbosch (graph-vertices clique more-vertices excluded-vertices)
  (if (and (null more-vertices) (null excluded-vertices))
      (list clique)
      (let iter ((answer '())
                 (excluded-vertices excluded-vertices)
                 (more-vertices more-vertices))
        (if (null more-vertices)
            answer
            (let* ((this-vertex (car more-vertices))
                   (more-vertices* (cdr more-vertices))
                   (neighbors (gethash this-vertex graph-vertices)))
              (iter (append (bron-kerbosch graph-vertices
                                           (adjoin this-vertex clique)
                                           (intersection more-vertices* neighbors)
                                           (intersection excluded-vertices neighbors))
                            answer)
                (adjoin this-vertex excluded-vertices)
                more-vertices*))))))

(defun maximal-cliques (graph-vertices)
  (bron-kerbosch graph-vertices ’() (hash-table-keys graph-vertices) ’()))

Once we have found the maximal cliques, we can find the largest clique by sorting the cliques by length and taking the first one. We sort the vertices in the clique and print as a comma separated list.

(defun part-2 ()
  (format
   nil "~{~a~^,~}"
   (sort
    (first
     (sort
      (maximal-cliques (get-input (input-pathname)))
      #’> :key #’length))
    #’string-lessp :key #’symbol-name)))