Day 25 - Advent of Code 2023

""" day_25_01.py """

# usage: python3 day_25_01.py < input

# ----------------------------------------------------------------------
# note: terminates quickly with "example" data, not so with "input" data
# ----------------------------------------------------------------------

import sys
from itertools import combinations


raw = {}

for line in sys.stdin:
    u, v = line.split(': ')
    raw[u] = v.split()

components = {}

for u, v in raw.items():
    k = components.get(u, set())
    k = k.union(v)
    components[u] = k

    for i in k:
        j = components.get(i, set())
        j = j.union(set([u]))
        components[i] = j

for u in combinations(combinations(components, 2), 3):
    explore = [list(components)[0]]
    visited = []
    while explore:
        piece = explore.pop()
        visited.append(piece)
        for i in components[piece]:
            if i not in explore and i not in visited:
                if (piece, i) not in u and (i, piece) not in u:
                    explore.append(i)
    if len(visited) < len(components):
        break

print(len(visited) * (len(components) - len(visited)))