Advent Of Code 2024 Day 23

from pathlib import Path
from collections import defaultdict


def parse(input: str) -> list[tuple[str, str]]:
    return [s.split("-", 1) for s in input.splitlines()]


def part1(data: list[tuple[str, str]]) -> int:
    connections: dict[str, set[str]] = defaultdict(set)
    for a, b in data:
        connections[a].add(b)
        connections[b].add(a)

    groups: set[frozenset[str]] = set()
    for a in connections:
        for b in connections[a]:
            for c in (connections[a] & connections[b]) - {a, b}:
                groups.add(frozenset([a, b, c]))

    tcomputers = {a for a in connections if a.startswith("t")}
    tgroups = {g for g in groups if g & tcomputers}
    return len(tgroups)


def merge_groups(
    groups: set[frozenset[str]], connections: dict[str, set[str]]
) -> set[frozenset[str]]:
    merged: set[frozenset[str]] = set()
    for g1 in groups:
        mx = max(g1)
        for c in connections:
            if c > mx and (g1 & connections[c]) == g1:
                merged.add(frozenset(g1 | {c}))
    return merged


def part2(data: list[str]) -> str:
    connections: dict[str, set[str]] = defaultdict(set)
    for a, b in data:
        connections[a].add(b)
        connections[b].add(a)

    groups: set[frozenset[str]] = set()
    for a in connections:
        for b in connections[a]:
            for c in (connections[a] & connections[b]) - {a, b}:
                groups.add(frozenset([a, b, c]))
    print("triples", len(groups))

    while len(groups) > 1:
        merged = merge_groups(groups, connections)
        if merged:
            print(f"{len(merged)=}")
            groups = merged
        else:
            break
    print(f"{len(groups)=}")
    for g in groups:
        return ",".join(sorted(g))


TEST = parse(Path("input/day23-test.txt").read_text())
assert part1(TEST) == 7
INPUT = parse(Path("input/day23.txt").read_text())
part1_total = part1(INPUT)
print(f"{part1_total=:,}")

assert part2(TEST) == "co,de,ka,ta"
part2_total = part2(INPUT)
print(f"{part2_total=}")  # ab,cp,ep,fj,fl,ij,in,ng,pl,qr,rx,va,vf