// Pruebas de lo que los apuntes afirman sobre las tres máquinas de { 0^k 1^k } (sesión A):
// que deciden el lenguaje, y cuántos pasos dan.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

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

static const long long kLimit = 1000000000;

// ⌊log2 n⌋, para n ≥ 1.
static long long floor_log2(std::size_t n) {
    long long result = 0;
    while (n > 1) {
        n /= 2;
        result++;
    }
    return result;
}

// Las tres máquinas deciden el lenguaje: se comparan con in_zeros_ones en todas las cadenas
// de longitud a lo sumo 12, y se comprueba el peor caso de cada longitud.
static std::size_t test_decide_and_worst_case() {
    Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
    Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
    MultitapeTm linear = two_tape_zeros_ones();
    std::size_t total = 0;
    for (std::size_t n = 0; n <= 12; n++) {
        long long worst_q = 0, worst_l = 0, worst_t = 0;
        for (const std::string& w : binary_strings(n)) {
            TmResult q = run_tm(quadratic, w, kLimit);
            TmResult l = run_tm(nlogn, w, kLimit);
            MultitapeResult t = run_multitape(linear, w);
            assert(q.halted && l.halted);
            assert(q.accepted == in_zeros_ones(w));
            assert(l.accepted == in_zeros_ones(w));
            assert(t.accepted == in_zeros_ones(w));
            worst_q = q.steps > worst_q ? q.steps : worst_q;
            worst_l = l.steps > worst_l ? l.steps : worst_l;
            worst_t = t.steps > worst_t ? t.steps : worst_t;
            // La cota de la demostración: a lo sumo ⌊log2 n⌋ + 2 pasadas de 2n + 1 pasos.
            if (n >= 1) {
                assert(l.steps <= (2 * static_cast<long long>(n) + 1) * (floor_log2(n) + 2));
            }
            // Con longitud impar, la máquina de n log n rechaza en la primera pasada.
            if (n % 2 == 1) {
                assert(!l.accepted && l.steps <= static_cast<long long>(n) + 1);
            }
            // La de dos cintas nunca pasa de n + 3 pasos, ni usa más de n + 2 celdas por cinta.
            assert(t.steps <= static_cast<long long>(n) + 3);
            assert(t.cells <= n + 2);
            total++;
        }
        long long m = static_cast<long long>(n);
        // Peor caso de la cuadrática: ⌈(n + 1)² / 2⌉.
        assert(worst_q == ((m + 1) * (m + 1) + 1) / 2);
        // Peor caso de la de n log n con n par: el de 0^k 1^k.
        if (n >= 2 && n % 2 == 0) {
            assert(worst_l == 2 * m * floor_log2(n) + m + 1);
        }
        if (n >= 2) {
            assert(worst_t == m + 3);
        }
    }
    return total;
}

// Las fórmulas exactas con la entrada 0^k 1^k, y los números de la tabla de los apuntes.
static void test_step_formulas() {
    Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
    Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
    MultitapeTm linear = two_tape_zeros_ones();
    for (std::size_t k = 0; k <= 300; k++) {
        long long kk = static_cast<long long>(k);
        assert(run_tm(quadratic, zeros_ones(k), kLimit).steps == 2 * kk * kk + 2 * kk + 1);
    }
    for (std::size_t k = 1; k <= 300; k++) {
        std::size_t n = 2 * k;
        long long m = static_cast<long long>(n);
        TmResult r = run_tm(nlogn, zeros_ones(k), kLimit, "back");
        assert(r.accepted);
        assert(r.steps == 2 * m * floor_log2(n) + m + 1);
        // Una vuelta al borde izquierdo por cada pasada que tacha: ⌊log2 k⌋ + 1.
        assert(static_cast<long long>(r.watched.size()) == floor_log2(k) + 1);
        assert(run_multitape(linear, zeros_ones(k)).steps == m + 3);
    }

    struct Row {
        std::size_t n;
        long long quadratic;
        long long nlogn;
        long long linear;
    };
    std::vector<Row> table = {
        {16, 145, 145, 19},        {32, 545, 353, 35},         {64, 2113, 833, 67},
        {128, 8321, 1921, 131},    {256, 33025, 4353, 259},    {512, 131585, 9729, 515},
        {1024, 525313, 21505, 1027}, {2048, 2099201, 47105, 2051}, {4096, 8392705, 102401, 4099},
        {8192, 33562625, 221185, 8195},
    };
    for (const Row& row : table) {
        std::string w = zeros_ones(row.n / 2);
        assert(run_tm(quadratic, w, kLimit).steps == row.quadratic);
        assert(run_tm(nlogn, w, kLimit).steps == row.nlogn);
        assert(run_multitape(linear, w).steps == row.linear);
    }
}

// Las ejecuciones que los apuntes copian.
static void test_quoted_runs() {
    Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
    Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
    assert(run_tm(quadratic, "0011", kLimit).steps == 13);
    assert(run_tm(quadratic, "0011", kLimit, "*").watched.size() == 14);
    assert(run_tm(quadratic, "00011", kLimit).steps == 18);

    TmResult r = run_tm(nlogn, "0000011111", kLimit, "n");
    assert(r.accepted && r.steps == 71);
    assert(r.watched.size() == 3);
    assert(r.watched[0].left == "S" && r.watched[0].right == "0X0XX1X1X");
    assert(r.watched[1].left == "S" && r.watched[1].right == "XX0XXXX1X");
    assert(r.watched[2].left == "S" && r.watched[2].right == "XXXXXXXXX");

    // Cinco ceros y tres unos: misma paridad en la primera pasada, distinta en la segunda.
    TmResult different = run_tm(nlogn, "00000111", kLimit, "n");
    assert(!different.accepted && different.watched.size() == 1);
    assert(run_tm(nlogn, "0001111", kLimit).steps == 8);
    assert(!run_tm(nlogn, "0101", kLimit).accepted);

    // El intento de una sola pasada no decide el lenguaje: acepta 001.
    Tm one_pass = load_tm("errors/zeros_ones_one_pass.tm");
    TmResult wrong = run_tm(one_pass, "001", kLimit);
    assert(wrong.accepted && !in_zeros_ones("001") && wrong.steps == 4);
}

int main() {
    std::size_t strings = test_decide_and_worst_case();
    test_step_formulas();
    test_quoted_runs();
    std::printf("test_time: ok (3 máquinas, %zu cadenas cada una)\n", strings);
}
