AoC '23 day 25

p1-4-2.py

# Somewhat faster by recording when sets are known to be separated

import itertools
from collections import defaultdict

infile = open("input.txt")
#infile = open("sample.txt")

nodes = set()

cs = defaultdict(set)

for line in infile:
    line = line.strip()
    ends = line.split()
    fr = ends[0][:-1]
    nodes.add(fr)
    for to in ends[1:]:
        cs[fr].add(to)
        cs[to].add(fr)
        nodes.add(to)

def pathing(src, dst, cuts):
    global nodes
    global cs
    come_from = {src: ""}
    to_visit = set()
    to_visit.add(src)
    while len(to_visit):
        n = to_visit.pop()
        for nn in cs[n]:
            proposed_edge = tuple(sorted((n, nn)))
            if proposed_edge in cuts:
                continue
            if nn not in come_from:
                assert(nn != n)
                come_from[nn] = n
                if nn == dst:
                    break
                to_visit.add(nn)

    if dst not in come_from:
        return None

    path = set()
    cur = dst
    while cur != src:
        prev = come_from[cur]
        path.add(tuple(sorted((cur, prev))))
        cur = prev

    return path

# If nodes A and B are in the same component, then there are at least 4 paths between them that
# share no edges in common.

nodes = list(nodes)
node_unions = {v: i for i, v in enumerate(nodes)}
node_union_count = len(nodes)

known_separate = set()

for n0, n1 in itertools.combinations(nodes, 2):
    if node_unions[n0] == node_unions[n1]:
        continue
    if frozenset([node_unions[n0], node_unions[n1]]) in known_separate:
        continue

    path = set()
    exclude = set()
    for _ in range(4):
        exclude.update(path)
        path = pathing(n0, n1, exclude)
        if path is None:
            break

    if path is None:
        known_separate.add(frozenset([node_unions[n0], node_unions[n1]]))
    else:
        # merge nodes
        node_union_count -= 1
        print(node_union_count)
        sys.stdout.flush()

        to_replace = node_unions[n1]
        to_replace_with = node_unions[n0]

        for k in node_unions:
            if node_unions[k] == to_replace:
                node_unions[k] = to_replace_with
        known_separate = set((s - frozenset([to_replace])).union(frozenset([to_replace_with])) if to_replace in s else s for s in known_separate)

root_ids = set(node_unions.values())
union0, union1 = iter(root_ids)

union0_size = sum(1 if v == union0 else 0 for v in node_unions.values())
union1_size = sum(1 if v == union1 else 0 for v in node_unions.values())
print(union0_size, union1_size)
print(union0_size * union1_size)

p1-4.py

# Initial random impl

import itertools
import random
import sys
from collections import defaultdict

infile = open("input.txt")
#infile = open("sample.txt")

nodes = set()

cs = defaultdict(set)

for line in infile:
    line = line.strip()
    ends = line.split()
    fr = ends[0][:-1]
    nodes.add(fr)
    for to in ends[1:]:
        cs[fr].add(to)
        cs[to].add(fr)
        nodes.add(to)

def pathing(src, dst, cuts):
    global nodes
    global cs
    come_from = {src: ""}
    to_visit = set()
    to_visit.add(src)
    while len(to_visit):
        n = to_visit.pop()
        for nn in cs[n]:
            proposed_edge = tuple(sorted((n, nn)))
            if proposed_edge in cuts:
                continue
            if nn not in come_from:
                assert(nn != n)
                come_from[nn] = n
                if nn == dst:
                    break
                to_visit.add(nn)

    if dst not in come_from:
        return None

    path = set()
    cur = dst
    while cur != src:
        prev = come_from[cur]
        path.add(tuple(sorted((cur, prev))))
        cur = prev

    return path

# If nodes A and B are in the same component, then there are at least 4 paths between them that
# share no edges in common.

nodes = list(nodes)
node_unions = {v: i for i, v in enumerate(nodes)}
node_union_count = len(nodes)

while node_union_count > 2:
    n0, n1 = random.sample(nodes, 2)
    if node_unions[n0] == node_unions[n1]:
        continue

    path = set()
    exclude = set()
    for _ in range(4):
        exclude.update(path)
        path = pathing(n0, n1, exclude)
        if path is None:
            break

    if path is not None:
        print(node_union_count)
        sys.stdout.flush()
        # merge nodes
        node_union_count -= 1
        to_replace = node_unions[n1]
        to_replace_with = node_unions[n0]

        for k in node_unions:
            if node_unions[k] == to_replace:
                node_unions[k] = to_replace_with

root_ids = set(node_unions.values())
union0, union1 = iter(root_ids)

union0_size = sum(1 if v == union0 else 0 for v in node_unions.values())
union1_size = sum(1 if v == union1 else 0 for v in node_unions.values())
print(union0_size, union1_size)
print(union0_size * union1_size)