docker_space/frontier_cs_8/analyze_structure.cpp

// Analyze what step counts are achievable with small n and varying alphabet
// Try to understand the structure of possible step counts
#include <bits/stdc++.h>
using namespace std;

constexpr long long P = 998244353;

struct MInt {
    long long x;
    MInt(): x(0) {}
    MInt(long long v): x(((v % P) + P) % P) {}
    MInt operator+(const MInt& b) const { return MInt(x + b.x); }
    MInt operator-(const MInt& b) const { return MInt(x - b.x); }
    MInt operator*(const MInt& b) const { return MInt(x * b.x); }
    bool operator==(const MInt& b) const { return x == b.x; }
};

int n_instr;
int type_arr[30]; // 0=POP, 1=HALT
int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];

int maxChar;
optional<pair<int, MInt>> dp[30][1030];
bool vis[30][1030];
bool infinite_flag;

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

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

MInt 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 MInt(P - 1); // sentinel for infinite
    return steps;
}

int main() {
    // Let's try a specific structure:
    // n=2: one HALT + one POP
    // HALT pushes some char b and goes to instruction g
    // POP pops some char a, goto g1, push char c, goto g2

    // With n=2, alphabet {1..A}:
    // Instruction 0: HALT PUSH b GOTO g (g in {0,1})
    // Instruction 1: POP a GOTO g1 PUSH c GOTO g2

    // solve(0, 0) = 1 (halt immediately)
    // solve(0, x) for x != 0: push b, goto g. So solve(g, b) then solve(result, x)
    //   steps = 1 + solve(g, b).steps + solve(solve(g,b).ret, x).steps

    // Let's manually compute for n=2:
    // Instr 0: HALT PUSH 1 GOTO 1
    // Instr 1: POP 1 GOTO 0 PUSH 1 GOTO 0
    //
    // solve(0, 0) = (-1, 1)  -- halt
    // solve(1, 1) = (0, 1)   -- pop, goto 0
    // solve(0, x) for x>0: push 1 goto 1. solve(1, 1) = (0, 1). solve(0, x).
    //   But this is circular! solve(0, x) depends on solve(0, x).
    //   So this program doesn't halt for x > 0 (other than when x is on the HALT path)

    // For the program to halt, we need no cycles in the dependency graph.
    // With n=2, alphabet 1..2:
    // Instr 0: HALT PUSH 1 GOTO 1
    // Instr 1: POP 2 GOTO 0 PUSH 1 GOTO 0
    //
    // solve(0, 0) = (-1, 1)
    // solve(1, 2) = (0, 1) -- pop, goto 0
    // solve(0, x) for x != 0: push 1, goto 1, solve(1, 1)
    //   solve(1, 1): x=1 != 2 (pop char). Push 1, goto 0. solve(0, 1) then solve(result, 1).
    //   solve(0, 1): push 1, goto 1. solve(1, 1) -- CYCLE! infinite.

    // Hmm. The challenge with small n is avoiding cycles.
    // Chain programs avoid cycles by having strictly increasing instruction indices.

    // Let me think about what makes chain programs special:
    // Chain: instrs 0..d-1 are POP, instr d is HALT
    // POP j: pops char (j+1), goto (j+1), push char (j+1), goto gy[j]
    // HALT d: push 1, goto d

    // The key is: POP j pops char (j+1). So when we push char (j+1) and call solve(gy[j], j+1),
    // the only instruction that can pop char (j+1) is instruction j itself.
    // This creates a well-structured recursion.

    // For non-chain: we could use different characters to create multiple "levels" of recursion
    // with the same instruction. E.g., one POP instruction that handles multiple stack symbols.

    // Actually, let me think about n=3 with the right structure:
    // If we can get 2 POP instructions to both create exponential growth,
    // and chain them, we might get 2^a * 2^b type behavior with a+b controlled.

    // Actually, let me try a different approach: enumerate step counts for very small programs

    n_instr = 3;
    maxChar = 4;

    set<long long> seen_steps;
    long long max_steps = 0;

    // Enumerate all programs with n=3, alphabet 1..4
    // Last instruction must be HALT
    // Try all configurations

    int count = 0;
    int halting = 0;

    for (int t0 = 0; t0 <= 1; t0++)
    for (int t1 = 0; t1 <= 1; t1++) {
        type_arr[2] = 1; // HALT
        type_arr[0] = t0;
        type_arr[1] = t1;

        auto enumerate_instr = [&](int i, auto& self, auto& callback) -> void {
            if (i == n_instr) {
                callback();
                return;
            }
            if (type_arr[i] == 0) { // POP
                for (int a = 1; a <= maxChar; a++)
                for (int g1 = 0; g1 < n_instr; g1++)
                for (int c = 1; c <= maxChar; c++)
                for (int g2 = 0; g2 < n_instr; g2++) {
                    pop_char_arr[i] = a;
                    goto1_arr[i] = g1;
                    push_char_arr[i] = c;
                    goto2_arr[i] = g2;
                    self(i + 1, self, callback);
                }
            } else { // HALT
                for (int c = 1; c <= maxChar; c++)
                for (int g2 = 0; g2 < n_instr; g2++) {
                    push_char_arr[i] = c;
                    goto2_arr[i] = g2;
                    self(i + 1, self, callback);
                }
            }
        };

        auto callback = [&]() {
            count++;
            MInt T = evaluate();
            if (T.x != (P - 1) % P) {
                halting++;
                seen_steps.insert(T.x);
                if (T.x > max_steps) {
                    max_steps = T.x;
                    cerr << "New max: " << T.x << " with config:";
                    for (int i = 0; i < n_instr; i++) {
                        if (type_arr[i] == 0) {
                            cerr << " POP" << pop_char_arr[i] << "→" << goto1_arr[i] << ",push" << push_char_arr[i] << "→" << goto2_arr[i];
                        } else {
                            cerr << " HALT,push" << push_char_arr[i] << "→" << goto2_arr[i];
                        }
                    }
                    cerr << endl;
                }
            }
        };

        enumerate_instr(0, enumerate_instr, callback);
    }

    cout << "Total programs: " << count << ", halting: " << halting << endl;
    cout << "Distinct step counts: " << seen_steps.size() << endl;
    cout << "Max step count: " << max_steps << endl;
    cout << "First 50 step counts:";
    int printed = 0;
    for (long long v : seen_steps) {
        if (printed++ >= 50) break;
        cout << " " << v;
    }
    cout << endl;

    return 0;
}