File size: 7,592 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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | #!/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}")
|