// Cuenta los pasos de las tres máquinas que deciden { 0^k 1^k : k ≥ 0 }:
// la cuadrática y la de n log n, de una cinta (machines/*.tm), y la lineal de dos cintas.
// Primero el peor caso sobre todas las entradas de cada longitud, que es la definición de
// tiempo; después solo las entradas 0^k 1^k, para longitudes grandes.
#include <cmath>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>

#include "multitape.h"
#include "tm.h"

int main() {
    try {
        Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
        Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
        MultitapeTm linear = two_tape_zeros_ones();
        const long long limit = 1000000000;

        std::cout << "Peor caso sobre las 2^n entradas de longitud n: pasos, y la primera entrada que los alcanza\n";
        std::cout << " n   cuadrática            n log n               dos cintas\n";
        for (std::size_t n = 0; n <= 12; n++) {
            long long worst_q = -1, worst_l = -1, worst_t = -1;
            std::string input_q, input_l, input_t;
            for (const std::string& w : binary_strings(n)) {
                long long q = run_tm(quadratic, w, limit).steps;
                long long l = run_tm(nlogn, w, limit).steps;
                long long t = run_multitape(linear, w).steps;
                if (q > worst_q) {
                    worst_q = q;
                    input_q = w;
                }
                if (l > worst_l) {
                    worst_l = l;
                    input_l = w;
                }
                if (t > worst_t) {
                    worst_t = t;
                    input_t = w;
                }
            }
            // La columna tiene 16 caracteres; ε ocupa uno en pantalla y dos bytes en el std::string.
            auto show = [](long long steps, const std::string& w) {
                std::cout << std::setw(5) << steps << "  " << (w.empty() ? "ε" : w)
                          << std::string(15 - (w.empty() ? 1 : w.size()), ' ');
            };
            std::cout << std::setw(2) << n;
            show(worst_q, input_q);
            show(worst_l, input_l);
            show(worst_t, input_t);
            std::cout << '\n';
        }

        std::cout << "\nPasos con la entrada 0^k 1^k, de longitud n = 2k\n";
        std::cout << "    n   cuadrática   pasos/n²    n log n   pasos/(n·log₂ n)   dos cintas\n";
        for (std::size_t n = 16; n <= 8192; n *= 2) {
            std::string w = zeros_ones(n / 2);
            TmResult q = run_tm(quadratic, w, limit);
            TmResult l = run_tm(nlogn, w, limit);
            MultitapeResult t = run_multitape(linear, w);
            if (!q.accepted || !l.accepted || !t.accepted) {
                throw std::runtime_error("una máquina no aceptó 0^k 1^k");
            }
            double size = static_cast<double>(n);
            std::cout << std::setw(5) << n << std::setw(13) << q.steps << std::fixed << std::setprecision(3)
                      << std::setw(11) << static_cast<double>(q.steps) / (size * size) << std::setw(11) << l.steps
                      << std::setw(19) << static_cast<double>(l.steps) / (size * std::log2(size)) << std::setw(13)
                      << t.steps << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
