docker_space/frontier_cs_8/construct.py

#!/usr/bin/env python3
"""
Construct a non-chain program with n=27 (26 POPs + 1 HALT) that achieves target mod P.

Key idea: Use a standard chain of d1 POPs (giving exact T1), then use additional
instructions with larger alphabet to add the remaining delta via modular arithmetic.

Wait, that doesn't reduce n.

Alternative: Use a chain of d=26 POPs but modify the HALT instruction to also
push a non-standard char, creating additional recursion levels.

In the standard chain:
  HALT d: push 1, goto d.
  solve(d, 0) = 1 (halt immediately)
  solve(d, x) for x != 0: push 1, goto d. solve(d, 1) then solve(result, x).

If HALT pushes char 1 and goes to itself:
  solve(d, 1): push 1, goto d. solve(d, 1) -> CYCLE! Infinite.

If HALT pushes char c and goes to instruction g:
  solve(d, x) for x != 0: push c, goto g. solve(g, c) then solve(result, x).
  If g < d: solve(g, c) traverses part of the chain.
  This is fine as long as no cycles.

In standard chain: HALT pushes char 1, goto d (self).
  solve(d, 1): push 1, goto d. solve(d, 1) -> needs solve(d, 1), CYCLE!
  Wait, that means in the standard chain, HALT is never called with x != 0?

Let me trace the standard chain more carefully.
Chain: d=3 (POPs 0,1,2, HALT 3), all gy[j]=0
POP 0: pop 1, goto 1, push 1, goto 0
POP 1: pop 2, goto 2, push 2, goto 0
POP 2: pop 3, goto 3, push 3, goto 0
HALT 3: push 1, goto 3

solve(0, 0): x=0 != 1. Push 1, goto 0. solve(0, 1) then solve(result, 0).
  solve(0, 1): x=1 == 1. Pop, goto 1. Return (1, 1).
  solve(1, 0): x=0 != 2. Push 2, goto 0. solve(0, 2) then solve(result, 0).
    solve(0, 2): x=2 != 1. Push 1, goto 0. solve(0, 1) then solve(result, 2).
      solve(0, 1) = (1, 1). solve(1, 2): x=2 == 2. Pop, goto 2. Return (2, 1).
      result = (2, 1+1+1) = (2, 3).
    solve(2, 0): x=0 != 3. Push 3, goto 0. solve(0, 3) then solve(result, 0).
      solve(0, 3): x=3 != 1. Push 1, goto 0. solve(0, 1) then solve(result, 3).
        solve(0, 1) = (1, 1). solve(1, 3): x=3 != 2. Push 2, goto 0. solve(0, 2) then solve(result, 3).
          solve(0, 2) = (2, 3). solve(2, 3): x=3 == 3. Pop, goto 3. Return (3, 1).
          result = (3, 3+1+1) = (3, 5).
        result = (3, 1+5+1) = (3, 7).
      solve(3, 0): x=0. HALT. Return (-1, 1).
      result = (-1, 7+1+1) = (-1, 9).
    result = (-1, 3+9+1) = (-1, 13).
  result = (-1, 1+13+1) = (-1, 15).

T = 15 = 2^4 - 1. Correct!

Note: HALT is only ever called with x=0 (which halts). It's never called with x != 0
because in the standard chain, the only path to HALT is from POP d-1 popping its char,
going to instruction d. And at that point, the stack has been fully unwound.

But what if we change HALT's push_goto to point to something other than itself?
E.g., HALT pushes char c, goto g where g < d.
Then solve(d, x) for x != 0: push c, goto g. solve(g, c) then solve(result, x).
This would ONLY matter if HALT is ever called with x != 0.

In the standard chain, HALT IS called with x=0 only. But we can CHANGE that!
If we modify some POP's goto1 (pop destination) to point to HALT instead of the next POP,
then HALT could be reached with a non-empty stack.

For example: POP j's pop destination = HALT (instead of j+1).
Then when char j+1 is popped at POP j, we go to HALT with whatever is now on top.
If the stack isn't empty at that point, HALT pushes and recurses.

This creates additional recursion levels THROUGH the HALT instruction.
"""

P = 998244353

# Let me implement a general program evaluator
def evaluate(n, instructions):
    """
    instructions[i] = ('POP', pop_char, goto1, push_char, goto2) or
                       ('HALT', push_char, goto2)
    Returns step count mod P, or -1 if infinite.
    """
    dp = {}
    vis = set()

    def solve(i, x):
        if (i, x) in dp:
            return dp[(i, x)]
        if (i, x) in vis:
            return None  # infinite
        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]

# Standard chain with d=26
d = 26
target1 = 150994941
target2 = 150994939

# Standard chain program
def make_chain(d, gy):
    instrs = []
    for j in range(d):
        # POP (j+1) GOTO (j+1) PUSH (j+1) GOTO gy[j]
        instrs.append(('POP', j+1, j+1, j+1, gy[j]))
    # HALT PUSH 1 GOTO d
    instrs.append(('HALT', 1, d))
    return instrs

gy = [0]*d
instrs = make_chain(d, gy)
T = evaluate(d+1, instrs)
print(f"Standard chain d={d}: T = {T} (max = {2**(d+1)-1})")

# Now let's try modifying the chain to create more states
# Idea 1: Change POP j's goto1 (pop destination) to some non-standard value
# This means after popping at POP j, we go somewhere unexpected,
# potentially creating more complex recursion.

# Idea 2: Change the push_char to a value > d (not poppable by any POP)
# This forces the char to propagate to HALT.
# If HALT then pushes a poppable char and goes to the chain, we get MORE recursion.

# Let's try Idea 2:
# Modified chain where POP k pushes char d+1 (not poppable) instead of char k+1.
# HALT pushes char 1 and goes to instruction 0.
# When char d+1 reaches HALT, HALT pushes char 1, goes to 0.
# Then char 1 gets popped by POP 0 at instruction 0.
# This adds an extra layer of recursion.

# Test with small d first
for d_test in [3, 4, 5]:
    # Standard chain
    gy = [0]*d_test
    std_instrs = make_chain(d_test, gy)
    std_T = evaluate(d_test+1, std_instrs)

    # Modified: POP 0 pushes char d_test+1 instead of 1
    # HALT pushes char 1, goes to 0
    mod_instrs = []
    for j in range(d_test):
        pc = d_test + 1 if j == 0 else j + 1  # POP 0 pushes non-standard
        mod_instrs.append(('POP', j+1, j+1, pc, 0))
    mod_instrs.append(('HALT', 1, 0))  # HALT pushes 1, goto 0
    mod_T = evaluate(d_test+1, mod_instrs)

    print(f"\nd_test={d_test}:")
    print(f"  Standard T = {std_T}")
    print(f"  Modified T = {mod_T}")

    # What if ALL POPs push char d+1?
    mod2_instrs = []
    for j in range(d_test):
        mod2_instrs.append(('POP', j+1, j+1, d_test+1, 0))
    mod2_instrs.append(('HALT', 1, 0))
    mod2_T = evaluate(d_test+1, mod2_instrs)
    print(f"  All push d+1, T = {mod2_T}")

    # What about: each POP pushes a unique extra char
    mod3_instrs = []
    for j in range(d_test):
        mod3_instrs.append(('POP', j+1, j+1, d_test+1+j, 0))
    mod3_instrs.append(('HALT', 1, 0))
    mod3_T = evaluate(d_test+1, mod3_instrs)
    print(f"  Each push unique extra char, T = {mod3_T}")

    # POP j pushes char j+2 (shifted by 1)
    mod4_instrs = []
    for j in range(d_test):
        pc = j + 2 if j + 2 <= d_test else 1  # wrap around
        mod4_instrs.append(('POP', j+1, j+1, pc, 0))
    mod4_instrs.append(('HALT', 1, d_test))
    mod4_T = evaluate(d_test+1, mod4_instrs)
    print(f"  Push shifted char, T = {mod4_T}")