#include <cstdint>
#include <iomanip>
#include <iostream>
#include <set>
#include <vector>

void bb1();
void bb2();
void bb3();
void bb4();

typedef int_fast8_t i8;
typedef int64_t i64;
typedef uint64_t u64;

int main() {
    int n;
    std::cout << "Card count: ";
    std::cin >> n;
    std::cout << "\n";

    if (n < 1) std::cout << "Can not compute busy beaver function for less than 1 card!\n";
    else if (n == 1) bb1();
    else if (n == 2) bb2();
    else if (n == 3) bb3();
    else if (n == 4) bb4();
    else std::cout << "Can not compute busy beaver function for more than 4 cards!\n";

    return 0;
}

inline i8 spl(i64 raw) {
    return (raw > 0l) - (raw <= 0l);
}

inline size_t index(i64 pos) {
    const i64 mask = pos >> 63;
    const u64 mag = (pos + mask) ^ mask;
    return static_cast<size_t>((mag << 1) - (pos < 0));
}

inline void check(std::vector<i8>& vec, size_t idx) {
    if (idx >= vec.size()) vec.resize(idx << 1, 0);
}

inline size_t count(const std::vector<i8>& vec) {
    size_t num = 0;
    for (i8 c : vec) {
        num += (c > 0);
    }
    return num;
}

inline size_t fullhash(const std::vector<i8>& vec, i64 state, i8 in, size_t idx) {
    size_t h = 5381 + vec.size();
    for (i8 c : vec) {
        h = ((h << 5) + h) + c;
    }
    h = ((h << 5) + h) + state;
    h = ((h << 5) + h) + in;
    return ((h << 5) + h) + idx;
}

template <typename T>
inline bool contains(const std::set<T> set, T& elem) {
    return set.find(elem) != set.end();
}

void bb1() {
    constexpr size_t VECLIMIT = 4;
    constexpr size_t SETLIMIT = 16;

    size_t score = 0;

    i64 perm = -1;
    i64 card[1][2][3];

    while (++perm < 64) {
        i64 valid = 0;
        i64 state;
        i64 c0 = perm / 8;
        i64 c1 = perm % 8;

        card[0][0][0] = c0 & 1;
        card[0][0][1] = spl(c0 & 2);
        card[0][0][2] = state = c0 >> 2;
        valid += (state < 1);

        card[0][1][0] = c1 & 1;
        card[0][1][1] = spl(c1 & 2);
        card[0][1][2] = state = c1 >> 2;
        valid += (state < 1);

        if (!valid) continue;

        auto vec = std::vector<i8>(1, 0);
        auto hashes = std::set<size_t>();

        state = 0;
        i8 in = 0;
        i64 pos = 0;
        size_t hash, idx = 0;

        do {
            if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = fullhash(vec, state, in, idx))) {
                state = -1;
                break;
            }
            else hashes.insert(hash);
            idx = index(pos);
            check(vec, idx);
            in = vec[idx];
            vec[idx] = static_cast<i8>(card[state][in][0]);
            pos += card[state][in][1];
            state = card[state][in][2];
        }       while (state < 1);

        if (state > 0) score = std::max(score, count(vec));
    }

    std::cout << "Score: " << score << "\n";
}

void bb2() {
    constexpr size_t VECLIMIT = 8;
    constexpr size_t SETLIMIT = 32;

    size_t score = 0;

    i64 perm = -1;
    i64 card[2][2][3];

    while (++perm < 20736) {
        i64 valid = 0;
        i64 state;
        i64 c0 = perm / 1728;
        i64 c1 = (perm / 144) % 12;
        i64 c2 = (perm / 12) % 12;
        i64 c3 = perm % 12;

        card[0][0][0] = c0 & 1;
        card[0][0][1] = spl(c0 & 2);
        card[0][0][2] = state = c0 >> 2;
        valid += (state < 2);

        card[0][1][0] = c1 & 1;
        card[0][1][1] = spl(c1 & 2);
        card[0][1][2] = state = c1 >> 2;
        valid += (state < 2);

        card[1][0][0] = c2 & 1;
        card[1][0][1] = spl(c2 & 2);
        card[1][0][2] = state = c2 >> 2;
        valid += (state < 2);

        card[1][1][0] = c3 & 1;
        card[1][1][1] = spl(c3 & 2);
        card[1][1][2] = state = c3 >> 2;
        valid += (state < 2);

        if (!valid) continue;

        auto vec = std::vector<i8>(1, 0);
        auto hashes = std::set<size_t>();

        state = 0;
        i8 in = 0;
        i64 pos = 0;
        size_t hash, idx = 0;

        do {
            if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = fullhash(vec, state, in, idx))) {
                state = -1;
                break;
            }
            else hashes.insert(hash);
            idx = index(pos);
            check(vec, idx);
            in = vec[idx];
            vec[idx] = static_cast<i8>(card[state][in][0]);
            pos += card[state][in][1];
            state = card[state][in][2];
        }       while (state < 2);

        if (state > 0) score = std::max(score, count(vec));
    }

    std::cout << "Score: " << score << "\n";
}

void bb3() {
    std::cout << "This may take some time...\n0%";

    constexpr i64 PERMCOUNT = 16777216;
    constexpr size_t VECLIMIT = 16;
    constexpr size_t SETLIMIT = 64;

    size_t score = 0;

    i64 perm = -1;
    i64 card[3][2][3];

    int progress = 0;

    while (++perm < PERMCOUNT) {
        i64 valid = 0;
        i64 state;
        i64 c0 = perm / 1048576;
        i64 c1 = (perm / 65536) % 16;
        i64 c2 = (perm / 4096) % 16;
        i64 c3 = (perm / 256) % 16;
        i64 c4 = (perm / 16) % 16;
        i64 c5 = perm % 16;

        card[0][0][0] = c0 & 1;
        card[0][0][1] = spl(c0 & 2);
        card[0][0][2] = state = c0 >> 2;
        valid += (state < 3);

        card[0][1][0] = c1 & 1;
        card[0][1][1] = spl(c1 & 2);
        card[0][1][2] = state = c1 >> 2;
        valid += (state < 3);

        card[1][0][0] = c2 & 1;
        card[1][0][1] = spl(c2 & 2);
        card[1][0][2] = state = c2 >> 2;
        valid += (state < 3);

        card[1][1][0] = c3 & 1;
        card[1][1][1] = spl(c3 & 2);
        card[1][1][2] = state = c3 >> 2;
        valid += (state < 3);

        card[2][0][0] = c4 & 1;
        card[2][0][1] = spl(c4 & 2);
        card[2][0][2] = state = c4 >> 2;
        valid += (state < 3);

        card[2][1][0] = c5 & 1;
        card[2][1][1] = spl(c5 & 2);
        card[2][1][2] = state = c5 >> 2;
        valid += (state < 3);

        if (!valid) continue;

        auto vec = std::vector<i8>(1, 0);
        auto hashes = std::set<size_t>();

        state = 0;
        i8 in = 0;
        i64 pos = 0;
        size_t hash, idx = 0;

        do {
            if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = fullhash(vec, state, in, idx))) {
                state = -1;
                break;
            }
            else hashes.insert(hash);
            idx = index(pos);
            check(vec, idx);
            in = vec[idx];
            vec[idx] = static_cast<i8>(card[state][in][0]);
            pos += card[state][in][1];
            state = card[state][in][2];
        }       while (state < 3);

        if (state > 0) score = std::max(score, count(vec));

        int new_progress = static_cast<int>(100.0 * perm / PERMCOUNT);
        if (new_progress > progress) std::cout << "\r" << new_progress << "%";
        progress = new_progress;
    }

    std::cout << "\r100%\n\nScore: " << score << "\n";
}

void bb4() {
    std::cout << "This may take a very, very long time...\n0.00%";
    std::cout << std::fixed << std::setprecision(2);

    constexpr i64 PERMCOUNT = 25600000000;
    constexpr size_t VECLIMIT = 32;
    constexpr size_t SETLIMIT = 128;

    size_t score = 0;

    i64 perm = -1;
    i64 card[4][2][3];

    int progress = 0;

    while (++perm < 25600000000) {
        i64 valid = 0;
        i64 state;
        i64 c0 = perm / 1280000000;
        i64 c1 = (perm / 64000000) % 20;
        i64 c2 = (perm / 3200000) % 20;
        i64 c3 = (perm / 160000) % 20;
        i64 c4 = (perm / 8000) % 20;
        i64 c5 = (perm / 400) % 20;
        i64 c6 = (perm / 20) % 20;
        i64 c7 = perm % 20;

        card[0][0][0] = c0 & 1;
        card[0][0][1] = spl(c0 & 2);
        card[0][0][2] = state = c0 >> 2;
        valid += (state < 4);

        card[0][1][0] = c1 & 1;
        card[0][1][1] = spl(c1 & 2);
        card[0][1][2] = state = c1 >> 2;
        valid += (state < 4);

        card[1][0][0] = c2 & 1;
        card[1][0][1] = spl(c2 & 2);
        card[1][0][2] = state = c2 >> 2;
        valid += (state < 4);

        card[1][1][0] = c3 & 1;
        card[1][1][1] = spl(c3 & 2);
        card[1][1][2] = state = c3 >> 2;
        valid += (state < 4);

        card[2][0][0] = c4 & 1;
        card[2][0][1] = spl(c4 & 2);
        card[2][0][2] = state = c4 >> 2;
        valid += (state < 4);

        card[2][1][0] = c5 & 1;
        card[2][1][1] = spl(c5 & 2);
        card[2][1][2] = state = c5 >> 2;
        valid += (state < 4);

        card[3][0][0] = c6 & 1;
        card[3][0][1] = spl(c6 & 2);
        card[3][0][2] = state = c6 >> 2;
        valid += (state < 4);

        card[3][1][0] = c7 & 1;
        card[3][1][1] = spl(c7 & 2);
        card[3][1][2] = state = c7 >> 2;
        valid += (state < 4);

        if (!valid) continue;

        auto vec = std::vector<i8>(1, 0);
        auto hashes = std::set<size_t>();

        state = 0;
        i8 in = 0;
        i64 pos = 0;
        size_t hash, idx = 0;

        do {
            if (vec.size() > VECLIMIT || hashes.size() > SETLIMIT || contains(hashes, hash = fullhash(vec, state, in, idx))) {
                state = -1;
                break;
            }
            else hashes.insert(hash);
            idx = index(pos);
            check(vec, idx);
            in = vec[idx];
            vec[idx] = static_cast<i8>(card[state][in][0]);
            pos += card[state][in][1];
            state = card[state][in][2];
        }       while (state < 4);

        if (state > 0) score = std::max(score, count(vec));

        double percent = 100.0 * perm / PERMCOUNT;
        int new_progress = static_cast<int>(100.0 * percent);
        if (new_progress > progress) std::cout << "\r" << percent << "%";
        progress = new_progress;
    }

    std::cout << "\r100%\n\nScore: " << score << "\n";
}