Warning: Some posts on this platform may contain adult material intended for mature audiences only. Viewer discretion is advised. By clicking ‘Continue’, you confirm that you are 18 years or older and consent to viewing explicit content.
(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 python3import 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]))
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