graphs.py

"""
graphs.py -- what a tree of on-line product units pays: the narrowed
reader's programme carried from a chain to a tree.

QUESTION. chains.py prices units in series: a consumer below its floor
spends its producer's leftover inset, the least total over delay
assignments read by a pass along the chain. A graph adds fan-in, a unit
reading two produced streams, each through its own hull. On small
trees at one cell, does the programme read below NAIVE (below)
where no chain does, (a) by the new pairs of input magnitudes a
tree carries, or (b) by slack: an input that arrives early may sit one
delay above its floor at no cost to the latency, handing its consumer
a far larger inset?

THE SETTING. One slack-1 representable cell, a+- <= b - 2 (M^ < 1),
as chains.py. A stream is FRESH (largest magnitude M^, read through no
hull) or PRODUCED by a unit (largest magnitude tau, read through a
hull of its box inset by eta). A product unit reading U and V has
Lam = tau_U + tau_V, and over hulls of widths h_U, h_V its image is at
most tau_V h_U + tau_U h_V wide in its level's units (|u|, |v| bounded
at every point: no cross term), so at delay L it is alive where

    v(L) = (w - 1) - (Lam w - tau_V eta_U - tau_U eta_V)/b^L >= 0,

and hands on min(v(L), its room), chains.py::leftover at a fresh
input. A head x y is the unit over two fresh streams; its leftover is
chains.py's budget_xy, capped by its room. Cost: the LATENCY, the
longest path's sum of delays (a unit reading two streams waits for
the later). Its floor L* is the least L alive at zero insets; NAIVE is
the latency at every unit's floor.

THE PASS (the tree programme). Per unit and per latency t, B(t) is the
best leftover its subtree hands at latency <= t: the max over L of
v(L) on the inputs' B(t - L), each inset capped at w - 1, a fresh
input handing 0 at every t >= 0. v rises in L and in each inset, so
B rises in t and the pass is exact for the programme. LEAST is the
least t with the root alive. Delays searched: 0 .. L* + 3 per unit,
a superset of the frozen L* - 1 .. L* + 2; the pass is exact within
it. The w - 1 cap on insets never binds here (v < w - 1). A HELD unit
is searched at its floor alone.

SHAPES. C = (x y) z, the chain's two units; P = (x y)(x' y'), a pair of
heads; S = ((x y) z)(x' y'), the bare head x' y' early by the
consumer's delay; S_hold, S with x' y' held at its floor; Q =
((x y) z)((x' y') z').

PREDICTIONS (frozen before this code). P gains where
2 M^2 - 1 lies in (0, 2 M^2 S/w], disjoint from C's cells, (8, 3, 5)
among them at least 3 against naive 4. S gains on a window about
tau_U/b wide around M^3 + M^2 = 1, more cells than S_hold. Q thin.

CONTROLS, read before any shape. GA: C's least is
chains.py::two_unit(cell, xy_head)'s least at every cell. GB: P at
(8, 3, 5) reads 3 against 4, the hand value. GC (replacing the
frozen one, which held by construction): at (4, 2, 2), where the
threshold-miss law's z (x y) reads one below its floor and S's root
(floor 1, dead at 0 at any inset) cannot, S with its consumer (x y) z
held reads naive, and with its bare head x' y' held reads naive - 1.

THE CHAIN BASELINE. A cell counts as outside the chains when no chain
of 2 to 12 units behind a product head gains there (sum heads not
read)
(chains.py::two_unit and chains.py::programme_all).

KILL. Per shape, the count of cells with least < naive and how many
lie outside C's set (the baseline as frozen; the chain baseline was
added after the run). (a) dies if P and Q print 0 outside C's set; (b)
dies if S's count equals S_hold's.

FINDINGS (every number a print of the run below).
  Controls: GA 441 cells, 0 off; GB naive 4, least 3; GC (5, 5) and
  (5, 4). A planted break (hold ignoring its path), run on a scratch
  copy and not part of this run, fails GC at (5, 4), (5, 4).
  C gains at 17 cells, the threshold-miss law's 17 with their mirrors.
  P gains at 12, all outside C's, 10 outside every chain to 12 units:
  (8, 3, 5) (15, 5, 10) (19, 6, 13) (22, 7, 15) (25, 8, 17)
  (26, 8, 18) (29, 9, 20) (32, 10, 22) (36, 11, 25) (39, 12, 27);
  chains reach (5, 2, 3) and (12, 4, 8), where the four-unit chain's
  last link, Lam = M^ + M^4 just above 1, reads one below its floor (by
  hand, not printed here). (a) survives: a tree reads below NAIVE at
  cells where no chain of up to 12 units behind a product head does.
  Q gains at 26, 9 outside C's, 2 outside every chain ((35, 8, 27),
  (40, 9, 31)); its two inner chains gain at C's 17 in parallel, one
  digit. S gains at 26, 9 outside C's, none outside those chains;
  S_hold at 25, 8 outside C's. (b) survives against its frozen kill by
  one cell, (6, 2, 4), which a chain reaches too: over these cells and
  shapes, slack bought no cell those chains do not. The frozen premise
  behind the predicted widening, that a head hands O(1/b^2) at its
  floor, was wrong: its budget
  (w - 1) - 2 M^ w/b^L1* is already a large part of w - 1. No shape
  gains 2 or more.

RUN RECORD. 441 cells, 3/3 checks, 8.0 s, peak commit 8.1 MB
under a memory guard.
"""
import sys
import time
from fractions import Fraction as Fr

import chains

CHECKS = []
FRESH = "z"


def check(name, ok, detail=""):
    CHECKS.append(bool(ok))
    tail = f"  ({detail})" if detail else ""
    print(f"  {'PASS' if ok else 'FAIL'}  {name}{tail}")


def head():
    return (FRESH, FRESH)


SHAPES = {
    "C": (head(), FRESH),
    "P": (head(), head()),
    "S": ((head(), FRESH), head()),
    "Q": ((head(), FRESH), (head(), FRESH)),
}


def cells():
    for cell in chains.cells(3, 40, slack=1):
        if chains.representable(cell) and cell.Mh < 1:
            yield cell


def iprod(r, s):
    c = [x * y for x in r for y in s]
    return (min(c), max(c))


def v(cell, lam, L, tu, tv, eu, ev):
    return cell.w - 1 - (lam * cell.w - tv * eu - tu * ev) / Fr(cell.b) ** L


def build(cell, node, hold, tmax, path=()):
    """(tau, range, B, naive) of a node; B a list over t = 0..tmax of
    the best leftover at latency <= t, None where dead. hold: True to
    search every unit at its floor alone, or the path (child indices
    from the root) of one unit."""
    if node == FRESH:
        return cell.Mh, (-cell.Mm, cell.Mp), [Fr(0)] * (tmax + 1), 0
    U, V = node
    tu, ru, bu, nu = build(cell, U, hold, tmax, path + (0,))
    tv, rv, bv, nv = build(cell, V, hold, tmax, path + (1,))
    lam, rng = tu + tv, iprod(ru, rv)
    room = chains.room(cell, rng)
    assert cell.Mm + rng[0] >= 0 and cell.Mp - rng[1] >= 0
    Ls = 0
    while v(cell, lam, Ls, tu, tv, 0, 0) < 0:
        Ls += 1
    held = hold is True or hold == path
    Ls_range = [Ls] if held else range(0, Ls + 4)
    B = [None] * (tmax + 1)
    for t in range(tmax + 1):
        best = None
        for L in Ls_range:
            if t - L < 0 or bu[t - L] is None or bv[t - L] is None:
                continue
            eu, ev = (min(x, cell.w - 1) for x in (bu[t - L], bv[t - L]))
            r = v(cell, lam, L, tu, tv, eu, ev)
            if r >= 0:
                r = min(r, room)
                if best is None or r > best:
                    best = r
        B[t] = best
    return tu * tv, rng, B, Ls + max(nu, nv)


def price(cell, shape, hold=None, tmax=24):
    _, _, B, naive = build(cell, shape, hold, tmax)
    least = next((t for t, x in enumerate(B) if x is not None), None)
    return naive, least


def controls(cs):
    print("GA..GC  the controls")
    off = 0
    for cell in cs:
        n, lst = price(cell, SHAPES["C"])
        nn, ll, _, _ = chains.two_unit(cell, chains.xy_head)
        off += (n, lst) != (nn, ll)
    check("GA C is two_unit's (naive, least) at every cell",
          off == 0, f"{len(cs)} cells, {off} off")
    n, lst = price(chains.ms.Cell(8, 3, 5), SHAPES["P"])
    check("GB P at (8, 3, 5) reads 3 against 4", (n, lst) == (4, 3),
          f"naive {n}, least {lst}")
    cell = chains.ms.Cell(4, 2, 2)
    n0, l0 = price(cell, SHAPES["S"], hold=(0,))
    n1, l1 = price(cell, SHAPES["S"], hold=(1,))
    check("GC S at (4, 2, 2): consumer held naive, bare head held "
          "naive - 1", (l0, l1) == (n0, n1 - 1),
          f"({n0}, {l0}), ({n1}, {l1})")


def chain_gains(cell):
    naive, least, _, _ = chains.two_unit(cell, chains.xy_head)
    return least < naive or any(
        r[2] < r[0]
        for r in chains.programme_all(cell, chains.xy_head, 12).values())


def name(cell):
    return f"({cell.b}, {cell.am}, {cell.ap})"


def main():
    t0 = time.time()
    cs = list(cells())
    controls(cs)
    if not all(CHECKS):
        print("\nCONTROL FAILED: nothing below is read.")
        raise SystemExit(1)
    gains = {}
    for key, shape in SHAPES.items():
        gains[key] = {name(c): price(c, shape) for c in cs}
    vhold = (1,)
    gains["S_hold"] = {name(c): price(c, SHAPES["S"], hold=vhold)
                       for c in cs}
    base = {k for k, (n, l) in gains["C"].items() if l < n}
    chained = {name(c) for c in cs if chain_gains(c)}
    print(f"\nGD  gains over {len(cs)} cells, radices 3 to 40")
    for key, g in gains.items():
        won = sorted((k for k, (n, l) in g.items() if l < n),
                     key=lambda s: tuple(map(int, s[1:-1].split(","))))
        out = [k for k in won if k not in base]
        far = [k for k in won if k not in chained]
        deep = [k for k in won if g[k][0] - g[k][1] > 1]
        print(f"  {key:6s} {len(won):3d} gain, {len(out):3d} outside C's,"
              f" {len(far):3d} outside every chain, {len(deep)} by 2")
        print(f"         chains reach: "
              f"{' '.join(k for k in out if k in chained) or '-'}")
        print(f"         {' '.join(won)}")
    print(f"\n{sum(CHECKS)}/{len(CHECKS)} checks passed, "
          f"{time.time() - t0:.1f} s")
    raise SystemExit(0 if all(CHECKS) else 1)


if __name__ == "__main__":
    main()