""" gaps.py -- the bad offsets of the window as exact intervals, read against the largest gap of the offsets the hull's Z span admits: is c_inf a statement about lengths alone? QUESTION. hull.py prints that c_inf is, at all 48 cells, the least c at which the window is inductive on the hull set H(c), every valid key (G, H, f, t) with Z_lo(t, f) <= Z <= Z_hi(t, f), Z = G + kappa_t y, y = H - G r_t. A move's validity reads y alone. Is c_inf the least c at which no bad interval is longer than the largest gap among the offsets the hull's Z span admits? DESIGN (frozen before the engine). THE MOVE: reply d, move e (0 <= e <= a_(t+2)) send y to y' = -y / r_t + s, s = m d W_t + e r_(t+1), W_t = V_t - U_t r_(t+1) (theta_(t+c+1) = U_t theta_(t+1) + V_t theta_t). y' lies in V(t+1, d == 0) = [lo1, hi1] iff y lies in J(d, e) = [r_t (s - hi1), r_t (s - lo1)]. THE BAD OFFSETS: B(t, f, c) = the y of V(t, f) with a reply d leaving y in no J(d, e), a finite union of intervals relatively open in V(t, f), its components read exactly in the quadratic field. THE LATTICE: (G, H) -> (y, Z) has determinant -1, and |V| < 1, so H(c) at (t, f) is the lattice's points in V x [Z_lo, Z_hi], one per G at most. CERTAIN HIT (proved): a component of length l, inf a, sup b; every G in [Z_lo - kappa a, Z_hi - kappa b] whose offset -G r_t mod 1 falls in (a, b) gives a key of H(c) in B, that interval holds n = floor(L - kappa l) consecutive integers, L = Z_hi - Z_lo, and if the largest circle gap g(n) of n consecutive offsets (n and r_t only: the three-distance theorem) is < l, one falls there and WI fails on H(c). c_nec = the least c with the pinned moves and no component certainly hit; c_nec <= c_hull (= c_inf at 48, hull.py). It reads l, L, kappa_t and r_t, never where B sits or where the offsets fall. PREDICTION: c_nec = c_inf at all 48 cells. KILL: "c_nec < c_inf at n of 48 cells", n > 0: there position decides. c_nec > c_inf is an instrument fault, printed apart. Beside it, no kill: at c_inf - 1, whether the first failing key's component is certainly hit; L(t, f) at c_inf. CONTROLS (read before the verdict): (a) at every c up to c_inf, every key of H(c): y in B iff some reply leaves it no valid move (induct.py's moves), 0 disagreements; PLANT: B built with e <= a_(t+2) - 1 must disagree at some key; (b) c_enum, the least c with no key of H(c) in B, equals c_hull at 48 of 48; (c) g(n) against the three-distance theorem: at most 3 distinct gaps, the largest the sum of the other two when 3, at every n used; golden n = 8: gaps ||5 r|| and ||3 r||; (d) every component called certainly hit holds a key of H(c), 0 violations (proved); (e) THE PLANT, in the kill's direction: n halved must print c_nec < c_inf at some cell. FINDINGS (the --wide run, copied from its prints). KILL FIRED. c_nec < c_inf at 14 of 48 cells: golden x2, x3, x7, silver x3, x5, bronze x4, x9, sqrt(3) - 1 x2, x3, x4, V1 x2, x6, V2 x2, x3, each by one (11 of the 24 at m = 2..5). There, at c_inf - 1, the certain-hit test (g(n) < l, n = floor(L - kappa l)) fires on no component, yet a key of H lands in one: this length test does not reach c_inf. A length test on the exact count of admitted G is read only at golden x2, where it also misses (below); at the other 13 it is not run, and the frozen reading "position decides" is wider than this. Golden x2, c = 2, reduced flag: B's one component (0.0557, 0.2918) (its inf phi^-6), l 0.2361, L 4.2361, n 4, g(4) 0.3820 > l; the key (3, 2), y 0.1459, Z 3.0652, lies in it; the G interval [Z_lo - kappa a, Z_hi - kappa b] holds 5 integers, and g(5) = l exactly (sign 0): at the exact count it is a tie, not a certain hit (by hand: the sup b = y(6, 4) and Z(6, 4) = Z_hi, so one of the 5 offsets sits on the end, outside the open arc). At c_inf - 1 the first failing key's component is certainly hit at 22 cells and not at 17; 9 cells have no pinned move at c_inf - 1. B'S ENDS ARE LATTICE OFFSETS (by hand, not printed): r_t r_(t+1) = 1 - a_(t+1) r_t and every theta_k / theta_(t-1) is an integer combination of 1 and r_t, so each end of B is the offset of one integer key, its anchor (golden x2, c = 2: inf phi^-6 = y(8, 5), sup y(6, 4)); the keys of H in a component are the inf's anchor plus the lattice vectors v with 0 < y(v) < l and Z(anchor) + Z(v) in [Z_lo, Z_hi], an end's own key joining when the end is bad (golden x2, c = 2: (3, 2) = (8, 5) + v, v = (-5, -3), y(v) = 0.0902). L = Z_hi - Z_lo at c_inf: 5.683 to 2262.950 over the 208 rows. c_nec > c_inf (instrument fault): 0 cells. CONTROLS. (a) y in B against the engine's moves: 0 disagreements over 25987 keys; the plant (e <= a_(t+2) - 1) disagrees at 10311: (a) can fire. (b) c_enum = c_hull = c_inf at 48 of 48. (c) 0 of the 197 n used break the three-distance theorem; golden n = 8 gaps 0.1459 and 0.0902 against ||3 r|| and ||5 r||. (d) 0 of 162 components called certainly hit hold no key of H. (e) n halved prints c_nec < c_inf at 20 of 48: the kill can fire. RUN RECORD. Bare 0.8 s (KILL 11 of 24, the controls as above at m = 2..5); --wide 2.5 s, peak commit 9.9 MB. The golden x2 line and the count of cells with no pinned move at c_inf - 1 were added after the verdict, the other prints unchanged. The frozen side print "L(t, f) against m L_t" prints L's range only. Usage: python gaps.py [--wide] (--wide adds m = 6 .. 9) """ import math import os import sys import time from fractions import Fraction as Fr from functools import cmp_to_key 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, hull, hull_set, wi # noqa: E402 WIDE = "--wide" in sys.argv HALF = Fr(1, 2) def cmp(x, y): d = x.f - y.f if abs(d) > 1e-9: return 1 if d > 0 else -1 return (x - y).sign() def qfloor(x): k = math.floor(x.f) if (x - QF(k)).sign() < 0: k -= 1 elif (x - QF(k + 1)).sign() >= 0: k += 1 return k class Bad: """B(t, f, c) of one window, exact.""" def __init__(self, win, ecut=0): self.win, F, p = win, win.F, win.F.p self.J = {} for t in range(p): t1 = (t + 1) % p U, V = win.UV[t] W = QF(V) - F.r[t1] * U r = F.r[t] for f in (True, False): per_d = [] for d in win.replies(f, t): lo1, hi1 = win.V[(t1, d == 0)] js = [] for e in range(F.a(t + 2) + 1 - ecut): s = W * (win.m * d) + F.r[t1] * e js.append((r * (s - hi1), r * (s - lo1))) per_d.append(js) self.J[(t, f)] = per_d def bad(self, y, t, f): """y (in V(t, f)) has a reply with no valid move.""" return any(not any(le(a, y) and le(y, b) for a, b in js) for js in self.J[(t, f)]) def components(self, t, f): """[(inf, sup)] of B(t, f, c), exact.""" lo, hi = self.win.V[(t, f)] pts = [lo, hi] for js in self.J[(t, f)]: for a, b in js: for x in (a, b): if le(lo, x) and le(x, hi): pts.append(x) pts.sort(key=cmp_to_key(cmp)) uniq = [pts[0]] for x in pts[1:]: if cmp(x, uniq[-1]) != 0: uniq.append(x) elems = [] # (left, right, member) for i, x in enumerate(uniq): elems.append((x, x, self.bad(x, t, f))) if i + 1 < len(uniq): mid = (x + uniq[i + 1]) * HALF elems.append((x, uniq[i + 1], self.bad(mid, t, f))) out, cur = [], None for left, right, mem in elems: if mem: cur = (cur[0] if cur else left, right) elif cur: out.append(cur) cur = None if cur: out.append(cur) return out GCACHE = {} def gaps(F, t, n): """The distinct circle gaps of n consecutive offsets G r_t mod 1, exact, largest first.""" key = (F.per, t, n) if key in GCACHE: return GCACHE[key] r = F.r[t] xs = [] for G in range(n): x = r * G xs.append(x - QF(qfloor(x))) xs.sort(key=lambda x: x.f) gs = [xs[i + 1] - xs[i] for i in range(n - 1)] gs.append(QF(1) + xs[0] - xs[-1]) gs.sort(key=cmp_to_key(cmp), reverse=True) uniq = [gs[0]] for g in gs[1:]: if cmp(g, uniq[-1]) != 0: uniq.append(g) GCACHE[key] = uniq return uniq def certain(F, co, t, comp, L, half=False): a, b = comp ell = b - a n = qfloor(L - co.kap[t] * ell) if half: n //= 2 if n < 2: return False, n return (ell - gaps(F, t, n)[0]).sign() > 0, n def main(): t0 = time.time() maps = (2, 3, 4, 5) + ((6, 7, 8, 9) if WIDE else ()) kill = fault = cells = 0 half_kill = 0 a_dis = a_keys = a_plant = 0 b_bad = 0 d_viol = d_hits = 0 gap_fail, ns_used = 0, set() lucky = sure = 0 nopin_prev = 0 diag = [] Lrows = [] for name, per in PERIODIC: F = Field(per) p = F.p for m in maps: c_inf = least(F, m, "pin") c_nec = c_half = c_enum = c_hull = None first_fail = None for c in range(c_inf + 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) Hs = hull_set(win, co, zlo, zhi) B = Bad(win) Bp = Bad(win, ecut=1) any_in_B = False for G, H, f, t in Hs: y = win.y(G, H, t) mine = B.bad(y, t, f) eng = False for d in win.replies(f, t): G1, H1 = win.pre(G, H, t, d) if not win.moves(G1, H1, d == 0, (t + 1) % p): eng = True break a_keys += 1 a_dis += mine != eng a_plant += Bp.bad(y, t, f) != eng any_in_B |= mine if c_enum is None and not any_in_B: c_enum = c bad_key = wi(win, Hs) if c_hull is None and bad_key is None: c_hull = c hit = hit_half = False comp_of_fail = None for t in range(p): for f in (True, False): L = zhi[(t, f)] - zlo[(t, f)] if c == c_inf: Lrows.append(L.f) for comp in B.components(t, f): ok, n = certain(F, co, t, comp, L) okh, _ = certain(F, co, t, comp, L, half=True) if n >= 2: ns_used.add((F.per, t, n)) hit |= ok hit_half |= okh if ok: d_hits += 1 a, b = comp d_viol += not any( k[2] == f and k[3] == t and cmp(a, win.y(k[0], k[1], t)) < 0 and cmp(win.y(k[0], k[1], t), b) < 0 for k in Hs) if bad_key and bad_key[2] == f and \ bad_key[3] == t: y = win.y(bad_key[0], bad_key[1], t) if le(comp[0], y) and le(y, comp[1]): comp_of_fail = ok if (name.startswith("golden") and m == 2 and c == c_inf - 1): a, b = comp lo_g = zlo[(t, f)] - co.kap[t] * a hi_g = zhi[(t, f)] - co.kap[t] * b cnt = qfloor(hi_g) - qfloor(lo_g) cnt += (lo_g - QF(qfloor(lo_g)) ).sign() == 0 ell = b - a diag.append( f"golden x2, c = {c}, t {t} " f"{'full' if f else 'reduced'}: " f"component ({a.f:.4f}, " f"{b.f:.4f}), l {ell.f:.4f}, L " f"{L.f:.4f}, n {n}, g(n) " f"{gaps(F, t, n)[0].f:.4f}; " f"the failing key {bad_key[:2]}" f" (y {y.f:.4f}, Z " f"{co.Z(bad_key[0], bad_key[1], t).f:.4f}); " f"integers in [Z_lo - kappa a, " f"Z_hi - kappa b]: {cnt}, g of " f"that many {gaps(F, t, cnt)[0].f:.4f}" f", l - g exactly sign " f"{(ell - gaps(F, t, cnt)[0]).sign()}") if c_nec is None and not hit: c_nec = c if c_half is None and not hit_half: c_half = c if c == c_inf - 1 and bad_key is not None: first_fail = comp_of_fail cells += 1 nopin_prev += (c_inf >= 1 and Window(F, m, c_inf - 1).pin_starts()[1] > 0) if c_nec is None or c_nec > c_inf: fault += 1 elif c_nec < c_inf: kill += 1 half_kill += c_half is not None and c_half < c_inf b_bad += c_enum != c_hull or c_hull != c_inf if first_fail is True: sure += 1 elif first_fail is False: lucky += 1 print(f" {name:20s} x{m} c_inf {c_inf} c_nec {c_nec} " f"(n halved {c_half}) c_enum {c_enum} c_hull {c_hull}; " f"c_inf - 1's first failure certainly hit: {first_fail}", flush=True) for per, t, n in sorted(ns_used): F = Field(per) g = gaps(F, t, n) gap_fail += len(g) > 3 or (len(g) == 3 and cmp(g[0], g[1] + g[2]) != 0) F = Field((1,)) g8 = gaps(F, 0, 8) r = F.r[0] want = sorted([abs((r * 5 - QF(3)).f), abs((r * 3 - QF(2)).f)]) print("== GAPS: c_inf against the bad offsets' lengths") print(f" (a) y in B against the engine's moves: {a_dis} disagreements " f"over {a_keys} keys; PLANT (e <= a_(t+2) - 1): {a_plant}") print(f" (b) c_enum = c_hull = c_inf failing at {b_bad} of {cells}") print(f" (c) three-distance: {gap_fail} of {len(ns_used)} n used " f"break it; golden n = 8 gaps " f"{', '.join(f'{x.f:.4f}' for x in g8)} against " f"{', '.join(f'{x:.4f}' for x in want)}") print(f" (d) components called certainly hit holding no key of H: " f"{d_viol} of {d_hits}") print(f" (e) THE PLANT (n halved): c_nec < c_inf at {half_kill} of " f"{cells} cells") print(f" c_inf - 1's first failing key in a component certainly hit " f"at {sure} cells, not at {lucky}") print(f" cells with no pinned move at c_inf - 1: {nopin_prev}") for x in diag: print(" " + x) print(f" L = Z_hi - Z_lo at c_inf over {len(Lrows)} rows: " f"{min(Lrows):.3f} to {max(Lrows):.3f}") print(f" c_nec > c_inf (instrument fault): {fault} cells") print(f" KILL: c_nec < c_inf at {kill} of {cells} cells") print(f" {time.time() - t0:.1f} s") if __name__ == "__main__": main()