Advent of Code 2024, Day 23

For part 2, I used a naive algorithm that iteratively extends cliques. It takes around 20 seconds on my machine.

I later learned about the Bron–Kerbosch algorithm, which, even in its basic form, reduced the running time to about 0.3 seconds. This was another instance where I learned a new algorithm through Advent of Code; I had also learned about the shoelace formula through Advent of Code last year.

I also find it remarkable that the puzzle answer was not only a tuple (instead of a single element), but a tuple of strings (instead of integers).

Part 1

import sys

links = {}
with open(sys.argv[1]) as f:
    for line in f:
        a, b = line.strip().split("-")
        links.setdefault(a, set()).add(b)
        links.setdefault(b, set()).add(a)

triples = set()
for a in links:
    for b in links[a]:
        for c in links[b]:
            if c == a: continue
            if a not in links[c]: continue
            if "t" not in (a[0], b[0], c[0]): continue
            triples.add(tuple(sorted([a, b, c])))

print(len(triples))

Part 2, naive

import sys

links = {}
with open(sys.argv[1]) as f:
    for line in f:
        a, b = line.strip().split("-")
        links.setdefault(a, set()).add(b)
        links.setdefault(b, set()).add(a)

cliques = set()
frontier = {(node,) for node in links}
while len(frontier) > 0:
    print(len(cliques), "done", len(frontier), "to do")
    new = set()
    for clique in frontier:
        for node in links:
            if links[node].issuperset(clique):
                new.add(tuple(sorted(clique + (node,))))
    cliques.update(frontier)
    frontier = new

print(",".join(max(cliques, key=len)))

Part 2, Bron–Kerbosch

import sys

N = {}
with open(sys.argv[1]) as f:
    for line in f:
        a, b = line.strip().split("-")
        N.setdefault(a, set()).add(b)
        N.setdefault(b, set()).add(a)

C = []
def BK(R, P, X):
    if not P and not X:
        C.append(sorted(R))
    for v in P.copy():
        BK(R | {v}, P & N[v], X & N[v])
        P -= {v}
        X |= {v}

BK(set(), set(N), set())
print(",".join(max(C, key=len)))

2024-12-23