decide.py
Cited on: FLUSH.
To run it: save decide.py, with anchors.py, flush.py, gaps.py, hull.py, induct.py, ostrowski.py, tie.py beside it; standard library only.
"""
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()