Midnight Code Cup 2025 problem D (DSL Strikes Back), post-contest solutions

lib.py

"""Helper library to give the DSL a nicer syntax. See e.g. sum-loop.py for example usage."""
from collections import Counter
import inspect
import typing

ctr = 0
def name(tp):
    global ctr
    ctr += 1
    return f"{tp}_{ctr}"

initial_rule = None

types = []
rules = []

new_nodes = []
new_edges = []

types_map = {}

class Tag:
    def __init__(self, r): self.r = r
    def __str__(self): return self.r
    def __lt__(self, other): return cond(f"{self}<{other}")
    def __gt__(self, other): return cond(f"{self}>{other}")
    def __le__(self, other): return cond(f"{self}<={other}")
    def __ge__(self, other): return cond(f"{self}>={other}")
    def __eq__(self, other): return cond(f"{self}=={other}")
    def __ne__(self, other): return cond(f"{self}!={other}")
    def __lshift__(self, other): return f"{self}<<{other}"
    def __rshift__(self, other): return f"{self}>>{other}"
    def __mod__(self, other): return f"{self}%{other}"
    def __mul__(self, other): return f"{self}*{other}"
    def __add__(self, other): return f"{self}+{other}"
    def __sub__(self, other): return f"{self}-{other}"
    def __div__(self, other): return f"{self}/{other}"
    def __or__(self, other): return f"{self}|{other}"
    def __and__(self, other): return f"{self}&{other}"
    def __xor__(self, other): return f"{self}^{other}"
    def __rlshift__(self, other): return f"{other}<<{self}"
    def __rrshift__(self, other): return f"{other}>>{self}"
    def __rmod__(self, other): return f"{other}%{self}"
    def __rmul__(self, other): return f"{other}*{self}"
    def __radd__(self, other): return f"{other}+{self}"
    def __rsub__(self, other): return f"{other}-{self}"
    def __rdiv__(self, other): return f"{other}/{self}"
    def __ror__(self, other): return f"{other}|{self}"
    def __rand__(self, other): return f"{other}&{self}"
    def __rxor__(self, other): return f"{other}^{self}"

def edge(a, b):
    new_edges.append(f"{a}-{b}")

def add_type(type_name, active, *edges, prop=[]):
    assert edges, f"{type_name} does not have any edges"
    for n, c in Counter(edges).items():
        assert c == 1, f"duplicate edge name {n} in {type_name}"
    class C:
        _type_name = type_name
        def __init__(self, tag, *args):
            if isinstance(tag, (int, str, Tag)):
                tag = str(tag)
            else:
                raise Exception(f"failed to pass tag to {type_name}")
            self._name = name(type_name)
            new_nodes.append(f"{self._name} {type_name} {tag}")
            self._edges = edges
            for i, e in enumerate(edges):
                setattr(self, e, f"{self._name}.{i}")
            if args:
                assert len(args) >= len(edges), f"missing arguments when constructing {type_name}"
                assert len(args) <= len(edges), f"too many arguments when constructing {type_name}"
            for a, e in zip(args, edges):
                if a is ...:
                    continue
                n = getattr(self, e)
                if not isinstance(a, str):
                    a = getattr(a, a._edges[0])
                edge(n, a)
        @staticmethod
        def _make_initial(side):
            arg = C("tag", *([...] * len(edges)))
            for i in range(len(edges)):
                setattr(arg, edges[i], f"{side}{i}")
            setattr(arg, "tag", Tag(f"{side}_tag"))
            return arg
    C.__name__ = type_name
    types_map[type_name] = C
    inspect.getmodule(inspect.stack()[1][0]).__dict__[type_name] = C
    types.append((type_name, len(edges), active, prop))
    return C

def rule(fn):
    global the_cond, cond_val
    cond = "ALWAYS"
    types = list(typing.get_type_hints(fn).values())
    lhs_t = types[0]
    rhs_t = types[1]
    lhs = lhs_t._make_initial("lhs")
    rhs = rhs_t._make_initial("rhs")
    del new_nodes[:]
    del new_edges[:]
    the_cond = None
    cond_val = True
    fn(lhs, rhs)
    s = format_rule()
    if the_cond is not None:
        cond = the_cond
        cond_val = False
        fn(lhs, rhs)
        s += "\n" + format_rule()
    rules.append(f"{lhs_t._type_name} {rhs_t._type_name} {cond}\n" + s)

def initial(fn):
    global initial_rule
    assert initial_rule is None, "just one @initial allowed"
    del new_nodes[:]
    del new_edges[:]
    fn()
    initial_rule = format_rule()


def format_rule():
    s = f"{len(new_nodes)} {len(new_edges)}"
    for n in new_nodes:
        s += "\n" + n
    for n in new_edges:
        s += "\n" + n
    del new_nodes[:]
    del new_edges[:]
    return s

def cond(expr):
    global the_cond
    the_cond = expr
    return cond_val

add_type("INP", False, "out")
add_type("OUT", True, "out")
add_type("ERA", True, "out")
del types[:]

def finish():
    print(len(types))
    for tp in types:
        print(tp[0], tp[1], str(tp[2]).lower(), *tp[3])

    print(len(rules))
    for rule in rules:
        print(rule)

    assert initial_rule is not None
    print(initial_rule)

sort-bubble.py

# Bubble sort, using a circularly linked list. This roughly ties the best entry in code size.
from lib import *

add_type("START", True, "n")  # [0]
add_type("SETUP", True, "inp", "right", "eof")  # [ind]
add_type("EOF", True, "left", "right")  # [ind]
add_type("BLUE", True, "right", "left")  # [val]
add_type("RED", True, "left", "right")  # [val]

@initial
def f():
    START(0, INP(0))

@rule
def f(s: START, n: INP):
    e = EOF(n.tag - 1)
    SETUP(n.tag - 1, INP(n.tag), e.right, e)

@rule
def f(s: SETUP, i: INP):
    if s.tag >= 0:
        red = RED(i.tag)
        SETUP(s.tag - 1, INP(s.tag), red, s.eof)
        edge(red.right, s.right)
    else:
        BLUE(-2**63, s.right, s.eof)

@rule
def f(e: EOF, r: RED):
    EOF(e.tag, e.right, BLUE(r.tag, r.right, ...).left)

@rule
def f(lhs: BLUE, rhs: RED):
    low, high = lhs.tag, rhs.tag
    if not (lhs.tag < rhs.tag):
        low, high = high, low
    RED(low, lhs.left, BLUE(high, rhs.right, ...).left)

@rule
def f(b: BLUE, e: EOF):
    OUT(e.tag, START(b.tag))
    EOF(e.tag - 1, e.right, b.left)

finish()

sort-instaprop.py

# Sorting in O(1) parallel time by abusing activation propagation along secondary edges.
# For each input we count how many other inputs are smaller than it to find its output position,
# using a network like the following for summation, where every node propagates activity either
# down-right to add +1 to the sum, or right to add +0.
#
# o - o - o - o
#   \   \   \
#     o - o - o
#       \   \
#         o - o
#           \
#             o
from lib import *

maxn = 50

add_type("READB", True, "n", "out")  # [i+1]
add_type("READB2", True, "inp", "out")  # [0]
add_type("READC", True, "n", "out")  # [i+1]
add_type("READC2", True, "inp", "out")  # [0]
add_type("READVAL", False, "out")  # [val]
add_type("OUTPUT", False, "val", "source")  # [i]
add_type("EMPTY", False, "out")  # [0]
add_type("ADD0", False, "dummy", "fromlt", "fromeq", "togt", "toeq", prop=[4])  # [0]
add_type("ADD1", False, "dummy", "fromlt", "fromeq", "togt", "toeq", prop=[3])  # [0]

reada = {
    cmp: [
        [
            add_type(f"READA{cmp}{i}_{j}", True, *(["n"] * (j < 2)), "b",
                *[f"fromlt{k}" for k in range(1, i+1)],
                *[f"fromeq{k}" for k in range(i)],
                *[f"toeq{k}" for k in range(i+1)],
                *[f"togt{k}" for k in range(i+1)],
            )  # [i+1] / [0] / [val]
            for j in range(3)
        ]
        for i in range(maxn)
    ]
    for cmp in ("GT", "GE")
}

@initial
def f():
    for i in range(maxn):
        li = []
        for j in range(maxn):
            n1 = INP(0)
            n2 = INP(0)

            cmp = "GT" if i <= j else "GE"
            ai = reada[cmp][j][0](i+1)
            bi = READC(j+1, INP(0), ai.b)
            INP(0, ai)
            li.append(ai)

        for j in range(maxn-1):
            for k in range(j+1):
                edge(getattr(li[j], f"toeq{k}"), getattr(li[j+1], f"fromeq{k}"))
                edge(getattr(li[j], f"togt{k}"), getattr(li[j+1], f"fromlt{k+1}"))
        outs = [[None, None] for _ in range(maxn+1)]
        for j in range(maxn+1):
            for k in range(2):
                if (j == 0 and k == 1) or (j == maxn and k == 0):
                    continue
                v = READB(i+1, INP(0), ...)
                outs[j][k] = OUTPUT(j, v.out, ...)
        for k in range(maxn):
            edge(getattr(li[maxn-1], f"toeq{k}"), outs[k][0].source)
            edge(getattr(li[maxn-1], f"togt{k}"), outs[k+1][1].source)


@rule
def f(n: INP, r: READB):
    if r.tag <= n.tag:
        READB2(0, INP(r.tag), r.out)
    else:
        EMPTY(0, r.out)

@rule
def f(n: INP, r: READB2):
    READVAL(n.tag, r.out)

@rule
def f(n: INP, r: READC):
    if r.tag <= n.tag:
        READC2(0, INP(r.tag), r.out)
    else:
        # Pad input array with max possible value on the right.
        # Since we do a stable sort, this value will not make a difference.
        READVAL(2**63-1, r.out)

@rule
def f(n: INP, r: READC2):
    READVAL(n.tag, r.out)

@rule
def f(o: OUTPUT, e: EMPTY):
    ERA(0, o.source)

@rule
def f(o: OUTPUT, v: READVAL):
    ERA(0, o.source)
    OUT(o.tag, READVAL(v.tag))

for cmp in ("GT", "GE"):
    for i in range(maxn):
        READA, READA2, READVALA = reada[cmp][i]

        @rule
        def f(n: INP, r: READA):
            if r.tag <= n.tag:
                index = r.tag
            else:
                # Don't care, we won't write the result anyway.
                # Pick something valid to reduce special-casing.
                index = 0
            val = READA2(0)
            INP(index, val)
            for e in r._edges[1:]:
                edge(getattr(r, e), getattr(val, e))

        @rule
        def f(n: INP, r: READA2):
            val = READVALA(n.tag)
            for e in r._edges[1:]:
                edge(getattr(r, e), getattr(val, e))

        @rule
        def f(a: READVALA, b: READVAL):
            if (a.tag > b.tag if cmp == "GT" else a.tag >= b.tag):
                tp = ADD1
            else:
                tp = ADD0
            dummy1 = OUT(0) if i == 0 else ERA(0)
            dummy2 = ERA(0)
            for j in range(i+1):
                fromlt = getattr(a, f"fromlt{j}") if j > 0 else dummy1
                fromeq = getattr(a, f"fromeq{j}") if j != i else dummy2
                togt = getattr(a, f"togt{j}")
                toeq = getattr(a, f"toeq{j}")
                tp(0, ERA(0), fromlt, fromeq, togt, toeq)

finish()

sort-quick.py

# Sorting in O(n log n). This is competitive with the fastest solution in serial time.
from lib import *

add_type("INIT", True, "n")  # [0]
add_type("COMPLETE", False, "par")  # [0]
add_type("MAKELIST", True, "inp", "right")  # [ind]
add_type("EOF", True, "left", "out")  # [0]
add_type("START", True, "red")  # [ind]
add_type("DONE", False, "par")  # [ind]
add_type("STATE", False, "par", "lt_start", "gt_start")  # [ind]
add_type("REC", True, "state", "lt_end", "gt_end", "out")  # [midval]
add_type("RECMID", True, "done", "gt_start", "gt_end", "out")  # [midval]
add_type("BLUE", True, "right", "lt", "gt", "state")  # [val]
add_type("RED", True, "left", "right")  # [val]
add_type("EPS", True, "left", "right")  # [0]

# START <- RED <- RED <- ... <- RED <- EOF [ind] <- out
# processes to:
# DONE [newind] -> out

@initial
def f():
    INIT(0, INP(0))

@rule
def f(s: INIT, n: INP):
    MAKELIST(n.tag - 1, INP(n.tag), EOF(0, ..., COMPLETE(0)))

@rule
def f(m: MAKELIST, i: INP):
    if m.tag >= 0:
        red = RED(i.tag)
        MAKELIST(m.tag - 1, INP(m.tag), red)
        edge(red.right, m.right)
    else:
        START(0, m.right)

@rule
def f(s: START, e: EOF):
    DONE(s.tag, e.out)

@rule
def f(e: START, r: RED):
    state = STATE(e.tag)
    lt_eps = EPS(0, state.lt_start, ...)
    gt_eps = EPS(0, state.gt_start, ...)
    BLUE(r.tag, r.right, lt_eps.right, gt_eps.right, state)

@rule
def f(lhs: BLUE, rhs: RED):
    if lhs.tag < rhs.tag:
        gt = RED(rhs.tag, lhs.gt, ...).right
        lt = lhs.lt
    else:
        gt = lhs.gt
        lt = RED(rhs.tag, lhs.lt, ...).right
    BLUE(lhs.tag, rhs.right, lt, gt, lhs.state)

@rule
def f(b: BLUE, e: EOF):
    REC(b.tag, b.state, b.lt, b.gt, e.out)

@rule
def f(b: START, e: EPS):
    START(b.tag, e.right)

@rule
def f(r: REC, s: STATE):
    START(s.tag, s.lt_start)
    EOF(0, r.lt_end, RECMID(r.tag, ..., s.gt_start, r.gt_end, r.out))

@rule
def f(r: RECMID, d: DONE):
    OUT(d.tag, DONE(r.tag))
    START(d.tag + 1, r.gt_start)
    EOF(0, r.gt_end, r.out)

finish()

sort-quicker.py

# Optimized quicksort, with some more state being encoded into node types. This beats the fastest solution in serial time.
from lib import *

add_type("INIT", True, "n")  # [0]
add_type("COMPLETE", False, "par")  # [0]
add_type("MAKELIST", True, "inp", "right")  # [ind]
add_type("EOF", True, "left", "out")  # [0]
add_type("START", True, "red")  # [ind]
add_type("DONE", False, "par")  # [ind]
add_type("STATE", False, "par", "lt_start", "gt_start")  # [ind]
add_type("RED", True, "left", "right")  # [val]

rec = [[None] * 3 for _ in range(3)]
blue = [[None] * 3 for _ in range(3)]

for i in range(3):
    for j in range(3):
        rec[i][j] = add_type(f"REC{i}{j}", True, "state", "lt_end", "gt_end", "out")  # [midval]
        blue[i][j] = add_type(f"BLUE{i}{j}", True, "right", "lt", "gt", "state")  # [val]

add_type("RECMID0", True, "done", "out")  # [midval]
add_type("RECMID1", True, "done", "gt", "out")  # [midval]
add_type("RECMID2", True, "done", "gt_start", "gt_end", "out")  # [midval]

# START <- RED <- RED <- ... <- RED <- EOF [ind] <- out
# processes to:
# DONE [newind] -> out

@initial
def f():
    INIT(0, INP(0))

@rule
def f(s: INIT, n: INP):
    MAKELIST(n.tag - 1, INP(n.tag), EOF(0, ..., COMPLETE(0)))

@rule
def f(m: MAKELIST, i: INP):
    if m.tag >= 0:
        red = RED(i.tag)
        MAKELIST(m.tag - 1, INP(m.tag), red)
        edge(red.right, m.right)
    else:
        START(0, m.right)

@rule
def f(s: START, e: EOF):
    DONE(s.tag, e.out)

@rule
def f(e: START, r: RED):
    state = STATE(e.tag)
    BLUE00(r.tag, r.right, state.lt_start, state.gt_start, state)

for i in range(3):
    for j in range(3):
        BLUE = blue[i][j]
        REC = rec[i][j]

        @rule
        def f(lhs: BLUE, rhs: RED):
            lt = lhs.lt
            gt = lhs.gt
            ni = i
            nj = j
            if lhs.tag < rhs.tag:
                gt = RED(rhs.tag, gt, ...).right
                nj = min(j + 1, 2)
            else:
                lt = RED(rhs.tag, lt, ...).right
                ni = min(i + 1, 2)
            blue[ni][nj](lhs.tag, rhs.right, lt, gt, lhs.state)

        @rule
        def f(b: BLUE, e: EOF):
            REC(b.tag, b.state, b.lt, b.gt, e.out)

        @rule
        def f(r: REC, s: STATE):
            if i <= 1:
                if i == 0:
                    edge(s.lt_start, r.lt_end)
                else:
                    OUT(s.tag, s.lt_start)
                    if j == 1:
                        edge(r.lt_end, r.gt_end)
                    else:
                        ERA(0, r.lt_end)
                OUT(s.tag + i, DONE(r.tag))
                if j <= 1:
                    if j == 0:
                        edge(s.gt_start, r.gt_end)
                    elif j == 1:
                        OUT(s.tag + (i+1), s.gt_start)
                        if i != 1:
                            ERA(0, r.gt_end)
                    DONE(s.tag + (i+j+1), r.out)
                else:
                    START(s.tag + (i+1), s.gt_start)
                    EOF(0, r.gt_end, r.out)
            else:
                if j == 0:
                    edge(s.gt_start, r.gt_end)
                    mid = RECMID0(r.tag, ..., r.out)
                elif j == 1:
                    ERA(0, r.gt_end)
                    mid = RECMID1(r.tag, ..., s.gt_start, r.out)
                else:
                    mid = RECMID2(r.tag, ..., s.gt_start, r.gt_end, r.out)
                START(s.tag, s.lt_start)
                EOF(0, r.lt_end, mid)

@rule
def f(r: RECMID0, d: DONE):
    OUT(d.tag, DONE(r.tag))
    DONE(d.tag + 1, r.out)

@rule
def f(r: RECMID1, d: DONE):
    OUT(d.tag, DONE(r.tag))
    OUT(d.tag + 1, r.gt)
    DONE(d.tag + 2, r.out)

@rule
def f(r: RECMID2, d: DONE):
    OUT(d.tag, DONE(r.tag))
    START(d.tag + 1, r.gt_start)
    EOF(0, r.gt_end, r.out)

finish()

sum-instaprop.py

# Summation in O(1) parallel time by abusing activation propagation along secondary edges.
# For each output digit we figure out the input carry in O(1), by building a carry chain for the next digit sums where:
# - digit sum < 9 uses a node type that never propagates carry activity
# - digit sum > 9 uses a node type that starts active and propagates carry activity along a secondary edge
# - digit sum = 9 uses a node type that starts inactive and propagates carry activity along a secondary edge if it becomes active
from lib import *

maxn = 50

add_type("READLT1", True, "a", "b", "eq_nocarry0_out", "out")  # [0]
add_type("READLT2", True, "b", "eq_nocarry0_out", "out")  # [9-a]
add_type("READGT1", True, "a", "b", "eq_carry0_out", "out")  # [0]
add_type("READGT2", True, "b", "eq_carry0_out", "out")  # [9-a]
add_type("READEQ1", True, "a", "b", "eq_nocarry0_in", "eq_nocarry1_in", "eq_carry0_in", "eq_carry1_in", "eq_nocarry1_out", "eq_carry1_out", "out0", "out1")  # [0]
add_type("READEQ2", True, "b", "eq_nocarry0_in", "eq_nocarry1_in", "eq_carry0_in", "eq_carry1_in", "eq_nocarry1_out", "eq_carry1_out", "out0", "out1")  # [9-a]
add_type("EMITFINAL", False, "emit")  # [0]
add_type("VAL", False, "val")  # [val]
add_type("CARRY0", False, "out", "source1", "source2")  # [val]
add_type("CARRY1", False, "out", "source1", "source2")  # [val]
add_type("ACTIVE1", True, "dummy", "next", "out", prop=[1,2])  # [0]
add_type("INACTIVE1", False, "dummy", "next", "out")  # [0]
add_type("PROPAGATING2", False, "dummy", "in1", "in2", "next", "out", prop=[3,4])  # [0]
add_type("INACTIVE2", False, "dummy", "in1", "in2", "next", "out")  # [0]

emitsums = [None] * maxn

for i in range(-1, maxn):
    if i >= 0:
        READ1 = add_type(f"READ1_{i}", True, "inp", "b", "out")  # [0]
        READ2 = add_type(f"READ2_{i}", True, "inp", "out")  # [a]
        EMIT = add_type(f"EMIT_{i}", False, "out")  # [a+b]
        emitsums[i] = READ1

        @rule
        def f(a: INP, r: READ1):
            READ2(a.tag, r.b, r.out)

        @rule
        def f(b: INP, r: READ2):
            EMIT(b.tag + r.tag, r.out)

    else:
        EMIT = EMITFINAL

    @rule
    def f(s: EMIT, c: CARRY0):
        OUT(i + 1, VAL(s.tag if s.tag < 10 else s.tag - 10))
        ERA(0, c.source1)
        ERA(0, c.source2)

    @rule
    def f(s: EMIT, c: CARRY1):
        OUT(i + 1, VAL(s.tag + 1 if s.tag < 9 else s.tag - 9))
        ERA(0, c.source1)
        ERA(0, c.source2)

@rule
def f(a: INP, r: READLT1):
    READLT2(9 - a.tag, r.b, r.eq_nocarry0_out, r.out)

@rule
def f(b: INP, r: READLT2):
    tp = ACTIVE1 if b.tag < r.tag else INACTIVE1
    tp(0, ERA(0), r.eq_nocarry0_out, r.out)

@rule
def f(a: INP, r: READGT1):
    READGT2(9 - a.tag, r.b, r.eq_carry0_out, r.out)

@rule
def f(b: INP, r: READGT2):
    tp = ACTIVE1 if b.tag > r.tag else INACTIVE1
    tp(0, ERA(0), r.eq_carry0_out, r.out)

@rule
def f(a: INP, r: READEQ1):
    READEQ2(
        9 - a.tag, r.b,
        r.eq_nocarry0_in, r.eq_nocarry1_in, r.eq_carry0_in, r.eq_carry1_in,
        r.eq_nocarry1_out, r.eq_carry1_out,
        r.out0, r.out1
    )

@rule
def f(b: INP, r: READEQ2):
    tp = PROPAGATING2 if b.tag == r.tag else INACTIVE2
    tp(0, ERA(0), r.eq_nocarry0_in, r.eq_nocarry1_in, r.eq_nocarry1_out, r.out0)
    tp(0, ERA(0), r.eq_carry0_in, r.eq_carry1_in, r.eq_carry1_out, r.out1)

@initial
def f():
    carry0 = CARRY0(0, ..., OUT(0), ERA(0))
    carry1 = CARRY1(0, ..., ERA(0), ERA(0))
    eq_nocarry0 = OUT(0)
    eq_nocarry1 = ERA(0)
    eq_carry0 = ERA(0)
    eq_carry1 = ERA(0)
    for i in range(maxn-1, -1, -1):
        emitsums[i](0, INP(i), INP(maxn + i), carry0)
        emitsums[i](0, INP(i), INP(maxn + i), carry1)
        carry0 = CARRY0(0)
        carry1 = CARRY1(0)
        readeq = READEQ1(0, INP(i), INP(maxn + i), eq_nocarry0, eq_nocarry1, eq_carry0, eq_carry1, ..., ..., carry0.source1, carry1.source1)  # [0]
        readlt = READLT1(0, INP(i), INP(maxn + i), ..., carry0.source2)
        readgt = READGT1(0, INP(i), INP(maxn + i), ..., carry1.source2)
        eq_nocarry0 = readlt.eq_nocarry0_out
        eq_carry0 = readgt.eq_carry0_out
        eq_nocarry1 = readeq.eq_nocarry1_out
        eq_carry1 = readeq.eq_carry1_out
    EMITFINAL(0, carry0)
    EMITFINAL(0, carry1)
    ERA(0, eq_nocarry0)
    ERA(0, eq_carry0)
    ERA(0, eq_nocarry1)
    ERA(0, eq_carry1)

finish()

sum-loop.py

# Summation in O(n) using a loop. IIRC this ties the best solution in code size, but it's not terribly interesting.
from lib import *

size = 50

add_type("POS", True, "carry")  # [ind]
add_type("CARRY", True, "pos")  # [val]
add_type("ADDCARRY", True, "a", "b", "out")  # [val]
add_type("ADD", True, "b", "out")  # [val]
add_type("CONT", False, "out")  # [ind]

@initial
def f():
    CARRY(0, POS(size - 1))

@rule
def f(p: POS, c: CARRY):
    if p.tag >= 0:
        ADDCARRY(c.tag, INP(p.tag), INP(p.tag + size), CONT(p.tag))
    else:
        OUT(0, POS(c.tag))

@rule
def f(a: ADDCARRY, i: INP):
    ADD(a.tag + i.tag, a.b, a.out)

@rule
def f(a: ADD, i: INP):
    CARRY(a.tag + i.tag, a.out)

@rule
def f(c: CARRY, o: CONT):
    OUT(o.tag+1, POS(c.tag % 10))
    CARRY(c.tag / 10, POS(o.tag - 1))

finish()

sum-seq.py

# Summation in O(n) which beats the fastest solution in sequential time.
# The main trick here is to use a speculative INP read at the start of each loop iteration,
# which reduces the number of required interactions by one. We cannot perform the read of a[i]
# speculatively, because it might read index -1 and crash, but we can do it for b[i] since
# that just harmlessly references index 49. Carry is encoded in node type.
from lib import *

size = 50

add_type("VAL", False, "other")  # [val]
add_type("POS0", True, "b")  # [ind]
add_type("POS1", True, "b")  # [ind]
add_type("PROCESS", True, "ind")  # [a + b + carry]
add_type("ADD", True, "i", "out")  # [b + carry]

@initial
def f():
    POS0(size-1, INP(size*2 - 1))

for carry in range(2):
    POS = POS0 if carry == 0 else POS1

    @rule
    def f(p: POS, i: INP):
        if p.tag >= 0:
            ADD(i.tag + carry, INP(p.tag), VAL(p.tag))
        else:
            OUT(0, VAL(carry))

@rule
def f(a: ADD, i: INP):
    PROCESS(a.tag + i.tag, a.out)

@rule
def f(p: PROCESS, v: VAL):
    OUT(v.tag+1, VAL(p.tag % 10))
    tp = POS1 if p.tag >= 10 else POS0
    tp(v.tag-1, INP(v.tag + (size-1)))

finish()