docker_space/frontier_cs_8/construct3.py

#!/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}")