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