docker_space/frontier_cs_8/general_search.cpp

#include <bits/stdc++.h>
using namespace std;

static const long long P = 998244353;

// General program evaluator matching the checker
// Returns (next_instr, cost_mod_P) or (-2, 0) on cycle
struct Program {
    int n;
    // For each instruction: type (0=POP, 1=HALT), and parameters
    // POP: pop_val, pop_goto, push_val, push_goto
    // HALT: push_val, push_goto
    vector<int> type;
    vector<array<int, 4>> params; // POP: [pop_val, pop_goto, push_val, push_goto], HALT: [push_val, push_goto, -, -]

    // DP arrays
    vector<vector<optional<pair<int, long long>>>> dp;
    vector<vector<bool>> vis;
    bool has_cycle;

    void init() {
        dp.assign(n, vector<optional<pair<int, long long>>>(1025, nullopt));
        vis.assign(n, vector<bool>(1025, false));
        has_cycle = false;
    }

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

        if (type[i] == 0) { // POP
            int pop_val = params[i][0], pop_goto = params[i][1];
            int push_val = params[i][2], push_goto = params[i][3];
            if (x == pop_val) {
                dp[i][x] = {pop_goto, 1};
            } else {
                auto [j, u] = solve(push_goto, push_val);
                if (has_cycle) return {-2, 0};
                auto [k, v] = solve(j, x);
                if (has_cycle) return {-2, 0};
                dp[i][x] = {k, (u + v + 1) % P};
            }
        } else { // HALT
            int push_val = params[i][0], push_goto = params[i][1];
            if (x == 0) {
                dp[i][x] = {-1, 1};
            } else {
                auto [j, u] = solve(push_goto, push_val);
                if (has_cycle) return {-2, 0};
                auto [k, v] = solve(j, x);
                if (has_cycle) return {-2, 0};
                dp[i][x] = {k, (u + v + 1) % P};
            }
        }
        return dp[i][x].value();
    }
};

int main() {
    long long targets[2] = {150994941LL, 150994939LL};

    // Try small programs with n=2,3,4,5 instructions
    // Values limited to 1..V
    int V = 5; // small value range for speed

    for (int n = 2; n <= 6; n++) {
        cerr << "n=" << n << endl;
        // Must have at least one HALT instruction
        // The program starts at instruction 0

        // For efficiency, let's try specific structures:
        // Structure: (n-1) POP instructions followed by 1 HALT
        // But allow varied push/pop values and goto targets

        // Let's try: all POP except last is HALT
        // Each POP has 4 params, HALT has 2 params
        // POP params: pop_val in 1..V, pop_goto in 0..n-1, push_val in 1..V, push_goto in 0..n-1
        // HALT params: push_val in 1..V, push_goto in 0..n-1

        // Total configs = (V * n * V * n)^(n-1) * (V * n)
        // For n=3, V=5: (5*3*5*3)^2 * (5*3) = 225^2 * 15 = 759375
        // For n=4, V=5: (5*4*5*4)^3 * (5*4) = 400^3 * 20 = 1.28B -- too big
        // For n=3, V=10: (10*3*10*3)^2 * (10*3) = 900^2 * 30 = 24.3M -- ok
        // For n=4, V=3: (3*4*3*4)^3 * (3*4) = 144^3 * 12 = 35.8M -- ok

        int maxV;
        if (n <= 3) maxV = 20;
        else if (n == 4) maxV = 4;
        else if (n == 5) maxV = 3;
        else maxV = 2;

        long long count = 0;
        bool found[2] = {false, false};

        auto startTime = chrono::steady_clock::now();

        // Use random sampling for large spaces
        mt19937 rng(42 + n * 17);

        // For n=2,3 with small V, try exhaustive; else random
        bool exhaustive = false;
        long long totalConfigs = 1;
        for (int i = 0; i < n - 1; i++) totalConfigs *= (long long)maxV * n * maxV * n;
        totalConfigs *= (long long)maxV * n;
        if (totalConfigs <= 50000000) exhaustive = true;

        cerr << "  maxV=" << maxV << " totalConfigs=" << totalConfigs << " exhaustive=" << exhaustive << endl;

        if (exhaustive) {
            // Enumerate all configs
            // Use mixed-radix representation
            // dims: for POP: [pop_val, pop_goto, push_val, push_goto] each
            // for HALT: [push_val, push_goto]
            int ndim = 4 * (n - 1) + 2;
            vector<int> radix(ndim);
            for (int i = 0; i < n - 1; i++) {
                radix[4*i] = maxV;       // pop_val
                radix[4*i+1] = n;        // pop_goto
                radix[4*i+2] = maxV;     // push_val
                radix[4*i+3] = n;        // push_goto
            }
            radix[ndim-2] = maxV;        // HALT push_val
            radix[ndim-1] = n;           // HALT push_goto

            vector<int> idx(ndim, 0);

            while (true) {
                Program prog;
                prog.n = n;
                prog.type.resize(n);
                prog.params.resize(n);
                for (int i = 0; i < n - 1; i++) {
                    prog.type[i] = 0; // POP
                    prog.params[i][0] = idx[4*i] + 1;          // pop_val 1..maxV
                    prog.params[i][1] = idx[4*i+1];            // pop_goto 0..n-1
                    prog.params[i][2] = idx[4*i+2] + 1;        // push_val 1..maxV
                    prog.params[i][3] = idx[4*i+3];            // push_goto 0..n-1
                }
                prog.type[n-1] = 1; // HALT
                prog.params[n-1][0] = idx[ndim-2] + 1;         // push_val
                prog.params[n-1][1] = idx[ndim-1];             // push_goto

                prog.init();
                auto [dest, cost] = prog.solve(0, 0);
                if (!prog.has_cycle) {
                    for (int ti = 0; ti < 2; ti++) {
                        if (!found[ti] && cost == targets[ti]) {
                            found[ti] = true;
                            cout << "FOUND n=" << n << " target" << (ti+1) << " cost=" << cost << endl;
                            cout << n << endl;
                            for (int i = 0; i < n - 1; i++) {
                                cout << "POP " << prog.params[i][0] << " GOTO " << (prog.params[i][1]+1)
                                     << " PUSH " << prog.params[i][2] << " GOTO " << (prog.params[i][3]+1) << endl;
                            }
                            cout << "HALT PUSH " << prog.params[n-1][0] << " GOTO " << (prog.params[n-1][1]+1) << endl;
                        }
                    }
                }

                count++;
                if (count % 1000000 == 0) {
                    auto now = chrono::steady_clock::now();
                    auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
                    cerr << "  count=" << count << " (" << ms << "ms)" << endl;
                }

                // Increment
                int pos = ndim - 1;
                while (pos >= 0) {
                    idx[pos]++;
                    if (idx[pos] < radix[pos]) break;
                    idx[pos] = 0;
                    pos--;
                }
                if (pos < 0) break;
                if (found[0] && found[1]) break;
            }
        } else {
            // Random sampling
            long long maxAttempts = 100000000LL;
            for (long long att = 0; att < maxAttempts; att++) {
                Program prog;
                prog.n = n;
                prog.type.resize(n);
                prog.params.resize(n);
                for (int i = 0; i < n - 1; i++) {
                    prog.type[i] = 0;
                    prog.params[i][0] = 1 + rng() % maxV;
                    prog.params[i][1] = rng() % n;
                    prog.params[i][2] = 1 + rng() % maxV;
                    prog.params[i][3] = rng() % n;
                }
                prog.type[n-1] = 1;
                prog.params[n-1][0] = 1 + rng() % maxV;
                prog.params[n-1][1] = rng() % n;

                prog.init();
                auto [dest, cost] = prog.solve(0, 0);
                if (!prog.has_cycle) {
                    for (int ti = 0; ti < 2; ti++) {
                        if (!found[ti] && cost == targets[ti]) {
                            found[ti] = true;
                            cout << "FOUND n=" << n << " target" << (ti+1) << " cost=" << cost << endl;
                            cout << n << endl;
                            for (int i = 0; i < n - 1; i++) {
                                cout << "POP " << prog.params[i][0] << " GOTO " << (prog.params[i][1]+1)
                                     << " PUSH " << prog.params[i][2] << " GOTO " << (prog.params[i][3]+1) << endl;
                            }
                            cout << "HALT PUSH " << prog.params[n-1][0] << " GOTO " << (prog.params[n-1][1]+1) << endl;
                        }
                    }
                }

                count++;
                if (count % 10000000 == 0) {
                    auto now = chrono::steady_clock::now();
                    auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
                    cerr << "  count=" << count << " (" << ms << "ms)" << endl;
                    if (ms > 30000) break; // 30s timeout per n
                }
                if (found[0] && found[1]) break;
            }
        }

        cerr << "  total=" << count << " found=" << found[0] << "," << found[1] << endl;
        if (found[0] && found[1]) {
            cerr << "Both found at n=" << n << "!" << endl;
            break;
        }
    }

    return 0;
}