overlap.py

"""overlap.py -- the branching count trimmed at its ends: a child of a
fibre meeting A holds a whole image set near tau, at least e wide, inside
its box and the parent's hull, so only children whose box meets that
hull by e are counted, and z.U dies at L wherever
    b eta_max(L) + w - 2 e < b - 1,
e the producer's least image near tau on the floor chain.

THE QUESTION. Does the children's forced overlap (consecutive hulls
sharing about one image's width where images are dense) lower the
count's rate c, or only the constant in front of c^n?

THE DERIVATION (by hand, before this code). Overlap alone cuts the
cover N_n h / b^n to about N_n (h - e) / b^n: a factor in front, the
rate c / b untouched, since overlap bounds no fibre's number of
children. The fact behind it trims the count: a fibre is a union of
image sets (the producer's digit m is fixed by its input prefix of
length m + L_p), so a child meeting A holds one near tau, hull >= e,
inside box_k and the parent's hull I (b h long at the child's scale);
the k with |box_k cap I| >= e lie in an interval b h + w - 2 e long,
so c' = floor(b h + w - 2 e) + 1. Least images near tau, level scale:
behind the product head at L1, e_1 = 2 Mh w / b^L1; behind consumer i at
L_i reading z fresh and U_(i-1) (largest magnitude Mh^i),
e_i = (Mh^i w + Mh e_(i-1)) / b^L_i. On the floor chain (every upstream
unit at its floor; a lower delay only widens an image).

PREDICTIONS (frozen before this code). Q1: the trim kills no
certified life. Q2: at link 2, L = 1, it kills none of the 15 and adds
at most a handful past the count's 249. Q3: along the floor-2 runs it
closes under 5% of the 896 links the count leaves open past the
budget, the median staying 2. Q4: at L = 0 the first unit left open at
(4, 2, 2) moves from j = 8 to j = 9, every other verdict unchanged.

KILL (frozen). "certified lives the trimmed count kills: N", N > 0
kills the trim. "links the trim closes past the count: X of 896",
X < 45 with Q4 holding: the trim ships as one clause and nothing more
is built on it.

CONTROL (read first; the closure plant, e x 1000 inside section_chain's
counter, added after the first run). (20, 8, 12) and its mirror left
open at link 2, L = 1; the (4, 2, 2) hand values e_1 = 1/9,
e_2 = 1/24, trimmed margin negative at j = 8 and positive at j = 9; a
planted break, e = w at
(20, 8, 12)'s link 2, must kill that certified life. (Frozen as e = w/2;
2 (w/2) = w is below that link's margin 2.0896, so the plant could not
fire, and it was raised to w, a fibre's widest hull, before any run.)

FINDINGS (entered after the run; every number a print, K = 200,
radices 3..40).
  - Controls: (20, 8, 12) and its mirror left open (margin +2.0896, 2e_1
    0.0066, trimmed +2.0829); the plant e = w kills that link (trimmed
    -0.0157); (4, 2, 2) e_1 = 1/9, e_2 = 1/24, trimmed -0.0308 at j = 8,
    +0.0906 at j = 9.
  - Q1 HELD: certified lives the trimmed count kills: 0. The first kill
    does not fire.
  - Q2 HELD: at link 2 the trim kills 249 of the 274, the count's 249,
    new none, none of the 15 (least margin there +1.1215 against the
    largest 2e_1 0.0635).
  - Q3: links the trim closes past the count: 0 of 896 (the plant,
    e x 1000 in the same counter, closes 240 of 896); the median left
    open past the budget stays 2, none at 32 cells, the edge link alone
    at 79, as the count. 2e over the 4207 links runs 3.38e-05 to
    6.07e-02, median 6.33e-04, below every open margin. Q3's "e is
    O(1/b^2)" is not read: the print gives the range alone.
  - Q4 HELD: at L = 0 the first unit left open moves at (4, 2, 2) from
    j = 8 to j = 9; (4, 2, 2) is the one cell the count leaves open
    there, so "every other verdict unchanged" holds vacuously.
  - VERDICT by the frozen kill (X = 0 < 45, Q4 holding): the trim ships
    as one clause; nothing more is built on it. Overlap itself moves
    only the constant (the derivation), and the trim's 2e falls like
    w Mh^j / (b^L - 1) down a chain at delay L >= 1 while the deep margin
    at (4, 2, 2) rises to 1/3.

RUN RECORD: (pinned.section_sweep prints its own checks, tuned to radix
40: at the bare size its C3 and Q4 print FAIL, outside this script's
count.) Bare (K = 40, radices 3..12) 0.3 s, 6/6, 20.1 MB; K = 200,
radices 3..40, 94.3 s, 5/5, peak not read; again with the closure plant
added, 94.3 s, 6/6 (branching.py's same populations peak 38.4 MB).

USAGE: python overlap.py [K [bmax]], K = 40, bmax = 12 bare; the
record run python overlap.py 200 40.
"""

import os
import sys
import time
from fractions import Fraction as Fr

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import branching  # noqa: E402
import chains  # noqa: E402
import hulls  # noqa: E402
import manystream as ms  # noqa: E402
import pinned  # noqa: E402
import twolinks  # noqa: E402

CHECKS = []
margin = branching.margin
tag = branching.tag


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


def least_images(cell, n):
    """e[i], i = 1..n: the least image hull near tau of unit i's output
    on the floor chain behind the product head (level scale)."""
    L1s = chains.xy_head(cell)[1]
    e = {1: 2 * cell.Mh * cell.w / Fr(cell.b) ** L1s}
    for i, (_, Ls, _, _) in enumerate(twolinks.chain(cell, n), start=2):
        e[i] = (cell.Mh ** i * cell.w + cell.Mh * e[i - 1]) / Fr(cell.b) ** Ls
    return e


def trimmed(cell, L, j, e):
    """The trimmed margin at link j (consumer j reading unit j - 1)."""
    return margin(cell, L, cell.Mh ** j) - 2 * e[j - 1]


def section_control():
    print("O0  controls")
    for c in (ms.Cell(20, 8, 12), ms.Cell(20, 12, 8)):
        e = least_images(c, 2)
        m = trimmed(c, 1, 2, e)
        check(f"O0 {tag(c)} link 2 at L = 1 left open by the trim", m >= 0,
              f"margin {float(margin(c, 1, c.Mh ** 2)):+.4f}, 2e_1 "
              f"{float(2 * e[1]):.4f}, trimmed {float(m):+.4f}")
    c = ms.Cell(20, 8, 12)
    m = margin(c, 1, c.Mh ** 2) - 2 * c.w
    check("O0 plant: e = w kills the certified (20, 8, 12) link 2", m < 0,
          f"trimmed {float(m):+.4f}")
    c = ms.Cell(4, 2, 2)
    e = least_images(c, 10)
    t8, t9 = trimmed(c, 0, 8, e), trimmed(c, 0, 9, e)
    check("O0 (4, 2, 2) by hand: e_1 = 1/9, e_2 = 1/24, j = 8 closed, "
          "j = 9 open at L = 0",
          e[1] == Fr(1, 9) and e[2] == Fr(1, 24) and t8 < 0 <= t9,
          f"e_1 {e[1]}, e_2 {e[2]}, trimmed j = 8 {float(t8):+.4f}, "
          f"j = 9 {float(t9):+.4f}")


def section_link2(bmax):
    print(f"O1  link 2 at L = 1, radices 3..{bmax}")
    gains, rest, kill, spare = pinned.section_sweep(bmax)
    e = {tag(c): least_images(c, 1) for c in gains + rest}
    bad = [tag(c) for c in gains if trimmed(c, 1, 2, e[tag(c)]) < 0]
    cnt = [c for c in rest if margin(c, 1, c.Mh ** 2) < 0]
    trm = [c for c in rest if trimmed(c, 1, 2, e[tag(c)]) < 0]
    new = [tag(c) for c in trm if c not in cnt]
    print(f"    the count kills {len(cnt)} of the {len(rest)}, the trim "
          f"{len(trm)}; new {new}; among the {len(spare)}: "
          f"{[tag(c) for c in trm if c in spare]}")
    sm = [(float(margin(c, 1, c.Mh ** 2)), float(2 * e[tag(c)][1]))
          for c in spare]
    if sm:
        print(f"    at the {len(spare)}: least margin {min(m for m, _ in sm):+.4f}"
              f", largest 2e_1 {max(t for _, t in sm):.4f}")
    return bad


def section_chain(K, bmax):
    print(f"O2  floor-2 links j >= 3 at L = 1, radices 3..{bmax}, K {K}")
    rows = twolinks.section_links(K, bmax)
    E = {}
    for r in rows:
        c = r["cell"]
        if c not in E:
            E[c] = least_images(ms.Cell(*c), r["n"])
    bad = [(r["cell"], r["j"]) for r in rows
           if (r["A"] or r["B0"] or r["Bv"])
           and trimmed(ms.Cell(*r["cell"]), 1, r["j"], E[r["cell"]]) < 0]
    o_cnt, o_trm, exact, o_plant = [], [], [], 0
    for c in sorted({r["cell"] for r in rows}):
        cell = ms.Cell(*c)
        mine = sorted((r for r in rows if r["cell"] == c),
                      key=lambda r: r["j"])
        ga = [r["j"] for r in mine if r["A"]]
        edge = ga[0] - 1 if ga else mine[-1]["j"]
        oc = [r["j"] for r in mine if not r["A"]
              and margin(cell, 1, cell.Mh ** r["j"]) >= 0]
        ot = [j for j in oc if trimmed(cell, 1, j, E[c]) >= 0]
        Ep = {i: 1000 * x for i, x in E[c].items()}
        o_plant += sum(trimmed(cell, 1, j, Ep) < 0 for j in oc)
        o_cnt.append(len(oc))
        o_trm.append(len(ot))
        if ot == [edge]:
            exact.append(c)
    closed = sum(o_cnt) - sum(o_trm)
    check("O2 plant: e x 1000 closes links the count leaves open",
          o_plant > 0, f"{o_plant} of {sum(o_cnt)}")
    s = sorted(o_trm)
    med = s[len(s) // 2] if s else None
    print(f"    links the trim closes past the count: {closed} of "
          f"{sum(o_cnt)}")
    print(f"    links the trimmed count leaves open past the budget: median "
          f"{med}, total {sum(o_trm)} of {len(rows)}, at most "
          f"{max(o_trm or [0])}; none at {o_trm.count(0)} cells (the count "
          f"{o_cnt.count(0)}); exactly the edge link at {len(exact)} of "
          f"{len(o_trm)} cells")
    ds = sorted(float(2 * E[r["cell"]][r["j"] - 1]) for r in rows)
    if ds:
        print(f"    2e over the links: {ds[0]:.2e} to {ds[-1]:.2e}, median "
              f"{ds[len(ds) // 2]:.2e}")
    return bad


def section_floor1(bmax):
    print(f"O3  floor-1 consumers at L = 0, radices 3..{bmax}")
    out = []
    for b in range(3, bmax + 1):
        for cell in hulls.cells1(b, b):
            A1, L1s, S, _ = chains.xy_head(cell)
            if S(L1s) < 0:
                continue
            j = 2
            while j <= 400:
                tau = cell.Mh ** j
                if chains.unit_floor(cell, cell.Mh + tau) == 1 and \
                        margin(cell, 0, tau) >= 0:
                    break
                if margin(cell, 0, Fr(0)) < 0 and tau < Fr(1, 10 ** 6):
                    j = None
                    break
                j += 1
            if j is None or j > 400:
                continue
            j0, e = j, least_images(cell, j + 40)
            while j < j0 + 40 and trimmed(cell, 0, j, e) < 0:
                j += 1
            out.append((tag(cell), j0, j))
    print(f"    (cell, first open by the count, first open by the trim): "
          f"{out}")
    return out


def main():
    K = int(sys.argv[1]) if len(sys.argv) > 1 else 40
    bmax = int(sys.argv[2]) if len(sys.argv) > 2 else 12
    t0 = time.time()
    section_control()
    if not all(CHECKS):
        print("CONTROL FAILED; nothing below is read")
        raise SystemExit(1)
    bad = section_link2(bmax)
    bad += section_chain(K, bmax)
    print(f"    certified lives the trimmed count kills: {len(bad)} {bad[:4]}")
    check("Q1 the trim kills no certified life", not bad, f"{len(bad)}")
    section_floor1(bmax)
    print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
          f"{time.time() - t0:.1f} s")
    raise SystemExit(0 if all(CHECKS) else 1)


if __name__ == "__main__":
    main()