Interaction Combinators (39% ugly)

ic.py

import itertools


port = itertools.count()


wires = dict[int, int]()
cells = dict[int, tuple[str, int, tuple[int, ...]]]()
queue = set[tuple[int, int]]()


def wire() -> tuple[int, int]:
    a, b = next(port), next(port)
    wires[a], wires[b] = b, a
    return a, b


def join(first: int, second: int) -> None:
    queue.update({(wires[first], wires[second]), (wires[second], wires[first])})
    wires[wires.pop(first)], wires[wires.pop(second)] = wires[second], wires[first]


def cut(first: int, second: int) -> None:
    del cells[first]; del cells[second]
    del wires[first]; del wires[second]


def cell(s: str, arity: int) -> tuple[int, tuple[int, ...]]:
    p, xs = wire(), tuple(wire() for _ in range(arity))
    cells[p[0]] = (s, p[0], tuple(x[0] for x in xs))
    return p[1], tuple(x[1] for x in xs)


def constructor() -> tuple[int, tuple[int, ...]]:
    return cell("γ", 2)


def duplicator() -> tuple[int, tuple[int, ...]]:
    return cell("δ", 2)


def eraser() -> tuple[int, tuple[int, ...]]:
    return cell("ε", 0)


def multiplexor(n: int) -> tuple[int, tuple[int, ...]]:
    match n:
        case 0:
            e_p, () = eraser()
            return e_p, ()
        case _:
            m_p, m_xs = multiplexor(n - 1)
            c_p, (c_l, c_r) = constructor()
            join(m_p, c_r)
            return c_p, (c_l, *m_xs)


def demultiplexor(n: int) -> tuple[int, tuple[int, ...]]:
    match n:
        case 0:
            e_p, () = eraser()
            return e_p, ()
        case _:
            m_p, m_xs = demultiplexor(n - 1)
            c_p, (c_l, c_r) = constructor()
            join(m_p, c_l)
            return c_p, (*m_xs, c_r)


def autodual(n: int) -> tuple[int, tuple[int, ...]]:
    match n:
        case 0:
            e_p, () = eraser()
            return e_p, ()
        case _:
            m_p, m_xs = autodual(n - 1)
            d_p, (d_l, d_r) = duplicator()
            join(m_p, d_r)
            return d_p, (d_l, *m_xs)


def transpositor(p: int, q: int) -> tuple[int, tuple[int, ...]]:
    cs_xs = list[int]()
    m_p, m_xs = autodual(p + q)
    for (c_p, (c_l, c_r)), m_x in zip((constructor() for _ in range(p)), m_xs):
        cs_xs.extend([c_l, c_r])
        join(c_p, m_x)
    return m_p, (*cs_xs, *m_xs[p:])


def menu(*packages: int) -> tuple[int, tuple[int, ...]]:
    m_p, m_xs = multiplexor(len(packages))
    for package, m_x in zip(packages, m_xs):
        join(package, m_x)
    return m_p, ()


def selector(length: int, index: int) -> tuple[int, tuple[int, ...]]:
    m_p, m_xs = demultiplexor(length)
    for m_x in (*m_xs[:index], *m_xs[index + 1:]):
        e_p, () = eraser()
        join(e_p, m_x)
    return m_p, (m_xs[index],)


def print_net() -> None:
    id = itertools.count()
    port_to_id = dict[int, int]()
    for a, b in wires.items():
        if a not in port_to_id:
            port_to_id[a] = port_to_id[b] = next(id)

    for s, p, xs in cells.values():
        print(f"{s}{tuple(port_to_id[x] for x in xs)} → {port_to_id[p]}")


def interact(first: tuple[str, int, tuple[int, ...]], second: tuple[str, int, tuple[int, ...]]) -> None:
    match first, second:
        case ("γ", c_p, (c_l, c_r)), ("ε", e_p, ()):
            cut(c_p, e_p)
            (e1_p, ()), (e2_p, ()) = eraser(), eraser()
            join(c_l, e1_p); join(c_r, e2_p)
        case ("δ", d_p, (d_l, d_r)), ("ε", e_p, ()):
            cut(d_p, e_p)
            (e1_p, ()), (e2_p, ()) = eraser(), eraser()
            join(d_l, e1_p); join(d_r, e2_p)
        case ("γ", c_p, (c_l, c_r)), ("δ", d_p, (d_l, d_r)):
            cut(c_p, d_p)
            (d1_p, (d1_l, d1_r)), (d2_p, (d2_l, d2_r)) = duplicator(), duplicator()
            (c1_p, (c1_l, c1_r)), (c2_p, (c2_l, c2_r)) = constructor(), constructor()
            join(c_l, d1_p); join(c_r, d2_p)
            join(d1_l, c1_l); join(d1_r, c2_l); join(d2_l, c1_r); join(d2_r, c2_r)
            join(c1_p, d_l); join(c2_p, d_r)

        case ("γ", c1_p, (c1_l, c1_r)), ("γ", c2_p, (c2_l, c2_r)):
            cut(c1_p, c2_p)
            join(c1_l, c2_r); join(c1_r, c2_l)
        case ("δ", d1_p, (d1_l, d1_r)), ("δ", d2_p, (d2_l, d2_r)):
            cut(d1_p, d2_p)
            join(d1_l, d2_l); join(d1_r, d2_r)
        case ("ε", e1_p, ()), ("ε", e2_p, ()):
            cut(e1_p, e2_p)

        case _:
            pass


def reduce() -> None:
    while queue:
        a, b = queue.pop()
        if a in cells and b in cells:
            interact(cells[a], cells[b])


def init() -> None:
    m1_p, m1_xs = multiplexor(5)
    m2_p, m2_xs = demultiplexor(5)
    join(m1_p, m2_p)


def main() -> None:
    init()

    print("Non-reduced:")
    print_net()

    print()
    print(f"Wires: {wires}")
    print(f"Cells: {cells}")

    print()
    reduce()

    print("Reduced:")
    print_net()

    print()
    print(f"Wires: {wires}")
    print(f"Cells: {cells}")


main()