docker_space/frontier_cs_8/analyze_growth.cpp

// For n=2..6, find the maximum step count achievable with various alphabet sizes
// Use random search for speed
#include <bits/stdc++.h>
using namespace std;

constexpr long long P = 998244353;

int n_instr;
int maxChar;
int type_arr[30];
int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];

optional<pair<int, long long>> dp[30][110];
bool vis[30][110];
bool infinite_flag;

pair<int, long long> solve(int i, int x) {
    if (dp[i][x]) return dp[i][x].value();
    if (vis[i][x]) { infinite_flag = true; return {-1, 0}; }
    vis[i][x] = true;

    if (type_arr[i] == 0) {
        if (x == pop_char_arr[i]) {
            dp[i][x] = {goto1_arr[i], 1LL};
        } else {
            auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
            if (infinite_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (infinite_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    } else {
        if (x == 0) {
            dp[i][x] = {-1, 1LL};
        } else {
            auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
            if (infinite_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (infinite_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    }
    return dp[i][x].value();
}

long long evaluate() {
    for (int i = 0; i < n_instr; i++)
        for (int j = 0; j <= maxChar; j++) {
            dp[i][j].reset();
            vis[i][j] = false;
        }
    infinite_flag = false;
    auto [fi, steps] = solve(0, 0);
    if (infinite_flag) return -1;
    return steps;
}

int main() {
    mt19937 rng(42);

    for (int n = 2; n <= 8; n++) {
        for (int alpha = 1; alpha <= min(20, n*3); alpha++) {
            n_instr = n;
            maxChar = alpha;
            long long max_steps = 0;

            for (int trial = 0; trial < 200000; trial++) {
                for (int i = 0; i < n_instr; i++) {
                    if (i == n_instr - 1) type_arr[i] = 1;
                    else type_arr[i] = (rng() % 3 == 0) ? 1 : 0;

                    if (type_arr[i] == 0) {
                        pop_char_arr[i] = 1 + rng() % maxChar;
                        goto1_arr[i] = rng() % n_instr;
                        push_char_arr[i] = 1 + rng() % maxChar;
                        goto2_arr[i] = rng() % n_instr;
                    } else {
                        push_char_arr[i] = 1 + rng() % maxChar;
                        goto2_arr[i] = rng() % n_instr;
                    }
                }
                long long T = evaluate();
                if (T > max_steps) max_steps = T;
            }
            printf("n=%d alpha=%d maxT=%lld chain_max=%lld\n", n, alpha, max_steps, (1LL<<(n))-1);
        }
    }
    return 0;
}