File size: 3,035 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 | // Enumerate n=4, alphabet 1..3, find max step count and all achievable counts
#include <bits/stdc++.h>
using namespace std;
constexpr long long P = 998244353;
int n_instr = 4;
int maxChar = 3;
int type_arr[30];
int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];
optional<pair<int, long long>> dp[30][10];
bool vis[30][10];
bool infinite_flag;
pair<int, long long> solve(int i, int x) {
if (dp[i][x]) return dp[i][x].value();
if (vis[i][x]) { infinite_flag = true; return {-1, 0}; }
vis[i][x] = true;
if (type_arr[i] == 0) {
if (x == pop_char_arr[i]) {
dp[i][x] = {goto1_arr[i], 1LL};
} else {
auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
if (infinite_flag) return {-1, 0};
auto [k, v] = solve(j, x);
if (infinite_flag) return {-1, 0};
dp[i][x] = {k, (u + v + 1) % P};
}
} else {
if (x == 0) {
dp[i][x] = {-1, 1LL};
} else {
auto [j, u] = solve(goto2_arr[i], push_char_arr[i]);
if (infinite_flag) return {-1, 0};
auto [k, v] = solve(j, x);
if (infinite_flag) return {-1, 0};
dp[i][x] = {k, (u + v + 1) % P};
}
}
return dp[i][x].value();
}
long long evaluate() {
for (int i = 0; i < n_instr; i++)
for (int j = 0; j <= maxChar; j++) {
dp[i][j].reset();
vis[i][j] = false;
}
infinite_flag = false;
auto [fi, steps] = solve(0, 0);
if (infinite_flag) return -1;
return steps;
}
int main() {
long long max_steps = 0;
int halting = 0;
set<long long> seen;
// Try many random programs
mt19937 rng(42);
for (int trial = 0; trial < 10000000; trial++) {
// Random program
for (int i = 0; i < n_instr; i++) {
if (i == n_instr - 1) {
type_arr[i] = 1;
} else {
type_arr[i] = (rng() % 3 == 0) ? 1 : 0;
}
if (type_arr[i] == 0) {
pop_char_arr[i] = 1 + rng() % maxChar;
goto1_arr[i] = rng() % n_instr;
push_char_arr[i] = 1 + rng() % maxChar;
goto2_arr[i] = rng() % n_instr;
} else {
push_char_arr[i] = 1 + rng() % maxChar;
goto2_arr[i] = rng() % n_instr;
}
}
long long T = evaluate();
if (T >= 0) {
halting++;
seen.insert(T);
if (T > max_steps) {
max_steps = T;
fprintf(stderr, "New max: %lld at trial %d\n", T, trial);
}
}
}
printf("Halting: %d, distinct: %zu, max: %lld\n", halting, seen.size(), max_steps);
// Print some largest values
vector<long long> vals(seen.begin(), seen.end());
sort(vals.rbegin(), vals.rend());
printf("Top 20:");
for (int i = 0; i < min(20, (int)vals.size()); i++) printf(" %lld", vals[i]);
printf("\n");
return 0;
}
|