File size: 3,459 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #!/usr/bin/env python3
P = 998244353
def evaluate(n, instructions):
dp = {}
vis = set()
def solve(i, x):
if (i, x) in dp: return dp[(i, x)]
if (i, x) in vis: return None
vis.add((i, x))
inst = instructions[i]
if inst[0] == 'POP':
_, pop_c, g1, push_c, g2 = inst
if x == pop_c:
dp[(i, x)] = (g1, 1)
else:
r = solve(g2, push_c)
if r is None: return None
j, u = r
r2 = solve(j, x)
if r2 is None: return None
k, v = r2
dp[(i, x)] = (k, (u + v + 1) % P)
else:
_, push_c, g2 = inst
if x == 0:
dp[(i, x)] = (-1, 1)
else:
r = solve(g2, push_c)
if r is None: return None
j, u = r
r2 = solve(j, x)
if r2 is None: return None
k, v = r2
dp[(i, x)] = (k, (u + v + 1) % P)
return dp[(i, x)]
r = solve(0, 0)
if r is None: return -1
return r[1]
# Let me try various non-chain structures with d=3 and extra chars
# to see what step counts are achievable.
best_T = 0
best_prog = None
# Exhaustive search for n=4 (3 POP + 1 HALT) with alphabet up to 6
n = 4
A = 6
import itertools
count = 0
for i0_pop in range(1, A+1):
for i0_g1 in range(n):
for i0_push in range(1, A+1):
for i0_g2 in range(n):
for i1_pop in range(1, A+1):
for i1_g1 in range(n):
for i1_push in range(1, A+1):
for i1_g2 in range(n):
for i2_pop in range(1, A+1):
for i2_g1 in range(n):
for i2_push in range(1, A+1):
for i2_g2 in range(n):
for h_push in range(1, A+1):
for h_g2 in range(n):
instrs = [
('POP', i0_pop, i0_g1, i0_push, i0_g2),
('POP', i1_pop, i1_g1, i1_push, i1_g2),
('POP', i2_pop, i2_g1, i2_push, i2_g2),
('HALT', h_push, h_g2),
]
T = evaluate(n, instrs)
count += 1
if T > 0 and T > best_T:
best_T = T
best_prog = instrs
if T > 100:
print(f"New best T={T}: {instrs}")
if count % 10000000 == 0:
print(f" {count} configs tested, best T={best_T}")
print(f"\nTotal: {count} configs. Best T = {best_T}")
print(f"Best prog: {best_prog}")
|