""" decide.py -- which component, then which reply, decides c_inf: the observation at c_inf - 1, then ZERO and TWO. QUESTION. anchors.py prints that c_inf is, at the 39 live cells, the least c at which no component of B(t, f, c) has one of its four candidates with Z in W, yet at c_inf - 1 many hit components miss all four. Which component carries the cell's hit: is it one label (a flag, a reply, an end's source)? DESIGN. An OBSERVATION first (no kill). At c = c_inf - 1 per live cell, for each component C of B(t, f, c): (t, f); D(C), the replies d leaving C's midpoint in no J(d, e); each end's source, V's lo / hi or the lo / hi end of J(d, e); TRUE, the keys of H(c) in C with y bad (c_enum's ground truth); the four candidates that hit, with G'. OBSERVED (the --wide run, the 39 live cells at c_inf - 1, fitted, not evidence for them). Every cell has a component holding a true key whose bad replies at its midpoint are exactly {0}: cells with none, 0 (so 0 in D, 0). Labels that miss: d_max in D at 9 cells, the full flag at 2 (silver x3, bronze x4), the reduced flag at 6. ZERO (frozen before its engine). B_0(t, f, c) = the y of V(t, f) with no e in 0..a_(t+2) putting -y / r_t + e r_(t+1) in V(t + 1, full): bad under the zero reply; B_0 is in B, so c_0 = the least c with the pinned moves and no key of H(c) in B_0 is at most c_enum. WHY (by hand): the zero reply targets the full window, shorter than the reduced by m |theta| at the window's depth (the full R spans |theta_c| + |theta_(c+1)|, the reduced |theta_c|), so J(0, e)'s gaps are the longest of B's interior gaps (its edge pieces unpriced): a length reason, not a containment. Its weak corner: many nonzero replies, large c. FAMILY (built there, not drawn): period at most 2, quotients 1..5, one per cycle, not among the six: [4], [5], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]; m = 2..9. PREDICTION: c_0 = c_inf at every live cell. KILL: "c_0 < c_inf at n of N cells where it can fire", N the cells with a key of H(c) in B and not B_0 at some pinned c < c_inf, on the fresh family; n > 0 kills. CONTROLS: (a) y in B_0 iff the engine's zero reply (induct.py's pre, moves) leaves no valid move, every key of H(c), every c read; (b) golden x2, c = 2, key (3, 2) reduced in B_0 (by hand: y 0.1459 between J(0, 0)'s top 0.0557 and J(0, 1)'s foot 0.2918); (c) c_enum = c_inf at every cell; (d) THE PLANT: the top reply alone in place of 0 must print c < c_inf where it can fire. FINDINGS (the bare run's ZERO, copied from its prints). KILL MISSED. Fresh: c_0 < c_inf at 0 of 55 cells where it can fire (88 cells, 69 live, c_inf 2 to 5: the many-replies corner, not the large-c one). Fitted: 0 of 20 (48 cells, 39 live, c_inf 2 to 7). So at the 75 cells where the kill could fire, the 55 fresh ones the test, c_inf is the least c with the pinned moves at which every key of the hull set H(c) has a valid move after the zero reply; elsewhere it holds by construction and (c). THE ZERO REPLY ALONE (added at an audit, after the verdict): the pinned keys' closure under the zero reply alone and every valid move keeps a valid move after the zero reply at every pinned c read: it fails at 0 of 265 pinned (cell, c), c <= c_inf, both families. CONTROLS. (a) 0 disagreements over 108108 keys; its plant (e <= a_(t+2) - 1, added at the audit) disagrees at 27343: (a) can fire. (b) True, as by hand. (c) c_enum != c_inf at 0 of 48 and 0 of 88. (d) the top reply alone: c < c_inf at 9 of 39 (fitted) and 13 of 69 (fresh) cells where it can fire: the kill can fire. BY HAND (after the verdict, no run). The zero reply's pre key is (H, G - a_(t+1) H) at t + 1, y1 = -y / r_t, Z1 = r_t Z (hull.py's identities); the move e adds e r_(t+1) to y1 and -e lam_(t+1) to Z1. J(0, e) = J(0, 0) + e r_t r_(t+1) = J(0, 0) + y(a_(t+1) e, e), so a key in the zero gap e is a key in gap 0 shifted by the key (a_(t+1) e, e). Two closed forms die here: "c_inf is where the zero gaps close" (golden x2: |V_F| = 1 - 2 r^c, the gap open until c = 4, but c_inf = 3, the gap at c = 3 of length r (r - 1 + 2 r^3) = 0.0557 holding no key of H(3)); and "the zero input alone decides" (zero replies keep the flag full, and at silver x3 and bronze x4 no full-flag component holds a true key at c_inf - 1, so the zero-only closure cannot fail there, a reading of the --wide print; THE ZERO REPLY ALONE prints it at every pinned c): the binding key follows a nonzero digit. TWO (frozen before its engine). C_R(c) = the pinned keys' closure under the replies R(t, f) and every valid move; c_R = the least pinned c <= c_inf at which every key of C_R(c) has a valid move after the zero reply. Arms: c_zp (R = {0}), c_2 (R = {0, d_max}), c_a0 (every reply), c_all (every reply, every reply tested); c_zp <= c_2 <= c_a0 <= c_all = c_inf by inclusion. PREDICTION: c_a0 = c_inf at every cell (ZERO moved from H(c) to the pinned closure), c_2 = c_inf where it can fire. KILL: "c_2 < c_inf at n of N cells where it can fire", N the cells with a key of H(c) in B_0 outside C_2(c) at some pinned c < c_inf; n > 0 kills. Read after the verdict: N overcounts, as where every quotient is 1 C_2 is the pinned closure, so c_2 = c_a0 there. FINDINGS (the bare run's TWO, copied from its prints). KILL FIRED. c_2 < c_inf at 5 of 33 fitted cells (silver x4, bronze x4, x5, x8, x9) and 31 of 66 fresh: the replies 0 and d_max do not decide c_inf. The shortest reply strings reaching the stranded keys use every reply, single middle letters among them ((2,) at bronze x5, (3,) at [2, 4] x3, (2,) and (4,) at [3, 5] x8). THE ATTRIBUTION ARM HELD. c_a0 < c_inf at 0 of 28 fitted and 0 of 41 fresh cells where it can fire: at every pinned c < c_inf the pinned closure itself holds a key the zero reply strands, so c_inf is the least c with the pinned moves at which every key of the pinned closure has a valid move after the zero reply (both families, c_inf 2 to 7; a pattern). CONTROLS. (a) c_all = c_inf at 48 of 48 and 88 of 88; the closure with every reply equals induct.py's at every pinned (cell, c). (b) C_2 and the pinned closure lie in H(c) everywhere read. (c) THE PLANT: replies {0} agree with zero_only at 265 of 265 pinned (cell, c) and read c_zp < c_inf at 33 of 33 and 66 of 66 live cells where the kill can fire, and at 39 of 39 and 69 of 69 live cells, which follows from THE ZERO REPLY ALONE's 0 of 265, so the plant reads nothing; the kill's power is its firing. RUN RECORD. --wide 1.3 s; ZERO 6.7 s, both families; TWO 6.6 s, peak commit 12.6 MB. The label counts were folded into the --wide print after ZERO's verdict, from a scratch tally that printed the same counts. At an audit: the zero-only closure and (a)'s plant, ZERO's other prints unchanged (6.7 s); at a second audit the closure read at every pinned c, not its first. Usage: python decide.py [--wide] (bare: ZERO, then TWO, on both families at m = 2 .. 9; --wide: the observation at c_inf - 1, m = 2 .. 9) """ import os import sys import time from fractions import Fraction as Fr os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") from flush import PERIODIC # noqa: E402 from induct import Field, Window, least, QF, le # noqa: E402 from hull import Coords, dmax, hull, hull_set # noqa: E402 from gaps import Bad, cmp # noqa: E402 from anchors import anchor, Strip # noqa: E402 WIDE = "--wide" in sys.argv FRESH = [(f"{list(q)}", q) for q in [(4,), (5,), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]] HALF = Fr(1, 2) def sources(B, win, t, f, x): """Where the end x comes from: 'Vlo', 'Vhi', or (d, e, 'lo'/'hi').""" out = [] lo, hi = win.V[(t, f)] if cmp(x, lo) == 0: out.append("Vlo") if cmp(x, hi) == 0: out.append("Vhi") for d, js in zip(win.replies(f, t), B.J[(t, f)]): for e, (a, b) in enumerate(js): if cmp(x, a) == 0: out.append((d, e, "lo")) if cmp(x, b) == 0: out.append((d, e, "hi")) return out def bad_replies(B, win, t, f, y): return [d for d, js in zip(win.replies(f, t), B.J[(t, f)]) if not any(le(a, y) and le(y, b) for a, b in js)] def main(): t0 = time.time() maps = (2, 3, 4, 5, 6, 7, 8, 9) rows = [] for name, per in PERIODIC: F = Field(per) p = F.p for m in maps: c_inf = least(F, m, "pin") c = c_inf - 1 if c < 0: continue 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) Hs = hull_set(win, co, zlo, zhi) B = Bad(win) cell = [] for t in range(p): for f in (True, False): z0, z1 = zlo[(t, f)], zhi[(t, f)] dm = dmax(F, c, t, f) for comp in B.components(t, f): a, b = comp mid = (a + b) * QF(HALF) D = bad_replies(B, win, t, f, mid) tru = sorted( k[:2] for k in Hs if k[2] == f and k[3] == t and le(a, win.y(k[0], k[1], t)) and le(win.y(k[0], k[1], t), b) and B.bad(win.y(k[0], k[1], t), t, f)) Pa, Pb = anchor(F, t, a), anchor(F, t, b) S = Strip(win, B, t, f, comp) ins = [] for nm, P in (("a", Pa), ("b", Pb)): cands = [] if S.at(P[0]) == P: cands.append((nm, 0, P)) for s in (1, -1): g, k = S.ret(P, s) cands.append( (nm + ("up" if s > 0 else "dn"), g, k)) for kd, g, k in cands: z = co.Z(k[0], k[1], t) if le(z0, z) and le(z, z1): ins.append((kd, g)) cell.append(dict( t=t, f=f, dm=dm, D=D, comp=(a.f, b.f), sa=sources(B, win, t, f, a), sb=sources(B, win, t, f, b), tru=tru, ins=ins, Pa=Pa, Pb=Pb, za=co.Z(*Pa, t).f, zb=co.Z(*Pb, t).f, W=(z0.f, z1.f))) rows.append((name, m, c_inf, p, cell)) print("== DECIDE: at c_inf - 1, each component of B") for name, m, c_inf, p, cell in rows: print(f" {name} x{m} c_inf {c_inf} (p {p})") for r in cell: mark = ("TRUE" if r["tru"] else " ") + \ (" HIT" if r["ins"] else " ") print(f" {mark} t {r['t']} {'F' if r['f'] else 'R'} " f"dmax {r['dm']} D {r['D']} " f"({r['comp'][0]:.4f}, {r['comp'][1]:.4f}) " f"ends {r['sa']} / {r['sb']} " f"Z_a {r['za']:.2f} Z_b {r['zb']:.2f} " f"W [{r['W'][0]:.2f}, {r['W'][1]:.2f}] " f"true {len(r['tru'])} hits {r['ins']}") labels = {"D = {0}": lambda r: r["D"] == [0], "0 in D": lambda r: 0 in r["D"], "d_max in D": lambda r: r["dm"] in r["D"], "the full flag": lambda r: r["f"], "the reduced flag": lambda r: not r["f"]} for lab, P in labels.items(): bad = [f"{name.split()[0]} x{m}" for name, m, _, _, cell in rows if not any(P(r) for r in cell if r["tru"])] print(f" cells with no true component of label {lab}: {len(bad)}" f" {bad}") print(f" {len(rows)} live cells read, {time.time() - t0:.1f} s") def outside(js, y): return not any(le(a, y) and le(y, b) for a, b in js) def zero_only(win, limit=200000): """Does every key of the pinned keys' closure under the zero reply alone and every valid move keep a valid move after the zero reply?""" p = win.F.p st, _ = win.pin_starts() seen, todo = set(st), list(st) while todo: G, H, f, t = todo.pop() t1 = (t + 1) % p G1, H1 = win.pre(G, H, t, 0) mv = win.moves(G1, H1, True, t1) if not mv: return False for k in mv: key = (k[0], k[1], True, t1) if key not in seen: seen.add(key) todo.append(key) if len(seen) > limit: raise RuntimeError("closure past its limit") return True def zero_cell(F, m, ctl): """(c_inf, c_enum, c_0, c_top, live, can_fire, can_fire_top, c_zp).""" c_inf = least(F, m, "pin") if c_inf is None: return None p = F.p c_enum = c_0 = c_top = c_zp = None live = fire = fire_top = False for c in range(c_inf + 1): win = Window(F, m, c) st, miss = win.pin_starts() if miss: continue ctl["zp_read"] += 1 if zero_only(win): c_zp = c if c_zp is None else c_zp else: ctl["zp_fail"] += 1 co = Coords(F, m, c) zhi, _ = hull(win, co, st) zlo, _ = hull(win, co, st, low=True) Hs = hull_set(win, co, zlo, zhi) B = Bad(win) inB = in0 = inT = False for G, H, f, t in Hs: y = win.y(G, H, t) js = B.J[(t, f)] b0 = outside(js[0], y) bt = outside(js[-1], y) bb = B.bad(y, t, f) G1, H1 = win.pre(G, H, t, 0) eng = not win.moves(G1, H1, True, (t + 1) % p) ctl["a_keys"] += 1 ctl["a_bad"] += eng != b0 ctl["a_plant"] += eng != outside(js[0][:-1], y) if (F.per == (1,) and m == 2 and c == 2 and (G, H) == (3, 2) and not f): ctl["b"] = b0 inB |= bb in0 |= b0 inT |= bt if c < c_inf and bb and not b0: fire = True if c < c_inf and bb and not bt: fire_top = True if c < c_inf: live = True if c_enum is None and not inB: c_enum = c if c_0 is None and not in0: c_0 = c if c_top is None and not inT: c_top = c return c_inf, c_enum, c_0, c_top, live, fire, fire_top, c_zp def zero(): t0 = time.time() ctl = {"a_keys": 0, "a_bad": 0, "a_plant": 0, "b": None, "zp_read": 0, "zp_fail": 0} for label, fam in (("fitted", PERIODIC), ("fresh", FRESH)): none = cells = live = N = n = enum_bad = Nt = nt = 0 for name, per in fam: F = Field(per) for m in range(2, 10): r = zero_cell(F, m, ctl) if r is None: none += 1 print(f" {label} {name} x{m}: c_inf None", flush=True) continue c_inf, c_enum, c_0, c_top, lv, fire, fire_t, c_zp = r cells += 1 live += lv enum_bad += c_enum != c_inf N += fire n += fire and c_0 < c_inf Nt += fire_t nt += fire_t and c_top < c_inf print(f" {label} {name} x{m}: c_inf {c_inf} c_enum " f"{c_enum} c_0 {c_0} c_top {c_top} live {lv} " f"can fire {fire} (top {fire_t}) c_zp {c_zp}", flush=True) print(f"== ZERO, {label} family: {cells} cells ({none} with c_inf " f"None), {live} live") print(f" (c) c_enum != c_inf at {enum_bad} of {cells}") print(f" (d) THE PLANT (top reply alone): c_top < c_inf at {nt} of " f"{Nt} cells where it can fire") print(f" ZERO KILL ({label}): c_0 < c_inf at {n} of {N} cells " f"where it can fire") print(f" (a) B_0 against the engine's zero reply: {ctl['a_bad']} " f"disagreements over {ctl['a_keys']} keys; its plant (e <= " f"a_(t+2) - 1) disagrees at {ctl['a_plant']}") print(f" (b) golden x2, c = 2, key (3, 2) reduced, in B_0: {ctl['b']}") print(f" the zero reply alone, from the pinned keys: its closure fails at " f"{ctl['zp_fail']} of {ctl['zp_read']} pinned (cell, c) read, " f"c <= c_inf, both families") print(f" {time.time() - t0:.1f} s") def closure_r(win, reps, starts, limit=400000): """The closure of starts under the replies reps(f, t) and every valid move, with each key's first parent (key, reply).""" p = win.F.p par = {k: None for k in starts} todo = list(starts) while todo: G, H, f, t = todo.pop(0) t1 = (t + 1) % p for d in reps(f, t): G1, H1 = win.pre(G, H, t, d) for G2, H2 in win.moves(G1, H1, d == 0, t1): k = (G2, H2, d == 0, t1) if k not in par: par[k] = ((G, H, f, t), d) todo.append(k) if len(par) > limit: raise RuntimeError("closure past its limit") return par def zero_bad(win, key): G, H, f, t = key G1, H1 = win.pre(G, H, t, 0) return not win.moves(G1, H1, True, (t + 1) % win.F.p) def word(par, k): out = [] while par[k] is not None: k, d = par[k] out.append(d) return tuple(reversed(out)) def two_cell(F, m, ctl): """Per cell: c_inf, the four arms' least c, live, N, N' flags.""" c_inf = least(F, m, "pin") if c_inf is None: return None arms = {"zp": None, "2": None, "a0": None, "all": None} live = fire2 = fire0 = False words = [] for c in range(c_inf + 1): win = Window(F, m, c) st, miss = win.pin_starts() if miss: continue reps = {"zp": lambda f, t: (0,), "2": lambda f, t, c=c: sorted({0, dmax(F, c, t, f)}), "a0": lambda f, t, w=win: w.replies(f, t)} S = {a: closure_r(win, r, st) for a, r in reps.items()} ok_all, S_eng, _bad = win.closure(st) ctl["all_set"] += set(S["a0"]) != S_eng bad = {a: {k for k in S[a] if zero_bad(win, k)} for a in S} zp_old = zero_only(win) ctl["zp_read"] += 1 ctl["zp_dis"] += zp_old != (not bad["zp"]) for a in ("zp", "2", "a0"): if arms[a] is None and not bad[a]: arms[a] = c if arms["all"] is None and ok_all: arms["all"] = c co = Coords(F, m, c) zhi, _ = hull(win, co, st) zlo, _ = hull(win, co, st, low=True) Hs = hull_set(win, co, zlo, zhi) ctl["inH"] += (not set(S["2"]) <= Hs) + (not S_eng <= Hs) hb0 = {k for k in Hs if zero_bad(win, k)} if c < c_inf: live = True fire2 |= bool(hb0 - set(S["2"])) fire0 |= bool(hb0 - set(S["a0"])) if not bad["2"] and bad["a0"]: ws = sorted({word(S["a0"], k) for k in bad["a0"]}, key=lambda w: (len(w), w)) words.append((c, len(bad["a0"]), ws[:4])) return c_inf, arms, live, fire2, fire0, words def two(): t0 = time.time() ctl = {"all_set": 0, "zp_read": 0, "zp_dis": 0, "inH": 0} for label, fam in (("fitted", PERIODIC), ("fresh", FRESH)): cells = none = live = N = n = N0 = n0 = all_bad = 0 Np = np_ = zl = 0 for name, per in fam: F = Field(per) for m in range(2, 10): r = two_cell(F, m, ctl) if r is None: none += 1 continue c_inf, a, lv, f2, f0, words = r cells += 1 live += lv all_bad += a["all"] != c_inf N += f2 n += f2 and a["2"] < c_inf N0 += f0 n0 += f0 and a["a0"] < c_inf Np += lv and f2 np_ += lv and f2 and a["zp"] < c_inf zl += lv and a["zp"] < c_inf print(f" {label} {name} x{m}: c_inf {c_inf} c_all " f"{a['all']} c_a0 {a['a0']} c_2 {a['2']} c_zp " f"{a['zp']} live {lv} can fire {f2} (a0 {f0})", flush=True) for c, nb, ws in words: print(f" c = {c}: {nb} keys of the pinned closure " f"in B_0, none in C_2; shortest reply strings " f"{ws}") print(f"== TWO, {label} family: {cells} cells ({none} with c_inf " f"None), {live} live") print(f" (a) c_all != c_inf at {all_bad} of {cells}") print(f" (c) THE PLANT (replies {{0}}): c_zp < c_inf at {np_} of " f"{Np} live cells where the kill can fire, at {zl} of " f"{live} live cells") print(f" the attribution arm: c_a0 < c_inf at {n0} of {N0} cells " f"where it can fire") print(f" TWO KILL ({label}): c_2 < c_inf at {n} of {N} cells " f"where it can fire") print(f" (a') the closure with every reply against induct.py's: " f"{ctl['all_set']} pinned (cell, c) differ") print(f" (b) C_2 or the pinned closure outside H(c) at {ctl['inH']} " f"(closure, pinned (cell, c))") print(f" (c) replies {{0}} against decide.py's zero_only: " f"{ctl['zp_dis']} of {ctl['zp_read']} pinned (cell, c) disagree") print(f" {time.time() - t0:.1f} s") if __name__ == "__main__": if WIDE: main() else: zero() two()