Add files using upload-large-folder tool

1fd0050 verified 6 months ago

8.26 kB

// 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;
}

	// 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;
	}