docker_space/frontier_cs_8/fast_search.cpp

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

static const long long P = 998244353;

// Program structure: (n-1) POP instructions + 1 HALT at position n-1
// POP instruction i: POP (i+1) GOTO (i+1) PUSH push_val[i] GOTO push_goto[i]
//   pop matches value (i+1), goes to next instruction
//   push_val[i] in {1, ..., maxVal}, push_goto[i] in {0, ..., n-1}
// HALT at n-1: HALT PUSH halt_push GOTO halt_goto
//
// Stack values are 0 (empty), 1..maxVal
// State space: n * (maxVal + 1)

// Returns cost mod P, or -1 if cycle
long long evaluate(int n, const int* push_val, const int* push_goto, int halt_push, int halt_goto, int maxVal) {
    int nstates = n * (maxVal + 1);
    vector<int> dest(nstates, -2);
    vector<long long> cost(nstates, 0);
    vector<int8_t> state(nstates, 0); // 0=unvisited, 1=in-progress, 2=done

    // Stack-based DFS to avoid recursion overhead
    struct Frame {
        int i, x;
        int phase; // 0: initial, 1: after first sub-call, 2: after second sub-call
        int j; // intermediate instruction
        long long u; // intermediate cost
    };
    vector<Frame> stack;
    stack.reserve(nstates);

    auto idx = [&](int i, int x) { return i * (maxVal + 1) + x; };

    auto push_frame = [&](int i, int x) -> bool {
        int id = idx(i, x);
        if (state[id] == 2) return true; // already done
        if (state[id] == 1) return false; // cycle!
        state[id] = 1;
        stack.push_back({i, x, 0, 0, 0});
        return true;
    };

    // We need to evaluate (0, 0)
    if (!push_frame(0, 0)) return -1;

    while (!stack.empty()) {
        Frame& f = stack.back();
        int id = idx(f.i, f.x);

        if (f.i < n - 1) { // POP
            int pop_v = f.i + 1;
            if (f.x == pop_v) {
                dest[id] = f.i + 1; // pop_goto = next instruction
                cost[id] = 1;
                state[id] = 2;
                stack.pop_back();
                continue;
            }
            // Not matched: push push_val[i], goto push_goto[i]
            if (f.phase == 0) {
                // Need solve(push_goto[i], push_val[i])
                int sub_i = push_goto[f.i];
                int sub_x = push_val[f.i];
                int sub_id = idx(sub_i, sub_x);
                if (state[sub_id] == 2) {
                    f.j = dest[sub_id];
                    f.u = cost[sub_id];
                    f.phase = 1;
                    // fall through to phase 1
                } else if (state[sub_id] == 1) {
                    return -1; // cycle
                } else {
                    state[sub_id] = 1;
                    f.phase = 1;
                    stack.push_back({sub_i, sub_x, 0, 0, 0});
                    continue;
                }
            }
            if (f.phase == 1) {
                int sub_i = push_goto[f.i];
                int sub_x = push_val[f.i];
                int sub_id = idx(sub_i, sub_x);
                if (state[sub_id] != 2) return -1; // shouldn't happen
                f.j = dest[sub_id];
                f.u = cost[sub_id];
                // Now need solve(j, x)
                if (f.j == -1) {
                    // j=-1 means halted already, can't process x... this shouldn't happen
                    // unless the sub-program halted, which means x is still on stack
                    // Actually if j=-1, the program halted inside the sub-call.
                    // This means the whole program halted, cost = u + 1.
                    // But the checker would give dest=-1 meaning halt.
                    // Actually looking at the checker: dest=-1 only from HALT with x=0.
                    // After that, solve(j, x) with j=-1 would be out of bounds.
                    // This means if sub-call halts (returns dest=-1), then solving (dest=-1, x) is invalid.
                    // Wait, in the checker, dest is used as an instruction index, and -1 means halt.
                    // But then solve(j, x) with j=-1 would be called... but there's no instruction -1.
                    // Let me re-read the checker.
                    // Actually solve returns (k, v) where k is the next instruction or -1 (halt).
                    // Then the caller does solve(k, x). If k=-1, that's solve(-1, x) which is out of bounds.
                    // This means the program MUST be designed so that after the sub-call,
                    // the returned instruction is valid (not -1).
                    // So if a HALT with empty stack is reached during a sub-call,
                    // the returned dest is -1, and then solve(-1, x) would crash.
                    // The checker uses dp[-1][x] which is out of bounds...
                    // Actually in the checker, vectors are indexed from 0 to n-1.
                    // dp[-1] would be undefined behavior. But practically, this means
                    // programs where a HALT is reached with empty stack during a sub-call
                    // would cause UB in the checker, so they're invalid.
                    // CONCLUSION: in valid programs, HALT with empty stack should only be reached
                    // at the very end (solve(0,0)'s final halt).
                    return -1; // invalid program
                }
                int sub_id2 = idx(f.j, f.x);
                if (state[sub_id2] == 2) {
                    dest[id] = dest[sub_id2];
                    cost[id] = (f.u + cost[sub_id2] + 1) % P;
                    state[id] = 2;
                    stack.pop_back();
                    continue;
                } else if (state[sub_id2] == 1) {
                    return -1; // cycle
                } else {
                    state[sub_id2] = 1;
                    f.phase = 2;
                    stack.push_back({f.j, f.x, 0, 0, 0});
                    continue;
                }
            }
            if (f.phase == 2) {
                int sub_id2 = idx(f.j, f.x);
                if (state[sub_id2] != 2) return -1;
                dest[id] = dest[sub_id2];
                cost[id] = (f.u + cost[sub_id2] + 1) % P;
                state[id] = 2;
                stack.pop_back();
                continue;
            }
        } else { // HALT (i = n-1)
            if (f.x == 0) {
                dest[id] = -1;
                cost[id] = 1;
                state[id] = 2;
                stack.pop_back();
                continue;
            }
            // push halt_push, goto halt_goto
            if (f.phase == 0) {
                int sub_i = halt_goto;
                int sub_x = halt_push;
                int sub_id = idx(sub_i, sub_x);
                if (state[sub_id] == 2) {
                    f.j = dest[sub_id];
                    f.u = cost[sub_id];
                    f.phase = 1;
                } else if (state[sub_id] == 1) {
                    return -1;
                } else {
                    state[sub_id] = 1;
                    f.phase = 1;
                    stack.push_back({sub_i, sub_x, 0, 0, 0});
                    continue;
                }
            }
            if (f.phase == 1) {
                int sub_i = halt_goto;
                int sub_x = halt_push;
                int sub_id = idx(sub_i, sub_x);
                if (state[sub_id] != 2) return -1;
                f.j = dest[sub_id];
                f.u = cost[sub_id];
                if (f.j == -1) return -1; // invalid
                int sub_id2 = idx(f.j, f.x);
                if (state[sub_id2] == 2) {
                    dest[id] = dest[sub_id2];
                    cost[id] = (f.u + cost[sub_id2] + 1) % P;
                    state[id] = 2;
                    stack.pop_back();
                    continue;
                } else if (state[sub_id2] == 1) {
                    return -1;
                } else {
                    state[sub_id2] = 1;
                    f.phase = 2;
                    stack.push_back({f.j, f.x, 0, 0, 0});
                    continue;
                }
            }
            if (f.phase == 2) {
                int sub_id2 = idx(f.j, f.x);
                if (state[sub_id2] != 2) return -1;
                dest[id] = dest[sub_id2];
                cost[id] = (f.u + cost[sub_id2] + 1) % P;
                state[id] = 2;
                stack.pop_back();
                continue;
            }
        }
    }

    int id0 = idx(0, 0);
    if (state[id0] != 2) return -1;
    return cost[id0];
}

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

    // Search over programs with n instructions
    // Using push values 1..V where V is small
    // Each POP i has: pop_val=i+1, pop_goto=i+1, push_val in 1..V, push_goto in 0..n-1
    // HALT has: push_val in 1..V, push_goto in 0..n-2

    for (int n = 5; n <= 20; n++) {
        int d = n - 1;
        int V = min(d, 5); // max push value

        cerr << "n=" << n << " V=" << V << endl;

        mt19937 rng(42 + n * 999979);
        bool found[2] = {false, false};

        auto startTime = chrono::steady_clock::now();
        int timeLimit = 10000; // 10s per n

        int push_val[25], push_goto[25];
        int halt_push, halt_goto;
        int best_push_val[2][25], best_push_goto[2][25], best_halt_push[2], best_halt_goto[2];

        long long attempts = 0;

        while (!(found[0] && found[1])) {
            auto now = chrono::steady_clock::now();
            auto ms = chrono::duration_cast<chrono::milliseconds>(now - startTime).count();
            if (ms > timeLimit) break;

            // Random initialization
            for (int i = 0; i < d; i++) {
                push_val[i] = 1 + rng() % V;
                push_goto[i] = rng() % n;
            }
            halt_push = 1 + rng() % V;
            halt_goto = rng() % d; // point to a POP instruction

            long long cost = evaluate(n, push_val, push_goto, halt_push, halt_goto, V);
            if (cost < 0) continue;

            // Hill climbing
            for (int iter = 0; iter < 20000; iter++) {
                for (int ti = 0; ti < 2; ti++) {
                    if (!found[ti] && cost == targets[ti]) {
                        found[ti] = true;
                        memcpy(best_push_val[ti], push_val, sizeof(int) * d);
                        memcpy(best_push_goto[ti], push_goto, sizeof(int) * d);
                        best_halt_push[ti] = halt_push;
                        best_halt_goto[ti] = halt_goto;
                        cerr << "FOUND n=" << n << " target" << (ti+1) << endl;
                    }
                }
                if (found[0] && found[1]) break;

                // Mutate
                int save_val, save_goto, save_idx;
                int mut_type = rng() % 3; // 0: push_val, 1: push_goto, 2: halt params
                if (mut_type == 0) {
                    save_idx = rng() % d;
                    save_val = push_val[save_idx];
                    push_val[save_idx] = 1 + rng() % V;
                } else if (mut_type == 1) {
                    save_idx = rng() % d;
                    save_goto = push_goto[save_idx];
                    push_goto[save_idx] = rng() % n;
                } else {
                    save_val = halt_push;
                    save_goto = halt_goto;
                    halt_push = 1 + rng() % V;
                    halt_goto = rng() % d;
                }

                long long new_cost = evaluate(n, push_val, push_goto, halt_push, halt_goto, V);

                bool accept = false;
                if (new_cost >= 0) {
                    // Check if closer to any unfound target
                    long long bestOld = P, bestNew = P;
                    for (int ti = 0; ti < 2; ti++) {
                        if (!found[ti]) {
                            bestOld = min(bestOld, min((cost - targets[ti] + P) % P, (targets[ti] - cost + P) % P));
                            bestNew = min(bestNew, min((new_cost - targets[ti] + P) % P, (targets[ti] - new_cost + P) % P));
                        }
                    }
                    if (bestNew <= bestOld) accept = true;
                }

                if (accept) {
                    cost = new_cost;
                } else {
                    // Revert
                    if (mut_type == 0) push_val[save_idx] = save_val;
                    else if (mut_type == 1) push_goto[save_idx] = save_goto;
                    else { halt_push = save_val; halt_goto = save_goto; }
                }

                attempts++;
            }
        }

        auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
        cerr << "  attempts=" << attempts << " time=" << ms << "ms found=" << found[0] << "," << found[1] << endl;

        if (found[0] && found[1]) {
            for (int ti = 0; ti < 2; ti++) {
                cout << "Target " << (ti+1) << " (n=" << n << "):" << endl;
                cout << n << endl;
                for (int i = 0; i < d; i++) {
                    cout << "POP " << (i+1) << " GOTO " << (i+2)
                         << " PUSH " << best_push_val[ti][i] << " GOTO " << (best_push_goto[ti][i]+1) << endl;
                }
                cout << "HALT PUSH " << best_halt_push[ti] << " GOTO " << (best_halt_goto[ti]+1) << endl;
            }
            break;
        }
    }

    return 0;
}