classform.py
Cited on: FLUSH.
To run it: save classform.py, with anchors.py, decide.py, firstreturn.py, flush.py, gaps.py, hull.py, hullform.py, induct.py, keyweld.py, ostrowski.py, tie.py beside it; standard library only.
"""
classform.py -- the class step in closed form: c_inf read off the
quotients and m by the zero reply's gaps, their key ends, r_t's first
returns and the hull's closed-form ends, against induct.least.
QUESTION. The class step (firstreturn.py) certifies each of the zero
reply's forbidden pieces at c_inf by one end's first-return window
holding the hull's G-range; the hull's ends are Z of integer keys
(hullform.py). (Q) Is c_inf, at every cell, the least c with pinned
moves at which every zero-reply piece, built from keys in U_k, V_k, is
certified by three-gap windows against the closed-form G-range, no
closure grown, no game solved and no fixed point iterated?
DERIVED BY HAND (before the engine). Keys at phase t: K_k = (U_k,
V_k), q_(n+k) = U_k q_n + V_k q_(n-1), y(G, H) = H - r_t G, so y(K_k)
= (-1)^(k+1) P_k, P_k = |theta_(t+k)/theta_(t-1)| (K_0 = (1, 0), y =
-r_t; K_1 = (a_(t+1), 1), y = 1 - a_(t+1) r_t = r_t r_(t+1)).
THE WINDOW'S ENDS ARE KEYS. Field.valid's full window is [-P_1 - m
R_0, P_0 - m R_1], R the sorted pair (-1)^c P_c, (-1)^(c+1) P_(c+1)
= -y(K_c), -y(K_(c+1)). So V(t, F) = [y(m K_o - K_1), y(m K_e -
K_0)], K_o, K_e the odd- and even-indexed of K_c, K_(c+1) (y(K_o) >
0 > y(K_e)). The reduced window's R is sorted(-y(K_(c+1)), -y(K_c)
- y(K_(c+1))): at c even V(t, R) = [y(m K_(c+1) - K_1), y(m (K_c +
K_(c+1)) - K_0)], at c odd [y(m (K_c + K_(c+1)) - K_1), y(m K_(c+1)
- K_0)].
THE ZERO REPLY. Window.pre at d = 0 sends (G, H) at t to (H, G -
a_(t+1) H) at t + 1, and the moves subtract e = 0 .. a_(t+2) from
G, landing on the full flag; with 1/r_t = a_(t+1) + r_(t+1), y_(t+1)
= -y_t / r_t + e r_(t+1), so the valid y_t are the translates r_t (e
r_(t+1) - V(t+1, F)), e = 0 .. a_(t+2), stepping by y(K_1). A key
(G', H') at t + 1 pulls back to (a_(t+1) G' + H', G') at t, of y
-r_t y_(t+1)(G', H'), so K'_k pulls back to K_(k+1) and the order
reverses. Translate e is [y(m K_O - K_1) + e y(K_1), y(m K_E - K_2) +
e y(K_1)], K_O, K_E the odd- and even-indexed of K_(c+1), K_(c+2).
The forbidden pieces after reply 0 are the gaps between translates e
and e + 1, e = 0 .. a_(t+2) - 1, open, with key ends
E_a(e) = m K_E - K_2 + e K_1, E_b(e) = m K_O + e K_1,
of length L = y(E_b - E_a) = m (P_(c+1) + P_(c+2)) - P_2 (positive,
else no gap), each clipped to V(t, f). No piece lies beyond the
translates: at the bottom, y(m K_O - K_1) <= y(m K_o - K_1) on the
full flag (equal if c + 1 is odd, else P_(c+2) < P_c), and on the
reduced at c odd y(K_(c+2)) = a y(K_(c+1)) + y(K_c) <= y(K_c +
K_(c+1)); at the top, a_(t+2) K_1 - K_2 = -K_0 makes translate a's
top y(m K_E - K_0), at or above both windows' tops alike. A gap may
still straddle a window's end, the full flag's too (golden x2, c =
2: (0.0557, 0.1459], clipped at its top), so each is clipped. The
translates presume V(t + 1, F) nonempty, which pinned moves give.
Bronze x3, t = 0, c = 2 (K: (1, 0), (3, 1), (10, 3), (33, 10), (109,
33)): E_b = 3 (33, 10) = (99, 30), E_a = 3 (109, 33) - (10, 3) =
(317, 96), three gaps; golden x2, c = 3: (16, 10) and 2 (5, 3) - (2,
1) = (8, 5), one gap. At the period-4 cells, by hand from Field.a:
V1 x2 t = 1, c = 3 (K_4 = (7, 4), K_5 = (12, 7)): (24, 14), (12, 7);
t = 2 (K_4 = (7, 5), K_5 = (11, 8), K_1 = (1, 1)): (22, 16), (11, 8)
and the second gap (23, 17), (12, 9); V1 x3 t = 1, c = 4 (K_6 = (19,
11)): (36, 21), (55, 32); V2 x4 t = 0, c = 4 (K_5 = (39, 14), K_6 =
(53, 19)): (156, 56), (209, 75). Gap counts a_(t+2): 1, 2, 1, 1. All
22 of firstreturn.py's rows, ends and counts, read so.
THE WINDOWS. From E_a, h+ = n-(L) and h- = -n+(L); from E_b, h+ =
n+(L), h- = -n-(L), n+- r_t's records (firstreturn.py::three_gap).
A piece passes when no closed end is a hull key and some end E has
G-range low > G_E + h- and high < G_E + h+, the G-range floor(Z_lo -
kappa_t y_b) .. ceil(Z_hi - kappa_t y_a) with hullform.py's forms
(firstreturn.py's certified, its enumeration replaced).
TRANSPLANT, to re-derive: the forms were read at c_inf only; below
c_inf the hull's fixed point may take another policy or bind a
start. And the zero reply alone: a piece of another reply holding a
hull key below c_inf with every zero-reply piece passing would put
the formula under c_inf.
DESIGN (frozen before the engine). Cells: decide.py's 136 (flush.py's
PERIODIC and decide.py's FRESH by m = 2 .. 9). Per cell, c from 0:
skip c without pinned moves (Window.pin_starts, a check of a_(t+1) + 1
keys per phase, no closure); c_form is the first c at which every
zero-reply piece passes. Beside it induct.least(F, m, "pin").
Ingredients, each its own print, read at every c with pinned moves up
to c_inf: (i) the formula's pieces against keyweld.py's forbidden(win,
t, f, 0), exactly (ends and closures); (ii) the four forms against
hull.py's fixed points; (iii) the formula's pass against firstreturn's
certified on the same piece with hull.py's values, per piece.
PREDICTIONS. (P1) (i) agrees at every (cell, c, t, f). (P2) (ii)
agrees at c_inf (hullform.py's) and below it. (P3) c_form = c_inf at
every cell.
KILL: "c_form != c_inf at n of 136 cells", n > 0; printed apart over
the arm where c_inf exceeds the first c with pinned moves (the cells
where a piece must fail below c_inf, the derivation's corner), the
rest reading only that c_inf's pieces pass.
CONTROLS (read before the verdict). (a) bronze x3 and golden x2 at
phase 0, c_inf: the first gap's E_a, E_b, the windows from E_b and
the G-range per flag, beside the hand values above and firstreturn's
rows ((-4, 30) and (26, 100) at bronze); c_form 2 and 3. THE PLANTS,
one per step, each in the direction it pushes, each through the
formula alone: (b) E_b shifted by K_1: (i) must disagree somewhere;
(c) h+ and h- doubled (looser windows): c_form must fall below c_inf
at some cell; (d) the reduced upper end with K_c for K_(c+1)
(narrower G-range): c_form must fall at some cell.
FINDINGS (copied from the run's prints).
CONTROLS. (a) golden x2 (c_inf 3): E_a (8, 5), E_b (16, 10), from
E_b (h-, h+) = (-21, 13), G-range (-2, 7) full, (4, 10) reduced;
bronze x3 (c_inf 2): (317, 96), (99, 30), (-251, 109), (-4, 30)
and (26, 100): the hand values and firstreturn's rows; c_form 3
and 2. (b) E_b + K_1: pieces equal at 43 of 1060 (t, f) read:
(i) can fire. (c) windows doubled: c_form < c_inf at 8 of 136:
the kill can fire. (d) MISSED: the reduced upper end at K_c moves
c_form at 0 of 136. Added after the run, both missed too: (e)
both upper ends one index down, (f) both floors raised by Z(1,
0) = lambda_t: c_form != c_inf at 0 and 0 of 136.
INGREDIENTS, at every c with pinned moves from the first to c_inf.
Window ends as keys != Field.valid: 0 of 1060. (i) pieces !=
forbidden(d = 0): 0 of 1060. (ii) forms != hull.py: 0 of 1060,
so the forms hold below c_inf too at the 136 (the TRANSPLANT read,
not proved). (iii) pass != firstreturn's certified: 0 of 903.
P3, KILL MISSED. c_form != c_inf at 0 of 136 cells; on the arm where
c_inf exceeds the first c with pinned moves, 0 of 108.
So at decide.py's 136, c_inf is the least c with pinned moves at
which every zero-reply piece (the gaps (E_a(e), E_b(e)) clipped to
V(t, f)) has no closed end in the hull and passes its three-gap
window against the closed-form G-range: keys, r_t's records and m,
no closure, game or fixed point.
NOTICED AFTER THE RUN (a scratch diagnostic over this engine's
functions, not in it). Each of the 129 (cell, c) with pinned moves
below c_inf has failing pieces, 1 to 15, 709 in all: 694 fail on the
window's low side (49 of them also with a closed end in the hull), 15
by a closed end alone, none on the high side; the best low margin per
(cell, c) is -1599 to -1 in G.
So (d) and (e), lowering the top, cannot move a verdict, and (f)
moves the floor by under one key and moved none: the window's short
side, r_t's first return at L, decides, and c_inf may be a cruder
inequality between n+-(L) and the hull's G-extent, both in q's.
RUN RECORD. 9.6 s, peak commit 11.2 MB; the engine was written whole
after the freeze and run once. Then plants (e) and (f) were added
(every earlier print unchanged) and run once more, 10.5 s. The window
ends' print was in the engine before the run, beside (i), unfrozen.
After the runs the cells were keyed by their full names (two of
decide.py's FRESH share a first word) and the verdicts made the exit
code, every count unchanged: 0 iff (a) prints the four rows and c_form
values recorded in FINDINGS, (b) reads unequal pieces somewhere, (c)
moves some cell, (d) to (f) read 0, the four ingredients 0 of 1060,
1060, 1060 and 903, and P3 0 of 136 and 0 of 108.
Usage: python classform.py
"""
import math
import os
import sys
import time
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
from flush import PERIODIC # noqa: E402
from decide import FRESH # noqa: E402
from induct import Field, Window, least, QF, le # noqa: E402
from hull import Coords, hull, eq # noqa: E402
from keyweld import forbidden, lt # noqa: E402
from firstreturn import three_gap, certified, read_piece # noqa: E402
from hullform import uv, forms # noqa: E402
def lin(*terms):
"""Sum of coef * key over (coef, key) pairs."""
return (sum(k * g for k, (g, h) in terms),
sum(k * h for k, (g, h) in terms))
def ykey(F, t, key):
return QF(key[1]) - F.r[t] * key[0]
def win_keys(F, t, m, c, f):
"""The window V(t, f)'s ends as keys, as derived."""
Kc, Kc1 = uv(F, t, c), uv(F, t, c + 1)
K0, K1 = uv(F, t, 0), uv(F, t, 1)
Ko, Ke = (Kc, Kc1) if c % 2 else (Kc1, Kc)
if f:
return lin((m, Ko), (-1, K1)), lin((m, Ke), (-1, K0))
if c % 2 == 0:
return lin((m, Kc1), (-1, K1)), lin((m, Kc), (m, Kc1), (-1, K0))
return lin((m, Kc), (m, Kc1), (-1, K1)), lin((m, Kc1), (-1, K0))
def pieces(F, t, m, c, f, plant_b=False):
"""The zero reply's forbidden pieces at (t, f), as derived:
[(ya, yb, ca, cb, key_a, key_b)]."""
K1, K2 = uv(F, t, 1), uv(F, t, 2)
Kc1, Kc2 = uv(F, t, c + 1), uv(F, t, c + 2)
KO, KE = (Kc1, Kc2) if (c + 1) % 2 else (Kc2, Kc1)
lk, hk = win_keys(F, t, m, c, f)
ylo, yhi = ykey(F, t, lk), ykey(F, t, hk)
if lt(yhi, ylo):
return []
out = []
for e in range(F.a(t + 2)):
Ea = lin((m, KE), (-1, K2), (e, K1))
Eb = lin((m, KO), (e + int(plant_b), K1))
ya, yb = ykey(F, t, Ea), ykey(F, t, Eb)
if not lt(ya, yb):
continue
ca = cb = False
if lt(ya, ylo):
ya, ca, Ea = ylo, True, lk
if lt(yhi, yb):
yb, cb, Eb = yhi, True, hk
if lt(ya, yb) or (ca and cb and eq(ya, yb)):
out.append((ya, yb, ca, cb, Ea, Eb))
return out
def passes(F, co, t, pc, zlo, zhi, scale=1, detail=None):
"""No hull key in the piece: no closed end in the hull and some
end's three-gap window holds the closed-form G-range."""
ya, yb, ca, cb, Ea, Eb = pc
for closed, E in ((ca, Ea), (cb, Eb)):
z = co.Z(*E, t)
if closed and le(zlo, z) and le(z, zhi):
return False
if not lt(ya, yb):
return True
npl, nmi = three_gap(F, t, yb - ya)
k = co.kap[t].f
glo = math.floor(zlo.f - k * yb.f)
ghi = math.ceil(zhi.f - k * ya.f)
ok = False
for E, hm, hp in ((Ea, -npl, nmi), (Eb, -nmi, npl)):
if detail is not None:
detail.append((E, hm, hp, (glo, ghi)))
if glo > E[0] + scale * hm and ghi < E[0] + scale * hp:
ok = True
return ok
def c_form(F, m, cmax=13, scale=1, plant_d=False, plant=None):
"""(first c with pinned moves, the formula's c)."""
cpin = None
for c in range(cmax + 1):
win = Window(F, m, c)
_st, miss = win.pin_starts()
if miss:
continue
cpin = c if cpin is None else cpin
co = Coords(F, m, c)
ok = True
for t in range(F.p):
fm = forms(F, co, m, c, t)
if plant_d:
fm[(False, False)] = fm[(True, False)]
if plant == "e":
fm[(False, False)] = fm[(True, False)]
fm[(True, False)] = co.Z(*uv(F, t, c - 1), t) * m
if plant == "f":
for f in (True, False):
fm[(f, True)] = fm[(f, True)] + co.Z(1, 0, t)
for f in (True, False):
for pc in pieces(F, t, m, c, f):
if not passes(F, co, t, pc, fm[(f, True)],
fm[(f, False)], scale):
ok = False
if ok:
return cpin, c
return cpin, None
def same_pieces(mine, ref):
if len(mine) != len(ref):
return False
return all(eq(a[0], b[0]) and eq(a[1], b[1]) and a[2] == b[2]
and a[3] == b[3] for a, b in zip(mine, ref))
def main():
t0 = time.time()
cells = kill = arm_n = arm_kill = 0
kill_list, ctl, cforms = [], [], {}
wk_bad = i_n = i_bad = ib_bad = ii_n = ii_bad = iii_n = iii_bad = 0
i_list, ii_list, iii_list = [], [], []
plant_c = plant_d = 0
plant_ef = {"e": 0, "f": 0}
for name, per in list(PERIODIC) + list(FRESH):
F = Field(per)
cname = name
for m in range(2, 10):
cells += 1
cinf = least(F, m, "pin")
cpin, cf = c_form(F, m)
cforms[(cname, m)] = cf
if cf != cinf:
kill += 1
kill_list.append((cname, m, cpin, cinf, cf))
if cinf is not None and cpin is not None and cinf > cpin:
arm_n += 1
arm_kill += cf != cinf
_, cfc = c_form(F, m, scale=2)
plant_c += cfc is not None and cinf is not None and cfc < cinf
_, cfd = c_form(F, m, plant_d=True)
plant_d += cfd is not None and cinf is not None and cfd < cinf
for pl in ("e", "f"):
_, cfp = c_form(F, m, plant=pl)
plant_ef[pl] += cfp != cinf
for c in range(cpin, (cinf or cpin) + 1):
win = Window(F, m, c)
st, miss = win.pin_starts()
if miss:
continue
co = Coords(F, m, c)
zhi, _ = hull(win, co, st)
zlo, _ = hull(win, co, st, low=True)
for t in range(F.p):
fm = forms(F, co, m, c, t)
for f in (True, False):
lk, hk = win_keys(F, t, m, c, f)
lo, hi = win.V[(t, f)]
wk_bad += not (eq(ykey(F, t, lk), lo)
and eq(ykey(F, t, hk), hi))
ii_n += 1
if not (eq(fm[(f, True)], zlo[(t, f)])
and eq(fm[(f, False)], zhi[(t, f)])):
ii_bad += 1
ii_list.append((cname, m, c, cinf, t, int(f)))
mine = pieces(F, t, m, c, f)
ref = forbidden(win, t, f, 0)
i_n += 1
if not same_pieces(mine, ref):
i_bad += 1
i_list.append((cname, m, c, t, int(f),
len(mine), len(ref)))
continue
ib_bad += same_pieces(
pieces(F, t, m, c, f, plant_b=True), ref)
for pc, rp in zip(mine, ref):
zl, zh = zlo[(t, f)], zhi[(t, f)]
ends, gr = read_piece(F, co, t, rp, zl, zh)
refok = certified(F, co, t, rp, zl, zh, ends,
gr)
iii_n += 1
myok = passes(F, co, t, pc, zl, zh)
if myok != refok:
iii_bad += 1
iii_list.append((cname, m, c, t, int(f),
myok, refok))
if (c == cinf and t == 0 and pc is mine[0]
and (cname, m) in (("bronze [3]", 3),
("golden [1]", 2))):
det = []
passes(F, co, t, pc, fm[(f, True)],
fm[(f, False)], detail=det)
ctl.append((cname, m, c, int(f), pc[4],
pc[5], det[1][1:]))
print("== CONTROLS")
print(" (a) phase 0, first piece (alpha, m, c_inf, flag, E_a, E_b, "
"(h-, h+) from E_b, G-range):")
for row in ctl:
print(" ", row)
print(f" c_form: bronze x3 {cforms[('bronze [3]', 3)]}, golden x2 "
f"{cforms[('golden [1]', 2)]}")
print(f" (b) THE PLANT E_b + K_1: (i)'s pieces read equal at "
f"{ib_bad} of {i_n - i_bad} (t, f) read")
print(f" (c) THE PLANT h+, h- doubled: c_form < c_inf at {plant_c} "
f"of {cells} cells")
print(f" (d) THE PLANT reduced upper end at K_c: c_form < c_inf at "
f"{plant_d} of {cells} cells")
print(f" (e) THE PLANT both upper ends one index down (added after "
f"the run): c_form != c_inf at {plant_ef['e']} of {cells}")
print(f" (f) THE PLANT both floors raised by Z(1, 0) (added after "
f"the run): c_form != c_inf at {plant_ef['f']} of {cells}")
print("== INGREDIENTS (c with pinned moves, first to c_inf)")
print(f" window ends as keys != Field.valid: {wk_bad} of {ii_n}")
print(f" (i) pieces != keyweld.forbidden(d = 0): {i_bad} of {i_n}; "
f"first: {i_list[:6]}")
print(f" (ii) forms != hull.py: {ii_bad} of {ii_n}; first: "
f"{ii_list[:6]}")
print(f" (iii) pass != firstreturn.certified (hull.py's values): "
f"{iii_bad} of {iii_n}; first: {iii_list[:6]}")
print("== P3")
print(f" arm c_inf > first pinned c: c_form != c_inf at {arm_kill} "
f"of {arm_n}")
print(f" apart: {kill_list[:10]}")
print(f" KILL: c_form != c_inf at {kill} of {cells} cells")
checks = [
[r[1:] for r in ctl] == [
(2, 3, 1, (8, 5), (16, 10), (-21, 13, (-2, 7))),
(2, 3, 0, (8, 5), (16, 10), (-21, 13, (4, 10))),
(3, 2, 1, (317, 96), (99, 30), (-251, 109, (-4, 30))),
(3, 2, 0, (317, 96), (99, 30), (-251, 109, (26, 100)))],
(cforms[("bronze [3]", 3)], cforms[("golden [1]", 2)]) == (2, 3),
ib_bad < i_n - i_bad,
plant_c > 0,
(plant_d, plant_ef["e"], plant_ef["f"]) == (0, 0, 0),
(wk_bad, i_bad, ii_bad, iii_bad) == (0, 0, 0, 0),
(ii_n, i_n, iii_n) == (1060, 1060, 903),
(cells, kill, arm_n, arm_kill) == (136, 0, 108, 0),
]
print(f" {sum(checks)}/{len(checks)} checks as recorded, "
f"{time.time() - t0:.1f} s")
sys.exit(0 if all(checks) else 1)
if __name__ == "__main__":
main()