sjmulder

Python (Not C...)

(Posting from an alt because SDF is having issues)

A graph problem 😬​. There are well-known algorithms but none trivial to implement in C.

I tried dividing the nodes into two groups and then moving the node with the worst in-group/out-group edge balance - a Wish version of the Kernighan-Lin algorithm. As expected, it got stuck in a local optimum for the real input and random prodding didn't help.

Programming is programming and libraries are fair game so I went to Python and used NetworkX which was my first time using the library but so easy to use! Maybe I'll go back and do it in C someday and implement the algorithm myself.

#!/usr/bin/env python3
import sys
import re
from networkx import Graph
from networkx.algorithms.community import greedy_modularity_communities

G = Graph()

for line in sys.stdin.readlines():
  words = re.findall("\\w+", line)
  for to in words[1:]:
    G.add_edge(words[0], to)

coms = greedy_modularity_communities(G, best_n=2)

print("25:", len(coms[0]) * len(coms[1]))

https://github.com/sjmulder/aoc/tree/master/2023/python/day25.py