Add files using upload-large-folder tool

1fd0050 verified 6 months ago

7.85 kB

// Fast generalized chain search with iterative evaluation
// d POPs + 1 HALT, with variable g1[] and gy[]
// Use topological sort on dependency graph instead of recursive solve.

#include <bits/stdc++.h>
using namespace std;

constexpr long long P = 998244353;

int d;
int g1_arr[30]; // pop-match goto for POP j
int gy_arr[30]; // push goto for POP j

// State (i, x) for i in 0..d, x in 0..d
// For POP i (i < d):
//   x == i+1: result = (g1[i], 1), depends on nothing
//   x != i+1: depends on (gy[i], i+1) and then (return_of_that, x)
// For HALT (i = d):
//   x == 0: result = (-1, 1)
//   x != 0: depends on (d, 1) and then (return_of_that, x)

// Build dependency graph and solve topologically
// Each state (i, x) can depend on at most 2 other states.
// If there's a cycle, the program is infinite.

struct State {
    int i, x;
    int ret_instr;
    long long cost;
    bool computed;
    bool in_cycle_check;
};

// Encode state as i * (d+1) + x
inline int encode(int i, int x) { return i * (d + 1) + x; }

long long eval_fast() {
    int num_states = (d + 1) * (d + 1);
    vector<int> ret_instr(num_states, -2);  // -2 = not computed
    vector<long long> cost(num_states, 0);
    vector<int8_t> status(num_states, 0);  // 0=unvisited, 1=in_progress, 2=done

    // Iterative DFS with explicit stack
    struct Frame {
        int state;
        int phase; // 0=initial, 1=after dep1, 2=after dep2
        int dep1_state, dep2_state;
    };

    vector<Frame> stk;

    auto get_result = [&](int s) -> pair<int, long long> {
        return {ret_instr[s], cost[s]};
    };

    auto process = [&](int start) -> bool {
        stk.push_back({start, 0, -1, -1});

        while (!stk.empty()) {
            auto& f = stk.back();
            int s = f.state;
            int i = s / (d + 1);
            int x = s % (d + 1);

            if (f.phase == 0) {
                if (status[s] == 2) { stk.pop_back(); continue; }
                if (status[s] == 1) return false; // cycle
                status[s] = 1;

                if (i < d) {
                    if (x == i + 1) {
                        ret_instr[s] = g1_arr[i];
                        cost[s] = 1;
                        status[s] = 2;
                        stk.pop_back();
                        continue;
                    } else {
                        f.dep1_state = encode(gy_arr[i], i + 1);
                        f.phase = 1;
                        stk.push_back({f.dep1_state, 0, -1, -1});
                        continue;
                    }
                } else {
                    // HALT
                    if (x == 0) {
                        ret_instr[s] = -1;
                        cost[s] = 1;
                        status[s] = 2;
                        stk.pop_back();
                        continue;
                    } else {
                        f.dep1_state = encode(d, 1);
                        f.phase = 1;
                        stk.push_back({f.dep1_state, 0, -1, -1});
                        continue;
                    }
                }
            } else if (f.phase == 1) {
                // dep1 is computed
                if (status[f.dep1_state] != 2) return false;
                int j = ret_instr[f.dep1_state];
                if (j < 0 || j > d) {
                    // dep1 leads to halt, then continue with x
                    // Actually if j == -1, it halted.
                    // For POP: solve(gy[i], i+1) returned (-1, u). Then solve(-1, x) - invalid!
                    // This shouldn't happen in a valid program.
                    // If the subprogram halts, then the "return instruction" is -1.
                    // The next step is solve(-1, x) which is undefined.
                    // This means the program structure is broken.
                    return false;
                }
                f.dep2_state = encode(j, x);
                f.phase = 2;
                stk.push_back({f.dep2_state, 0, -1, -1});
                continue;
            } else {
                // phase 2: both deps computed
                if (status[f.dep2_state] != 2) return false;
                long long u = cost[f.dep1_state];
                long long v = cost[f.dep2_state];
                ret_instr[s] = ret_instr[f.dep2_state];
                cost[s] = (u + v + 1) % P;
                status[s] = 2;
                stk.pop_back();
            }
        }
        return true;
    };

    if (!process(encode(0, 0))) return -1;
    if (status[encode(0, 0)] != 2) return -1;
    return cost[encode(0, 0)];
}

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();
    };

    fprintf(stderr, "Starting search d=%d...\n", d);

    bool found = false;
    int restarts = 0;
    int valid = 0;

    while (elapsed_ms() < 120000 && !found) {
        restarts++;

        // Initialize
        for (int j = 0; j < d; j++) {
            g1_arr[j] = j + 1; // standard initially
            gy_arr[j] = rng() % (j + 1);
        }
        // Randomly modify some g1 values
        int num_g1_changes = rng() % 4;
        for (int c = 0; c < num_g1_changes; c++) {
            int j = rng() % d;
            g1_arr[j] = rng() % (d + 1);
        }

        long long T = eval_fast();
        if (T < 0) continue;
        valid++;

        if (T == target1 || T == target2) {
            found = true;
            fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
            break;
        }

        // Hill climbing
        for (int iter = 0; iter < 100000 && !found; iter++) {
            int what = rng() % 3;
            int j = rng() % d;
            int sv_g1 = g1_arr[j], sv_gy = gy_arr[j];

            if (what == 0) gy_arr[j] = rng() % (j + 1);
            else if (what == 1) g1_arr[j] = rng() % (d + 1);
            else { gy_arr[j] = rng() % (j + 1); g1_arr[j] = rng() % (d + 1); }

            long long nT = eval_fast();
            if (nT < 0) {
                g1_arr[j] = sv_g1; gy_arr[j] = sv_gy;
                continue;
            }

            if (nT == target1 || nT == target2) {
                found = true;
                T = nT;
                fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
                break;
            }

            long long nd = min(min((nT - target1 + P) % P, (target1 - nT + P) % P),
                             min((nT - target2 + P) % P, (target2 - nT + P) % P));
            long long od = min(min((T - target1 + P) % P, (target1 - T + P) % P),
                             min((T - target2 + P) % P, (target2 - T + P) % P));

            if (nd <= od) T = nT;
            else { g1_arr[j] = sv_g1; gy_arr[j] = sv_gy; }
        }

        if (restarts % 200 == 0) {
            fprintf(stderr, "d=%d restart=%d valid=%d elapsed=%ldms\n", d, restarts, valid, elapsed_ms());
        }
    }

    if (found) {
        fprintf(stderr, "g1:");
        for (int j = 0; j < d; j++) fprintf(stderr, " %d", g1_arr[j]);
        fprintf(stderr, "\ngy:");
        for (int j = 0; j < d; j++) fprintf(stderr, " %d", gy_arr[j]);
        fprintf(stderr, "\n");

        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_arr[j]+1, j+1, gy_arr[j]+1);
        }
        printf("HALT PUSH 1 GOTO %d\n", n);
    } else {
        fprintf(stderr, "NOT FOUND d=%d after %d restarts (%d valid) in %ldms\n",
            d, restarts, valid, elapsed_ms());
    }

    return 0;
}

	// Fast generalized chain search with iterative evaluation
	// d POPs + 1 HALT, with variable g1[] and gy[]
	// Use topological sort on dependency graph instead of recursive solve.

	#include <bits/stdc++.h>
	using namespace std;

	constexpr long long P = 998244353;

	int d;
	int g1_arr[30]; // pop-match goto for POP j
	int gy_arr[30]; // push goto for POP j

	// State (i, x) for i in 0..d, x in 0..d
	// For POP i (i < d):
	// x == i+1: result = (g1[i], 1), depends on nothing
	// x != i+1: depends on (gy[i], i+1) and then (return_of_that, x)
	// For HALT (i = d):
	// x == 0: result = (-1, 1)
	// x != 0: depends on (d, 1) and then (return_of_that, x)

	// Build dependency graph and solve topologically
	// Each state (i, x) can depend on at most 2 other states.
	// If there's a cycle, the program is infinite.

	struct State {
	int i, x;
	int ret_instr;
	long long cost;
	bool computed;
	bool in_cycle_check;
	};

	// Encode state as i * (d+1) + x
	inline int encode(int i, int x) { return i * (d + 1) + x; }

	long long eval_fast() {
	int num_states = (d + 1) * (d + 1);
	vector<int> ret_instr(num_states, -2); // -2 = not computed
	vector<long long> cost(num_states, 0);
	vector<int8_t> status(num_states, 0); // 0=unvisited, 1=in_progress, 2=done

	// Iterative DFS with explicit stack
	struct Frame {
	int state;
	int phase; // 0=initial, 1=after dep1, 2=after dep2
	int dep1_state, dep2_state;
	};

	vector<Frame> stk;

	auto get_result = [&](int s) -> pair<int, long long> {
	return {ret_instr[s], cost[s]};
	};

	auto process = [&](int start) -> bool {
	stk.push_back({start, 0, -1, -1});

	while (!stk.empty()) {
	auto& f = stk.back();
	int s = f.state;
	int i = s / (d + 1);
	int x = s % (d + 1);

	if (f.phase == 0) {
	if (status[s] == 2) { stk.pop_back(); continue; }
	if (status[s] == 1) return false; // cycle
	status[s] = 1;

	if (i < d) {
	if (x == i + 1) {
	ret_instr[s] = g1_arr[i];
	cost[s] = 1;
	status[s] = 2;
	stk.pop_back();
	continue;
	} else {
	f.dep1_state = encode(gy_arr[i], i + 1);
	f.phase = 1;
	stk.push_back({f.dep1_state, 0, -1, -1});
	continue;
	}
	} else {
	// HALT
	if (x == 0) {
	ret_instr[s] = -1;
	cost[s] = 1;
	status[s] = 2;
	stk.pop_back();
	continue;
	} else {
	f.dep1_state = encode(d, 1);
	f.phase = 1;
	stk.push_back({f.dep1_state, 0, -1, -1});
	continue;
	}
	}
	} else if (f.phase == 1) {
	// dep1 is computed
	if (status[f.dep1_state] != 2) return false;
	int j = ret_instr[f.dep1_state];
	if (j < 0 \|\| j > d) {
	// dep1 leads to halt, then continue with x
	// Actually if j == -1, it halted.
	// For POP: solve(gy[i], i+1) returned (-1, u). Then solve(-1, x) - invalid!
	// This shouldn't happen in a valid program.
	// If the subprogram halts, then the "return instruction" is -1.
	// The next step is solve(-1, x) which is undefined.
	// This means the program structure is broken.
	return false;
	}
	f.dep2_state = encode(j, x);
	f.phase = 2;
	stk.push_back({f.dep2_state, 0, -1, -1});
	continue;
	} else {
	// phase 2: both deps computed
	if (status[f.dep2_state] != 2) return false;
	long long u = cost[f.dep1_state];
	long long v = cost[f.dep2_state];
	ret_instr[s] = ret_instr[f.dep2_state];
	cost[s] = (u + v + 1) % P;
	status[s] = 2;
	stk.pop_back();
	}
	}
	return true;
	};

	if (!process(encode(0, 0))) return -1;
	if (status[encode(0, 0)] != 2) return -1;
	return cost[encode(0, 0)];
	}

	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();
	};

	fprintf(stderr, "Starting search d=%d...\n", d);

	bool found = false;
	int restarts = 0;
	int valid = 0;

	while (elapsed_ms() < 120000 && !found) {
	restarts++;

	// Initialize
	for (int j = 0; j < d; j++) {
	g1_arr[j] = j + 1; // standard initially
	gy_arr[j] = rng() % (j + 1);
	}
	// Randomly modify some g1 values
	int num_g1_changes = rng() % 4;
	for (int c = 0; c < num_g1_changes; c++) {
	int j = rng() % d;
	g1_arr[j] = rng() % (d + 1);
	}

	long long T = eval_fast();
	if (T < 0) continue;
	valid++;

	if (T == target1 \|\| T == target2) {
	found = true;
	fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
	break;
	}

	// Hill climbing
	for (int iter = 0; iter < 100000 && !found; iter++) {
	int what = rng() % 3;
	int j = rng() % d;
	int sv_g1 = g1_arr[j], sv_gy = gy_arr[j];

	if (what == 0) gy_arr[j] = rng() % (j + 1);
	else if (what == 1) g1_arr[j] = rng() % (d + 1);
	else { gy_arr[j] = rng() % (j + 1); g1_arr[j] = rng() % (d + 1); }

	long long nT = eval_fast();
	if (nT < 0) {
	g1_arr[j] = sv_g1; gy_arr[j] = sv_gy;
	continue;
	}

	if (nT == target1 \|\| nT == target2) {
	found = true;
	T = nT;
	fprintf(stderr, "FOUND! d=%d T=%lld\n", d, T);
	break;
	}

	long long nd = min(min((nT - target1 + P) % P, (target1 - nT + P) % P),
	min((nT - target2 + P) % P, (target2 - nT + P) % P));
	long long od = min(min((T - target1 + P) % P, (target1 - T + P) % P),
	min((T - target2 + P) % P, (target2 - T + P) % P));

	if (nd <= od) T = nT;
	else { g1_arr[j] = sv_g1; gy_arr[j] = sv_gy; }
	}

	if (restarts % 200 == 0) {
	fprintf(stderr, "d=%d restart=%d valid=%d elapsed=%ldms\n", d, restarts, valid, elapsed_ms());
	}
	}

	if (found) {
	fprintf(stderr, "g1:");
	for (int j = 0; j < d; j++) fprintf(stderr, " %d", g1_arr[j]);
	fprintf(stderr, "\ngy:");
	for (int j = 0; j < d; j++) fprintf(stderr, " %d", gy_arr[j]);
	fprintf(stderr, "\n");

	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_arr[j]+1, j+1, gy_arr[j]+1);
	}
	printf("HALT PUSH 1 GOTO %d\n", n);
	} else {
	fprintf(stderr, "NOT FOUND d=%d after %d restarts (%d valid) in %ldms\n",
	d, restarts, valid, elapsed_ms());
	}

	return 0;
	}