File size: 2,531 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 | #!/usr/bin/env python3
"""
Trace modified chain to understand why it's infinite, then fix it.
"""
P = 998244353
def evaluate_verbose(n, instructions, max_depth=50):
dp = {}
vis = set()
depth = [0]
def solve(i, x, indent=0):
prefix = " " * indent
if (i, x) in dp:
return dp[(i, x)]
if (i, x) in vis:
print(f"{prefix}CYCLE at ({i}, {x})")
return None
vis.add((i, x))
if indent > max_depth:
print(f"{prefix}MAX DEPTH at ({i}, {x})")
return None
inst = instructions[i]
if inst[0] == 'POP':
_, pop_c, g1, push_c, g2 = inst
if x == pop_c:
print(f"{prefix}solve({i},{x}): POP match, goto {g1}. cost=1")
dp[(i, x)] = (g1, 1)
else:
print(f"{prefix}solve({i},{x}): POP miss (need {pop_c}), push {push_c} goto {g2}")
r = solve(g2, push_c, indent+1)
if r is None: return None
j, u = r
print(f"{prefix} resolve returned to instr {j}, cost {u}")
r2 = solve(j, x, indent+1)
if r2 is None: return None
k, v = r2
print(f"{prefix} continue from {j} with {x}: -> {k}, cost {v}")
dp[(i, x)] = (k, (u + v + 1) % P)
else:
_, push_c, g2 = inst
if x == 0:
print(f"{prefix}solve({i},{x}): HALT. cost=1")
dp[(i, x)] = (-1, 1)
else:
print(f"{prefix}solve({i},{x}): HALT non-empty, push {push_c} goto {g2}")
r = solve(g2, push_c, indent+1)
if r is None: return None
j, u = r
print(f"{prefix} resolve returned to instr {j}, cost {u}")
r2 = solve(j, x, indent+1)
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]
# Test: d=3, modified POP 0 pushes char 4 instead of 1
# HALT pushes 1 goto 0
d = 3
instrs = [
('POP', 1, 1, 4, 0), # POP 0: pop 1, goto 1, push 4, goto 0
('POP', 2, 2, 2, 0), # POP 1: pop 2, goto 2, push 2, goto 0
('POP', 3, 3, 3, 0), # POP 2: pop 3, goto 3, push 3, goto 0
('HALT', 1, 0), # HALT 3: push 1, goto 0
]
print("=== Modified chain d=3, POP 0 pushes 4 ===")
T = evaluate_verbose(4, instrs)
print(f"T = {T}")
|