Add files using upload-large-folder tool

1fd0050 verified 6 months ago

7.34 kB

// Analyze what step counts are achievable with small n and varying alphabet
// Try to understand the structure of possible step counts
#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_instr;
int type_arr[30]; // 0=POP, 1=HALT
int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];

int maxChar;
optional<pair<int, MInt>> dp[30][1030];
bool vis[30][1030];
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_arr[i] == 0) { // POP
        if (x == pop_char_arr[i]) {
            dp[i][x] = {goto1_arr[i], MInt(1)};
        } else {
            auto [j, u] = solve(goto2_arr[i], push_char_arr[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_arr[i], push_char_arr[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_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 MInt(P - 1); // sentinel for infinite
    return steps;
}

int main() {
    // Let's try a specific structure:
    // n=2: one HALT + one POP
    // HALT pushes some char b and goes to instruction g
    // POP pops some char a, goto g1, push char c, goto g2

    // With n=2, alphabet {1..A}:
    // Instruction 0: HALT PUSH b GOTO g (g in {0,1})
    // Instruction 1: POP a GOTO g1 PUSH c GOTO g2

    // solve(0, 0) = 1 (halt immediately)
    // solve(0, x) for x != 0: push b, goto g. So solve(g, b) then solve(result, x)
    //   steps = 1 + solve(g, b).steps + solve(solve(g,b).ret, x).steps

    // Let's manually compute for n=2:
    // Instr 0: HALT PUSH 1 GOTO 1
    // Instr 1: POP 1 GOTO 0 PUSH 1 GOTO 0
    //
    // solve(0, 0) = (-1, 1)  -- halt
    // solve(1, 1) = (0, 1)   -- pop, goto 0
    // solve(0, x) for x>0: push 1 goto 1. solve(1, 1) = (0, 1). solve(0, x).
    //   But this is circular! solve(0, x) depends on solve(0, x).
    //   So this program doesn't halt for x > 0 (other than when x is on the HALT path)

    // For the program to halt, we need no cycles in the dependency graph.
    // With n=2, alphabet 1..2:
    // Instr 0: HALT PUSH 1 GOTO 1
    // Instr 1: POP 2 GOTO 0 PUSH 1 GOTO 0
    //
    // solve(0, 0) = (-1, 1)
    // solve(1, 2) = (0, 1) -- pop, goto 0
    // solve(0, x) for x != 0: push 1, goto 1, solve(1, 1)
    //   solve(1, 1): x=1 != 2 (pop char). Push 1, goto 0. solve(0, 1) then solve(result, 1).
    //   solve(0, 1): push 1, goto 1. solve(1, 1) -- CYCLE! infinite.

    // Hmm. The challenge with small n is avoiding cycles.
    // Chain programs avoid cycles by having strictly increasing instruction indices.

    // Let me think about what makes chain programs special:
    // Chain: instrs 0..d-1 are POP, instr d is HALT
    // POP j: pops char (j+1), goto (j+1), push char (j+1), goto gy[j]
    // HALT d: push 1, goto d

    // The key is: POP j pops char (j+1). So when we push char (j+1) and call solve(gy[j], j+1),
    // the only instruction that can pop char (j+1) is instruction j itself.
    // This creates a well-structured recursion.

    // For non-chain: we could use different characters to create multiple "levels" of recursion
    // with the same instruction. E.g., one POP instruction that handles multiple stack symbols.

    // Actually, let me think about n=3 with the right structure:
    // If we can get 2 POP instructions to both create exponential growth,
    // and chain them, we might get 2^a * 2^b type behavior with a+b controlled.

    // Actually, let me try a different approach: enumerate step counts for very small programs

    n_instr = 3;
    maxChar = 4;

    set<long long> seen_steps;
    long long max_steps = 0;

    // Enumerate all programs with n=3, alphabet 1..4
    // Last instruction must be HALT
    // Try all configurations

    int count = 0;
    int halting = 0;

    for (int t0 = 0; t0 <= 1; t0++)
    for (int t1 = 0; t1 <= 1; t1++) {
        type_arr[2] = 1; // HALT
        type_arr[0] = t0;
        type_arr[1] = t1;

        auto enumerate_instr = [&](int i, auto& self, auto& callback) -> void {
            if (i == n_instr) {
                callback();
                return;
            }
            if (type_arr[i] == 0) { // POP
                for (int a = 1; a <= maxChar; a++)
                for (int g1 = 0; g1 < n_instr; g1++)
                for (int c = 1; c <= maxChar; c++)
                for (int g2 = 0; g2 < n_instr; g2++) {
                    pop_char_arr[i] = a;
                    goto1_arr[i] = g1;
                    push_char_arr[i] = c;
                    goto2_arr[i] = g2;
                    self(i + 1, self, callback);
                }
            } else { // HALT
                for (int c = 1; c <= maxChar; c++)
                for (int g2 = 0; g2 < n_instr; g2++) {
                    push_char_arr[i] = c;
                    goto2_arr[i] = g2;
                    self(i + 1, self, callback);
                }
            }
        };

        auto callback = [&]() {
            count++;
            MInt T = evaluate();
            if (T.x != (P - 1) % P) {
                halting++;
                seen_steps.insert(T.x);
                if (T.x > max_steps) {
                    max_steps = T.x;
                    cerr << "New max: " << T.x << " with config:";
                    for (int i = 0; i < n_instr; i++) {
                        if (type_arr[i] == 0) {
                            cerr << " POP" << pop_char_arr[i] << "→" << goto1_arr[i] << ",push" << push_char_arr[i] << "→" << goto2_arr[i];
                        } else {
                            cerr << " HALT,push" << push_char_arr[i] << "→" << goto2_arr[i];
                        }
                    }
                    cerr << endl;
                }
            }
        };

        enumerate_instr(0, enumerate_instr, callback);
    }

    cout << "Total programs: " << count << ", halting: " << halting << endl;
    cout << "Distinct step counts: " << seen_steps.size() << endl;
    cout << "Max step count: " << max_steps << endl;
    cout << "First 50 step counts:";
    int printed = 0;
    for (long long v : seen_steps) {
        if (printed++ >= 50) break;
        cout << " " << v;
    }
    cout << endl;

    return 0;
}

	// Analyze what step counts are achievable with small n and varying alphabet
	// Try to understand the structure of possible step counts
	#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_instr;
	int type_arr[30]; // 0=POP, 1=HALT
	int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30];

	int maxChar;
	optional<pair<int, MInt>> dp[30][1030];
	bool vis[30][1030];
	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_arr[i] == 0) { // POP
	if (x == pop_char_arr[i]) {
	dp[i][x] = {goto1_arr[i], MInt(1)};
	} else {
	auto [j, u] = solve(goto2_arr[i], push_char_arr[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_arr[i], push_char_arr[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_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 MInt(P - 1); // sentinel for infinite
	return steps;
	}

	int main() {
	// Let's try a specific structure:
	// n=2: one HALT + one POP
	// HALT pushes some char b and goes to instruction g
	// POP pops some char a, goto g1, push char c, goto g2

	// With n=2, alphabet {1..A}:
	// Instruction 0: HALT PUSH b GOTO g (g in {0,1})
	// Instruction 1: POP a GOTO g1 PUSH c GOTO g2

	// solve(0, 0) = 1 (halt immediately)
	// solve(0, x) for x != 0: push b, goto g. So solve(g, b) then solve(result, x)
	// steps = 1 + solve(g, b).steps + solve(solve(g,b).ret, x).steps

	// Let's manually compute for n=2:
	// Instr 0: HALT PUSH 1 GOTO 1
	// Instr 1: POP 1 GOTO 0 PUSH 1 GOTO 0
	//
	// solve(0, 0) = (-1, 1) -- halt
	// solve(1, 1) = (0, 1) -- pop, goto 0
	// solve(0, x) for x>0: push 1 goto 1. solve(1, 1) = (0, 1). solve(0, x).
	// But this is circular! solve(0, x) depends on solve(0, x).
	// So this program doesn't halt for x > 0 (other than when x is on the HALT path)

	// For the program to halt, we need no cycles in the dependency graph.
	// With n=2, alphabet 1..2:
	// Instr 0: HALT PUSH 1 GOTO 1
	// Instr 1: POP 2 GOTO 0 PUSH 1 GOTO 0
	//
	// solve(0, 0) = (-1, 1)
	// solve(1, 2) = (0, 1) -- pop, goto 0
	// solve(0, x) for x != 0: push 1, goto 1, solve(1, 1)
	// solve(1, 1): x=1 != 2 (pop char). Push 1, goto 0. solve(0, 1) then solve(result, 1).
	// solve(0, 1): push 1, goto 1. solve(1, 1) -- CYCLE! infinite.

	// Hmm. The challenge with small n is avoiding cycles.
	// Chain programs avoid cycles by having strictly increasing instruction indices.

	// Let me think about what makes chain programs special:
	// Chain: instrs 0..d-1 are POP, instr d is HALT
	// POP j: pops char (j+1), goto (j+1), push char (j+1), goto gy[j]
	// HALT d: push 1, goto d

	// The key is: POP j pops char (j+1). So when we push char (j+1) and call solve(gy[j], j+1),
	// the only instruction that can pop char (j+1) is instruction j itself.
	// This creates a well-structured recursion.

	// For non-chain: we could use different characters to create multiple "levels" of recursion
	// with the same instruction. E.g., one POP instruction that handles multiple stack symbols.

	// Actually, let me think about n=3 with the right structure:
	// If we can get 2 POP instructions to both create exponential growth,
	// and chain them, we might get 2^a * 2^b type behavior with a+b controlled.

	// Actually, let me try a different approach: enumerate step counts for very small programs

	n_instr = 3;
	maxChar = 4;

	set<long long> seen_steps;
	long long max_steps = 0;

	// Enumerate all programs with n=3, alphabet 1..4
	// Last instruction must be HALT
	// Try all configurations

	int count = 0;
	int halting = 0;

	for (int t0 = 0; t0 <= 1; t0++)
	for (int t1 = 0; t1 <= 1; t1++) {
	type_arr[2] = 1; // HALT
	type_arr[0] = t0;
	type_arr[1] = t1;

	auto enumerate_instr = [&](int i, auto& self, auto& callback) -> void {
	if (i == n_instr) {
	callback();
	return;
	}
	if (type_arr[i] == 0) { // POP
	for (int a = 1; a <= maxChar; a++)
	for (int g1 = 0; g1 < n_instr; g1++)
	for (int c = 1; c <= maxChar; c++)
	for (int g2 = 0; g2 < n_instr; g2++) {
	pop_char_arr[i] = a;
	goto1_arr[i] = g1;
	push_char_arr[i] = c;
	goto2_arr[i] = g2;
	self(i + 1, self, callback);
	}
	} else { // HALT
	for (int c = 1; c <= maxChar; c++)
	for (int g2 = 0; g2 < n_instr; g2++) {
	push_char_arr[i] = c;
	goto2_arr[i] = g2;
	self(i + 1, self, callback);
	}
	}
	};

	auto callback = [&]() {
	count++;
	MInt T = evaluate();
	if (T.x != (P - 1) % P) {
	halting++;
	seen_steps.insert(T.x);
	if (T.x > max_steps) {
	max_steps = T.x;
	cerr << "New max: " << T.x << " with config:";
	for (int i = 0; i < n_instr; i++) {
	if (type_arr[i] == 0) {
	cerr << " POP" << pop_char_arr[i] << "→" << goto1_arr[i] << ",push" << push_char_arr[i] << "→" << goto2_arr[i];
	} else {
	cerr << " HALT,push" << push_char_arr[i] << "→" << goto2_arr[i];
	}
	}
	cerr << endl;
	}
	}
	};

	enumerate_instr(0, enumerate_instr, callback);
	}

	cout << "Total programs: " << count << ", halting: " << halting << endl;
	cout << "Distinct step counts: " << seen_steps.size() << endl;
	cout << "Max step count: " << max_steps << endl;
	cout << "First 50 step counts:";
	int printed = 0;
	for (long long v : seen_steps) {
	if (printed++ >= 50) break;
	cout << " " << v;
	}
	cout << endl;

	return 0;
	}