docker_space/frontier_cs_8/gen_chain_search.cpp

// Generalized chain search: d POPs + 1 HALT
// POP j: pop (j+1), goto g1[j], push (j+1), goto gy[j]
// HALT: push 1, goto d
// Variables: g1[j] in {0..d}, gy[j] in {0..j}
// For d=26, search for targets 150994941 and 150994939

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

constexpr long long P = 998244353;

int d;
int g1[30]; // pop-match goto
int gy[30]; // push goto

// dp[i][x] where i in 0..d, x in 0..d
optional<pair<int, long long>> dp[31][31];
bool vis[31][31];
bool inf_flag;

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

    if (i < d) {
        if (x == i + 1) {
            dp[i][x] = {g1[i], 1LL};
        } else {
            auto [j, u] = solve(gy[i], i + 1);
            if (inf_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (inf_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    } else {
        // HALT
        if (x == 0) {
            dp[i][x] = {-1, 1LL};
        } else {
            auto [j, u] = solve(d, 1); // push 1, goto d (self)
            if (inf_flag) return {-1, 0};
            auto [k, v] = solve(j, x);
            if (inf_flag) return {-1, 0};
            dp[i][x] = {k, (u + v + 1) % P};
        }
    }
    return dp[i][x].value();
}

long long eval() {
    for (int i = 0; i <= d; i++)
        for (int j = 0; j <= d; j++) {
            dp[i][j].reset();
            vis[i][j] = false;
        }
    inf_flag = false;
    auto [fi, steps] = solve(0, 0);
    if (inf_flag) return -1;
    return steps;
}

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();
    };

    bool found = false;
    int restarts = 0;

    fprintf(stderr, "Starting search d=%d...\n", d);
    while (elapsed_ms() < 120000 && !found) {
        restarts++;

        // Initialize: standard g1, random gy
        for (int j = 0; j < d; j++) {
            g1[j] = j + 1; // standard
            gy[j] = rng() % (j + 1);
        }

        long long T = eval();
        if (T < 0) continue;

        for (int iter = 0; iter < 500000 && !found; iter++) {
            if (T == target1 || T == target2) {
                found = true;
                fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
                fprintf(stderr, "g1:");
                for (int j = 0; j < d; j++) fprintf(stderr, " %d", g1[j]);
                fprintf(stderr, "\ngy:");
                for (int j = 0; j < d; j++) fprintf(stderr, " %d", gy[j]);
                fprintf(stderr, "\n");

                // Output program
                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[j]+1, j+1, gy[j]+1);
                }
                printf("HALT PUSH 1 GOTO %d\n", n);
                break;
            }

            // Mutate
            int what = rng() % 3;
            int j = rng() % d;

            int sv_g1 = g1[j], sv_gy = gy[j];

            if (what == 0) {
                gy[j] = rng() % (j + 1);
            } else if (what == 1) {
                g1[j] = rng() % (d + 1); // allow goto any instr 0..d
            } else {
                gy[j] = rng() % (j + 1);
                g1[j] = rng() % (d + 1);
            }

            long long nT = eval();
            if (nT < 0) {
                g1[j] = sv_g1; gy[j] = sv_gy;
                continue;
            }

            long long nd1 = min((nT - target1 + P) % P, (target1 - nT + P) % P);
            long long nd2 = min((nT - target2 + P) % P, (target2 - nT + P) % P);
            long long od1 = min((T - target1 + P) % P, (target1 - T + P) % P);
            long long od2 = min((T - target2 + P) % P, (target2 - T + P) % P);
            long long best_nd = min(nd1, nd2);
            long long best_od = min(od1, od2);

            if (best_nd <= best_od) T = nT;
            else { g1[j] = sv_g1; gy[j] = sv_gy; }
        }

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

    if (!found) {
        fprintf(stderr, "NOT FOUND d=%d after %d restarts in %ldms\n", d, restarts, elapsed_ms());
    }

    return 0;
}