/* Jonathan Frech, 2021-11-22, -27 */
// c++ -std=c++20 -Wall -Wextra -Wpedantic -Wswitch-enum -Werror -O3 fgol-traj.cpp -o fgol-traj

#include <array>
#include <bit>
#include <cstdint>
#include <optional>
#include <cstdlib>
#include <iostream>
#include <random>
#include <set>

using world_t = uint64_t;


world_t gol_step(const world_t w) {
    uint64_t v{0};

    constexpr std::array<world_t, 64> neighbourhood_masks{[](){
        std::array<world_t, 64> masks{};
        for (int j{0}; j < 64; ++j) {
            masks[j] = 0;
            int Y{j/8}, X{j%8};
            for (int dy{-1}; dy <= 1; ++dy) {
                for (int dx{-1}; dx <= 1; ++dx) {
                    if (dy == 0 && dx == 0)
                        continue;
                    int y{(Y+dy+8) % 8}, x{(X+dx+8) % 8};
                    masks[j] |= 1ULL << (y*8+x);
                }
            }
        }
        return masks;
    }()};

    for (int j{0}; j < 64; ++j) {
        const int pc{std::popcount(w & neighbourhood_masks[j])};
        if (pc == 3 || (w & (1ULL << j) && pc == 2))
            v |= 1ULL << j;
    }

    return v;
}

std::string encode_world(const world_t w) {
    std::string hex{};
    for (int j{15}; j >= 0; --j) {
        hex += "0123456789abcdef"[(w >> (4*j)) & 0xf];
    }
    return hex;
}

void find_records() {
    std::mt19937_64 rng{std::random_device{}()};
    std::uniform_int_distribution<unsigned short> byte_dis{0, 0xff};

    auto random_world{[&]() {
        world_t w{};
        for (size_t j{0}; j < 8; ++j) {
            w |= static_cast<world_t>(byte_dis(rng)) << (8*j);
        }
        return w;
    }};

    uint64_t record_t{0};

    for (;;) {
        const world_t w0{random_world()};

        std::set<world_t> seen{};
        world_t w{w0};
        uint64_t t{0};
        do {
            ++t;
            seen.insert(w);
            w = gol_step(w);
        } while (!seen.contains(w));

        if (t >= record_t) {
            record_t = t;
            std::cout << "t(" << encode_world(w0) << ") = " << t << "\n" << std::flush;
        }
    }
}

void print(const world_t w) {
    for (int y{0}; y < 8; ++y) {
        for (int x{0}; x < 8; ++x)
            std::cout << (w & (1ULL << (y*8+x)) ? "[]" : "  ");
        std::cout << '\n';
    }
    std::cout << '\n';
}

void stats(const world_t w0) {
    std::cout << "world " << encode_world(w0) << ":\n";
    print(w0);

    std::set<world_t> seen{};
    world_t w{w0};
    uint64_t t{0};
    do {
        ++t;
        seen.insert(w);
        w = gol_step(w);
    } while (!seen.contains(w));
    const world_t first_point_of_periodicity{w};

    std::cout << "trajectory length until first self-colision: " << t << "\n";

    uint64_t periodicity{0};
    w = first_point_of_periodicity;
    do {
        w = gol_step(w);
        ++periodicity;
    } while (w != first_point_of_periodicity);

    std::cout << "periodicity: " << periodicity << "\n";
    std::cout << "first point of periodicity: " << encode_world(first_point_of_periodicity);
    if (w0 == first_point_of_periodicity)
        std::cout << " (this world is recurrent)\n";
    else
        std::cout << "\n";
}

std::optional<world_t> decode_world(std::string const&hex) {
    world_t w{0};
    if (hex.size() != 16)
        return std::nullopt;

    for (int j{15}; j >= 0; --j) {
        const char c{hex[15-j]};
        if ('0' <= c && c <= '9')
            w |= (static_cast<world_t>(c - '0') & 0xf) << (4*j);
        else if ('a' <= c && c <= 'f')
            w |= (static_cast<world_t>(10 + c - 'a') & 0xf) << (4*j);
        else
            return std::nullopt;
    }

    return std::make_optional(w);
}


int main(int argc, char **argv) {
    std::vector<std::string> args(argc);
    for (int j{0}; j < argc; ++j)
        args[j] = argv[j];
    std::string program_name{args.size() > 0 ? args[0] : ""};

    if (args.size() == 1) {
        return find_records(), /* this function cannot exit */ EXIT_FAILURE;
    } else if (args.size() == 2) {
        std::optional<world_t> ow{decode_world(args[1])};
        if (!ow.has_value()) {
            std::cerr << "invalid world: " << args[1] << "\n";
            goto usage;
        }
        stats(ow.value());
        return EXIT_SUCCESS;
    }

    usage: return std::cerr << "usage: " << program_name << "\n       "
        << program_name << "world\n" << std::flush, EXIT_FAILURE;
}