File size: 4,669 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | // 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;
}
|