File size: 8,259 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 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 | // General program searcher: non-chain programs that might achieve target with fewer instructions
// For n instructions, each can be POP or HALT with various parameters
// The checker computes step count via memoized recursion on (instr, stack_top)
//
// Key insight: with non-chain goto targets, we can create more complex execution patterns
// that potentially achieve higher step counts with fewer instructions.
//
// For a program with n instructions and alphabet {1..A}:
// - Each state is (instruction, stack_top) where stack_top in {0..A}
// - The execution DAG on these states determines step count
// - Step count can potentially be O(n * A * ...) depending on structure
//
// Strategy: for n instructions using alphabet {1..a}, we have n*(a+1) states
// Each POP instr i with char c: when top==c, go to goto1 (1 step). Otherwise push char2 goto goto2.
// Each HALT instr i: when top==0, halt (1 step). Otherwise push char goto goto2.
//
// The step count from state (i, x) is computed as:
// POP i, top x: if x == a[i][0]: steps=1, next=(a[i][1], ???)
// Actually the recursion returns (next_instr, steps).
// When x != pop_char: first compute (j, u) = solve(push_goto, push_char)
// then (k, v) = solve(j, x)
// result = (k, u + v + 1)
//
// So solve(i, x) computes: starting at instr i with x on top of stack,
// what is the total number of steps until halt, and what is the "return instruction"
// (the instruction after the last pop that cleared this stack level)
#include <bits/stdc++.h>
using namespace std;
constexpr long long P = 998244353;
struct MInt {
long long x;
MInt(): x(0) {}
MInt(long long v): x(((v % P) + P) % P) {}
MInt operator+(const MInt& b) const { return MInt(x + b.x); }
MInt operator-(const MInt& b) const { return MInt(x - b.x); }
MInt operator*(const MInt& b) const { return MInt(x * b.x); }
bool operator==(const MInt& b) const { return x == b.x; }
};
int n;
int type[30]; // 0=POP, 1=HALT
int pop_char[30], goto1[30], push_char[30], goto2[30];
// For HALT: push_char[i], goto2[i]
optional<pair<int, MInt>> dp[30][1025];
bool vis[30][1025];
bool infinite_flag;
pair<int, MInt> solve(int i, int x) {
if (dp[i][x]) return dp[i][x].value();
if (vis[i][x]) { infinite_flag = true; return {-1, MInt(0)}; }
vis[i][x] = true;
if (type[i] == 0) { // POP
if (x == pop_char[i]) {
dp[i][x] = {goto1[i], MInt(1)};
} else {
auto [j, u] = solve(goto2[i], push_char[i]);
if (infinite_flag) return {-1, MInt(0)};
auto [k, v] = solve(j, x);
if (infinite_flag) return {-1, MInt(0)};
dp[i][x] = {k, u + v + MInt(1)};
}
} else { // HALT
if (x == 0) {
dp[i][x] = {-1, MInt(1)};
} else {
auto [j, u] = solve(goto2[i], push_char[i]);
if (infinite_flag) return {-1, MInt(0)};
auto [k, v] = solve(j, x);
if (infinite_flag) return {-1, MInt(0)};
dp[i][x] = {k, u + v + MInt(1)};
}
}
return dp[i][x].value();
}
MInt evaluate() {
for (int i = 0; i < n; i++)
for (int j = 0; j <= 1024; j++) {
dp[i][j].reset();
vis[i][j] = false;
}
infinite_flag = false;
auto [fi, steps] = solve(0, 0);
if (infinite_flag) return MInt(-1); // sentinel
return steps;
}
int main(int argc, char* argv[]) {
if (argc < 3) {
cerr << "Usage: " << argv[0] << " <target_mod_P> <n_instructions>" << endl;
return 1;
}
long long target = atoll(argv[1]);
n = atoi(argv[2]);
int maxAlpha = min(n + 1, 5); // limit alphabet size for search
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();
};
// Random program generator
auto randomize = [&]() {
for (int i = 0; i < n; i++) {
if (i == n - 1) {
// Last instruction should be HALT for termination
type[i] = 1;
} else {
type[i] = (rng() % 4 == 0) ? 1 : 0; // mostly POP
}
if (type[i] == 0) {
pop_char[i] = 1 + rng() % maxAlpha;
goto1[i] = rng() % n;
push_char[i] = 1 + rng() % maxAlpha;
goto2[i] = rng() % n;
} else {
push_char[i] = 1 + rng() % maxAlpha;
goto2[i] = rng() % n;
}
}
};
// Mutation
auto mutate = [&]() {
int i = rng() % n;
int what = rng() % 5;
if (what == 0 && i < n - 1) {
// flip type
type[i] = 1 - type[i];
if (type[i] == 0) {
pop_char[i] = 1 + rng() % maxAlpha;
goto1[i] = rng() % n;
push_char[i] = 1 + rng() % maxAlpha;
goto2[i] = rng() % n;
} else {
push_char[i] = 1 + rng() % maxAlpha;
goto2[i] = rng() % n;
}
} else if (what == 1) {
if (type[i] == 0) push_char[i] = 1 + rng() % maxAlpha;
else push_char[i] = 1 + rng() % maxAlpha;
} else if (what == 2) {
goto2[i] = rng() % n;
} else if (what == 3 && type[i] == 0) {
goto1[i] = rng() % n;
} else {
if (type[i] == 0) pop_char[i] = 1 + rng() % maxAlpha;
}
};
int restarts = 0;
bool found = false;
// Save best state
int best_type[30], best_pop_char[30], best_goto1[30], best_push_char[30], best_goto2[30];
while (elapsed_ms() < 120000 && !found) { // 2 minutes
restarts++;
randomize();
MInt T = evaluate();
if (T.x == (long long)(-1 + P) % P) continue; // infinite
if (T.x == target) { found = true; break; }
for (int iter = 0; iter < 100000 && !found; iter++) {
// Save state
int sv_type[30], sv_pop[30], sv_g1[30], sv_push[30], sv_g2[30];
memcpy(sv_type, type, sizeof(int)*n);
memcpy(sv_pop, pop_char, sizeof(int)*n);
memcpy(sv_g1, goto1, sizeof(int)*n);
memcpy(sv_push, push_char, sizeof(int)*n);
memcpy(sv_g2, goto2, sizeof(int)*n);
mutate();
MInt nT = evaluate();
if (nT.x == (long long)(-1 + P) % P) {
// revert
memcpy(type, sv_type, sizeof(int)*n);
memcpy(pop_char, sv_pop, sizeof(int)*n);
memcpy(goto1, sv_g1, sizeof(int)*n);
memcpy(push_char, sv_push, sizeof(int)*n);
memcpy(goto2, sv_g2, sizeof(int)*n);
continue;
}
if (nT.x == target) { found = true; break; }
long long nd = min((nT.x - target + P) % P, (target - nT.x + P) % P);
long long od = min((T.x - target + P) % P, (target - T.x + P) % P);
if (nd <= od) {
T = nT;
} else {
// revert
memcpy(type, sv_type, sizeof(int)*n);
memcpy(pop_char, sv_pop, sizeof(int)*n);
memcpy(goto1, sv_g1, sizeof(int)*n);
memcpy(push_char, sv_push, sizeof(int)*n);
memcpy(goto2, sv_g2, sizeof(int)*n);
}
}
if (restarts % 100 == 0) {
cerr << "restart=" << restarts << " elapsed=" << elapsed_ms() << "ms" << endl;
}
}
if (found) {
cerr << "FOUND n=" << n << " after " << restarts << " restarts" << endl;
// Output
cout << n << endl;
for (int i = 0; i < n; i++) {
if (type[i] == 0) {
cout << "POP " << pop_char[i] << " GOTO " << (goto1[i]+1)
<< " PUSH " << push_char[i] << " GOTO " << (goto2[i]+1) << endl;
} else {
cout << "HALT PUSH " << push_char[i] << " GOTO " << (goto2[i]+1) << endl;
}
}
} else {
cerr << "NOT FOUND n=" << n << " after " << restarts << " restarts" << endl;
}
return 0;
}
|