Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_8 /general_search.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
1fd0050 verified
Raw History Blame Contribute Delete
9.56 kB
#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;
}