docker_space/frontier_cs_8/fast_gen_search.cpp

// Fast generalized chain search with iterative evaluation
// d POPs + 1 HALT, with variable g1[] and gy[]
// Use topological sort on dependency graph instead of recursive solve.

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

constexpr long long P = 998244353;

int d;
int g1_arr[30]; // pop-match goto for POP j
int gy_arr[30]; // push goto for POP j

// State (i, x) for i in 0..d, x in 0..d
// For POP i (i < d):
//   x == i+1: result = (g1[i], 1), depends on nothing
//   x != i+1: depends on (gy[i], i+1) and then (return_of_that, x)
// For HALT (i = d):
//   x == 0: result = (-1, 1)
//   x != 0: depends on (d, 1) and then (return_of_that, x)

// Build dependency graph and solve topologically
// Each state (i, x) can depend on at most 2 other states.
// If there's a cycle, the program is infinite.

struct State {
    int i, x;
    int ret_instr;
    long long cost;
    bool computed;
    bool in_cycle_check;
};

// Encode state as i * (d+1) + x
inline int encode(int i, int x) { return i * (d + 1) + x; }

long long eval_fast() {
    int num_states = (d + 1) * (d + 1);
    vector<int> ret_instr(num_states, -2);  // -2 = not computed
    vector<long long> cost(num_states, 0);
    vector<int8_t> status(num_states, 0);  // 0=unvisited, 1=in_progress, 2=done

    // Iterative DFS with explicit stack
    struct Frame {
        int state;
        int phase; // 0=initial, 1=after dep1, 2=after dep2
        int dep1_state, dep2_state;
    };

    vector<Frame> stk;

    auto get_result = [&](int s) -> pair<int, long long> {
        return {ret_instr[s], cost[s]};
    };

    auto process = [&](int start) -> bool {
        stk.push_back({start, 0, -1, -1});

        while (!stk.empty()) {
            auto& f = stk.back();
            int s = f.state;
            int i = s / (d + 1);
            int x = s % (d + 1);

            if (f.phase == 0) {
                if (status[s] == 2) { stk.pop_back(); continue; }
                if (status[s] == 1) return false; // cycle
                status[s] = 1;

                if (i < d) {
                    if (x == i + 1) {
                        ret_instr[s] = g1_arr[i];
                        cost[s] = 1;
                        status[s] = 2;
                        stk.pop_back();
                        continue;
                    } else {
                        f.dep1_state = encode(gy_arr[i], i + 1);
                        f.phase = 1;
                        stk.push_back({f.dep1_state, 0, -1, -1});
                        continue;
                    }
                } else {
                    // HALT
                    if (x == 0) {
                        ret_instr[s] = -1;
                        cost[s] = 1;
                        status[s] = 2;
                        stk.pop_back();
                        continue;
                    } else {
                        f.dep1_state = encode(d, 1);
                        f.phase = 1;
                        stk.push_back({f.dep1_state, 0, -1, -1});
                        continue;
                    }
                }
            } else if (f.phase == 1) {
                // dep1 is computed
                if (status[f.dep1_state] != 2) return false;
                int j = ret_instr[f.dep1_state];
                if (j < 0 || j > d) {
                    // dep1 leads to halt, then continue with x
                    // Actually if j == -1, it halted.
                    // For POP: solve(gy[i], i+1) returned (-1, u). Then solve(-1, x) - invalid!
                    // This shouldn't happen in a valid program.
                    // If the subprogram halts, then the "return instruction" is -1.
                    // The next step is solve(-1, x) which is undefined.
                    // This means the program structure is broken.
                    return false;
                }
                f.dep2_state = encode(j, x);
                f.phase = 2;
                stk.push_back({f.dep2_state, 0, -1, -1});
                continue;
            } else {
                // phase 2: both deps computed
                if (status[f.dep2_state] != 2) return false;
                long long u = cost[f.dep1_state];
                long long v = cost[f.dep2_state];
                ret_instr[s] = ret_instr[f.dep2_state];
                cost[s] = (u + v + 1) % P;
                status[s] = 2;
                stk.pop_back();
            }
        }
        return true;
    };

    if (!process(encode(0, 0))) return -1;
    if (status[encode(0, 0)] != 2) return -1;
    return cost[encode(0, 0)];
}

int main(int argc, char* argv[]) {
    d = argc > 1 ? atoi(argv[1]) : 26;
    long long target1 = 150994941;
    long long target2 = 150994939;

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    auto startTime = chrono::steady_clock::now();
    auto elapsed_ms = [&]() {
        return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
    };

    fprintf(stderr, "Starting search d=%d...\n", d);

    bool found = false;
    int restarts = 0;
    int valid = 0;

    while (elapsed_ms() < 120000 && !found) {
        restarts++;

        // Initialize
        for (int j = 0; j < d; j++) {
            g1_arr[j] = j + 1; // standard initially
            gy_arr[j] = rng() % (j + 1);
        }
        // Randomly modify some g1 values
        int num_g1_changes = rng() % 4;
        for (int c = 0; c < num_g1_changes; c++) {
            int j = rng() % d;
            g1_arr[j] = rng() % (d + 1);
        }

        long long T = eval_fast();
        if (T < 0) continue;
        valid++;

        if (T == target1 || T == target2) {
            found = true;
            fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
            break;
        }

        // Hill climbing
        for (int iter = 0; iter < 100000 && !found; iter++) {
            int what = rng() % 3;
            int j = rng() % d;
            int sv_g1 = g1_arr[j], sv_gy = gy_arr[j];

            if (what == 0) gy_arr[j] = rng() % (j + 1);
            else if (what == 1) g1_arr[j] = rng() % (d + 1);
            else { gy_arr[j] = rng() % (j + 1); g1_arr[j] = rng() % (d + 1); }

            long long nT = eval_fast();
            if (nT < 0) {
                g1_arr[j] = sv_g1; gy_arr[j] = sv_gy;
                continue;
            }

            if (nT == target1 || nT == target2) {
                found = true;
                T = nT;
                fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
                break;
            }

            long long nd = min(min((nT - target1 + P) % P, (target1 - nT + P) % P),
                             min((nT - target2 + P) % P, (target2 - nT + P) % P));
            long long od = min(min((T - target1 + P) % P, (target1 - T + P) % P),
                             min((T - target2 + P) % P, (target2 - T + P) % P));

            if (nd <= od) T = nT;
            else { g1_arr[j] = sv_g1; gy_arr[j] = sv_gy; }
        }

        if (restarts % 200 == 0) {
            fprintf(stderr, "d=%d restart=%d valid=%d elapsed=%ldms\n", d, restarts, valid, elapsed_ms());
        }
    }

    if (found) {
        fprintf(stderr, "g1:");
        for (int j = 0; j < d; j++) fprintf(stderr, " %d", g1_arr[j]);
        fprintf(stderr, "\ngy:");
        for (int j = 0; j < d; j++) fprintf(stderr, " %d", gy_arr[j]);
        fprintf(stderr, "\n");

        int n = d + 1;
        printf("%d\n", n);
        for (int j = 0; j < d; j++) {
            printf("POP %d GOTO %d PUSH %d GOTO %d\n",
                j+1, g1_arr[j]+1, j+1, gy_arr[j]+1);
        }
        printf("HALT PUSH 1 GOTO %d\n", n);
    } else {
        fprintf(stderr, "NOT FOUND d=%d after %d restarts (%d valid) in %ldms\n",
            d, restarts, valid, elapsed_ms());
    }

    return 0;
}