stacked.py

"""
stacked.py -- two gains on one path: pairs of balanced product trees
priced by the tree pass.

QUESTION. graphs.py prices a tree of product units by one pass of the
narrowed reader's programme. A product unit reading leaf counts
(d_U, d_V) has Lam = M^(d_U) + M^(d_V) and gains, reading one below
its floor, where Lam sits just above 1 (floor 2 to delay 1) or just
above 1/b (floor 1 to delay 0). A unit downstream of a gaining one
reads larger leaf counts, so two gains may stack on one path. T(n) the
balanced product tree of n fresh leaves (graphs.py::tree); over the
unit (T(m), T(n)), 1 <= m <= n <= 16, at graphs.py's 441
cells: how often does the least latency sit 2 or more below the
naive, and which units gain?

DESIGN. graphs.py::build with a memo per cell (every T(n) shared), the
least latency its root's first live t, and graphs.py::trace the units
below their floors in one least assignment (the B(t) argmax at each
unit), named by leaf counts. Delays 0 .. L* + 3 per unit, as graphs.py.

PREDICTIONS (frozen before this code). GE (graphs.py's check): at
(8, 3, 5), (T(6), T(16)) reads naive 7, least 5. Gains by 2 at some
cell besides (8, 3, 5). Gains by 3: printed, no prediction.

CONTROL of the instrument, read first: the memoized pass equals
graphs.py::price on the same tree, unshared, at every cell for
(T(3), T(4)) and (T(6), T(16)).

FINDINGS (every number a print of the run below).
  K passes: 441 cells, 0 off. GE holds: (T(6), T(16)) at (8, 3, 5)
  reads naive 7, least 5.
  Over the 136 pairs at 441 cells (59,976 roots): 55,270 gain 0, 4,609
  gain 1, 97 gain 2, none gain 3. The 97 lie at 21 cells, (8, 3, 5)
  among them; the prediction (some cell besides) holds 20 times over.
  Every gaining unit reads one below its floor from 2 to 1 or from 1
  to 0, 29 (cell, unit) incidences of each in the traced assignment.
  At 14 of the 21 cells the
  gaining units include a floor-1 unit read at 0 (at (8, 3, 5): (2, 2)
  at 1 under (6, 16) at 0). At the other 7, (8, 2, 6), (9, 2, 7),
  (11, 2, 9), (12, 2, 10), (14, 2, 12), (30, 5, 25) and (37, 6, 31),
  every gaining unit reads from 2 to 1, so two leaf-count pairs at one
  cell sit with Lam just above 1, on one path: at (8, 2, 6), (4, 4) and
  (2, 8) in (T(2), T(8)), naive 8, least 6.

RUN RECORD. 1/1 checks, 55.1 s, peak commit 9.1 MB under a memory
guard.
"""
import sys
import time
from collections import Counter

import graphs

CHECKS = []
NMAX = 16


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 pairs():
    for m in range(1, NMAX + 1):
        for n in range(m, NMAX + 1):
            yield m, n


def least_of(cell, root, memo, tmax=24):
    _, _, B, naive = graphs.build(cell, root, None, tmax, memo=memo)
    least = next((t for t, x in enumerate(B) if x is not None), None)
    assert least is not None, "tmax"
    return naive, least


def main():
    t0 = time.time()
    cs = list(graphs.cells())
    print("K  the memoized pass against price(), every cell")
    off = 0
    for cell in cs:
        for m, n in ((3, 4), (6, 16)):
            root = (graphs.tree(m), graphs.tree(n))
            off += least_of(cell, root, {}) != graphs.price(cell, root)
    check("K memo equals price on (T(3), T(4)) and (T(6), T(16))",
          off == 0, f"{len(cs)} cells, {off} off")
    if not all(CHECKS):
        print("\nCONTROL FAILED: nothing below is read.")
        return 1

    by = Counter()
    deep = {}
    for cell in cs:
        memo = {}
        for m, n in pairs():
            root = (graphs.tree(m), graphs.tree(n))
            naive, least = least_of(cell, root, memo)
            g = naive - least
            by[g] += 1
            if g >= 2:
                low = []
                graphs.trace(cell, root, least, memo, low)
                deep.setdefault(graphs.name(cell), []).append(
                    (m, n, naive, least, sorted(set(
                        (u, v, L, Ls) for u, v, L, Ls in low))))
    np_ = sum(1 for _ in pairs())
    print(f"\nG  {np_} pairs at {len(cs)} cells: gain -> count")
    for g in sorted(by):
        print(f"    {g}: {by[g]}")
    print(f"\nD  cells with a gain by 2 or more: {len(deep)}")
    windows = Counter()
    upper = []
    for k in sorted(deep, key=lambda s: tuple(map(int, s[1:-1].split(",")))):
        rows = deep[k]
        top = max(r[2] - r[3] for r in rows)
        units = sorted({(u, v, L, Ls) for r in rows for (u, v, L, Ls) in r[4]})
        if all((Ls, L) == (2, 1) for _, _, L, Ls in units):
            upper.append(k)
        for u, v, L, Ls in units:
            windows[(Ls, L)] += 1
        print(f"  {k:14s} {len(rows):3d} pairs, best gain {top};"
              f" gaining units (d_U, d_V, L, L*): "
              + " ".join(f"({u},{v},{L},{Ls})" for u, v, L, Ls in units))
        best = min(rows, key=lambda r: (r[3] - r[2], r[0] + r[1]))
        print(f"  {'':14s} e.g. (T({best[0]}), T({best[1]})) naive "
              f"{best[2]}, least {best[3]}")
    print("\nW  gaining units by (L*, L) over those cells: "
          + ", ".join(f"{a}->{b}: {c}"
                      for (a, b), c in sorted(windows.items())))
    print(f"   cells whose gaining units all read from 2 to 1: "
          f"{len(upper)}, {' '.join(upper)}")
    w = [r for r in deep.get("(8, 3, 5)", []) if (r[0], r[1]) == (6, 16)]
    print(f"\nGE at (8, 3, 5): {w[0][2:4] if w else 'absent'}")
    print(f"\n{sum(CHECKS)}/{len(CHECKS)} checks, {time.time() - t0:.1f} s")
    return 0 if all(CHECKS) else 1


if __name__ == "__main__":
    sys.exit(main())