docker_space/frontier_cs_8/analyze_n4.cpp

// Enumerate n=4, alphabet 1..3, find max step count and all achievable counts
#include <bits/stdc++.h>
using namespace std;

constexpr long long P = 998244353;

int n_instr = 4;
int maxChar = 3;
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][10];
bool vis[30][10];
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() {
    long long max_steps = 0;
    int halting = 0;
    set<long long> seen;

    // Try many random programs
    mt19937 rng(42);
    for (int trial = 0; trial < 10000000; trial++) {
        // Random program
        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 >= 0) {
            halting++;
            seen.insert(T);
            if (T > max_steps) {
                max_steps = T;
                fprintf(stderr, "New max: %lld at trial %d\n", T, trial);
            }
        }
    }

    printf("Halting: %d, distinct: %zu, max: %lld\n", halting, seen.size(), max_steps);
    // Print some largest values
    vector<long long> vals(seen.begin(), seen.end());
    sort(vals.rbegin(), vals.rend());
    printf("Top 20:");
    for (int i = 0; i < min(20, (int)vals.size()); i++) printf(" %lld", vals[i]);
    printf("\n");

    return 0;
}