| |
| """ |
| 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] |
|
|
| |
| |
| d = 3 |
| instrs = [ |
| ('POP', 1, 1, 4, 0), |
| ('POP', 2, 2, 2, 0), |
| ('POP', 3, 3, 3, 0), |
| ('HALT', 1, 0), |
| ] |
| print("=== Modified chain d=3, POP 0 pushes 4 ===") |
| T = evaluate_verbose(4, instrs) |
| print(f"T = {T}") |
|
|
