// Pruebas de las ventanas legales y del lema de las ventanas.
#include <cassert>
#include <functional>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "random_ntm.h"
#include "tableau.h"

// Todas las filas de abajo que dejan legales las t - 2 ventanas sobre la fila `top`.
// Va celda por celda y corta en cuanto una ventana completa es ilegal.
static std::set<Row> rows_below(const std::set<Window>& legal, const Cells& cells, const Row& top) {
    std::set<Row> found;
    Row bottom;
    std::function<void()> extend = [&]() {
        std::size_t j = bottom.size();
        if (j >= 3) {
            Window w = {top[j - 3], top[j - 2], top[j - 1], bottom[j - 3], bottom[j - 2], bottom[j - 1]};
            if (legal.count(w) == 0) {
                return;
            }
        }
        if (j == top.size()) {
            found.insert(bottom);
            return;
        }
        for (int s = 0; s < cells.size(); s++) {
            bottom.push_back(s);
            extend();
            bottom.pop_back();
        }
    };
    extend();
    return found;
}

// Lo que dice el lema: las filas que pueden ir debajo de # C # son exactamente las
// configuraciones que siguen a C en un paso y caben, más C misma si C acepta.
static std::set<Row> rows_by_steps(const Ntm& n, const Cells& cells, const Config& c, std::size_t t) {
    std::set<Row> expected;
    for (const Config& d : successors(n, c)) {
        if (fits(d, t)) {
            expected.insert(row_of(cells, d, t));
        }
    }
    if (c.state == n.accept) {
        expected.insert(row_of(cells, c, t));
    }
    return expected;
}

// Comprueba el lema con todas las configuraciones de N que caben en una fila de t celdas.
static long check_lemma(const Ntm& n, std::size_t t) {
    Cells cells = cells_of(n);
    std::set<Window> legal = legal_windows(n);
    long rows = 0;
    std::size_t tape_cells = t - 3;
    std::vector<std::size_t> digits(tape_cells, 0);
    bool more = true;
    while (more) {
        std::string tape;
        for (std::size_t d : digits) {
            tape.push_back(n.tape[d]);
        }
        for (const std::string& q : n.states) {
            for (std::size_t head = 0; head < tape_cells; head++) {
                Config c = {q, tape, head};
                normalize(c);
                Row top = row_of(cells, c, t);
                assert(rows_below(legal, cells, top) == rows_by_steps(n, cells, c, t));
                rows++;
            }
        }
        std::size_t k = 0;
        while (k < tape_cells && ++digits[k] == n.tape.size()) {
            digits[k++] = 0;
        }
        more = k < tape_cells;
    }
    return rows;
}

// Las propiedades de las ventanas que usa la demostración del lema.
static void check_properties(const Ntm& n) {
    Cells cells = cells_of(n);
    int border = cells.border();
    for (const Window& w : legal_windows(n)) {
        bool state_above = cells.is_state(w[0]) || cells.is_state(w[1]) || cells.is_state(w[2]);
        if (!state_above) {
            assert(w[4] == w[1]);  // sin estado arriba, el centro se copia
        }
        assert((w[0] == border) == (w[3] == border));  // las # quedan donde están
        assert((w[2] == border) == (w[5] == border));
        assert(w[1] != border && w[4] != border);
        assert(!(cells.is_state(w[1]) && w[2] == border));  // ningún estado pegado a la # derecha
        assert(!(cells.is_state(w[4]) && w[5] == border));
        int states_above = cells.is_state(w[0]) + cells.is_state(w[1]) + cells.is_state(w[2]);
        int states_below = cells.is_state(w[3]) + cells.is_state(w[4]) + cells.is_state(w[5]);
        assert(states_above <= 1 && states_below <= 1);
    }
}

int main() {
    Ntm eleven = read_ntm_file("machines/contains_11.tm");
    Ntm back = read_ntm_file("machines/contains_01_back.tm");
    Ntm left = read_ntm_file("machines/left_end_accept.tm");
    Ntm loop = read_ntm_file("machines/loop.tm");
    Ntm zeros = read_ntm_file("machines/zeros_ones.tm");
    Cells cells = cells_of(eleven);

    // El alfabeto de las celdas de contains_11: Γ, después Q, después #.
    assert((cells.names == std::vector<std::string>{"0", "1", "_", "q0", "q1", "q_accept", "q_reject", "#"}));
    assert(cells.size() == 8);

    // Las cantidades que citan los apuntes.
    assert(legal_windows(eleven).size() == 193);
    assert(legal_windows(back).size() == 453);
    assert(legal_windows(left).size() == 355);
    assert(legal_windows(loop).size() == 189);
    assert(legal_windows(zeros).size() == 1109);

    // Las cuatro formas dan exactamente las ventanas que aparecen en pasos de verdad.
    // Filas de hasta 7 celdas entre las # alcanzan para verlas todas: con 6 ya no aparecen nuevas.
    for (const Ntm* n : {&eleven, &loop}) {
        std::set<Window> seen = windows_from_steps(*n, 7);
        assert(legal_windows(*n) == seen);
        assert(windows_from_steps(*n, 6) == seen);
        check_properties(*n);
    }
    for (const Ntm* n : {&back, &left}) {
        assert(legal_windows(*n) == windows_from_steps(*n, 6));
        check_properties(*n);
    }
    assert(legal_windows(zeros) == windows_from_steps(zeros, 6));
    check_properties(zeros);

    // Las ventanas de ejemplo de los apuntes, con contains_11.
    std::set<Window> legal = legal_windows(eleven);
    auto window = [&cells](const std::vector<std::string>& names) {
        Window w;
        for (std::size_t k = 0; k < 6; k++) {
            w[k] = cells.index(names[k]);
        }
        return w;
    };
    assert(legal.count(window({"0", "q0", "1", "0", "1", "q1"})) == 1);   // adivina: pasa a q1
    assert(legal.count(window({"0", "q0", "1", "0", "1", "q0"})) == 1);   // sigue de largo
    assert(legal.count(window({"0", "q0", "1", "0", "0", "q0"})) == 0);   // escribe lo que no debe
    assert(legal.count(window({"0", "q0", "1", "q0", "0", "1"})) == 0);   // se mueve a la izquierda
    assert(legal.count(window({"0", "1", "1", "0", "1", "1"})) == 1);     // lejos del cabezal: se copia
    assert(legal.count(window({"0", "1", "1", "0", "0", "1"})) == 0);     // cambia una celda sin cabezal
    assert(legal.count(window({"1", "q1", "0", "1", "1", "q0"})) == 0);   // δ(q1, 0) no tiene movimientos
    assert(legal.count(window({"1", "q_accept", "_", "1", "q_accept", "_"})) == 1);  // ya aceptó: se repite
    assert(legal.count(window({"q0", "1", "#", "1", "q0", "#"})) == 0);   // no queda celda para leer
    // L en la primera celda, con left_end_accept.
    Cells left_cells = cells_of(left);
    std::set<Window> left_legal = legal_windows(left);
    Window stay = {left_cells.border(), left_cells.index("q0"), left_cells.index("0"),
                   left_cells.border(), left_cells.index("q1"), left_cells.index("X")};
    assert(left_legal.count(stay) == 1);

    // Las filas: # u q v #.
    Row first = row_of(cells, start_config(eleven, "011"), 7);
    assert(show_row(cells, first) == "# q0 0 1 1 _ #");
    assert(is_config_row(cells, first));
    assert(config_of(cells, first) == start_config(eleven, "011"));
    assert(!fits(start_config(eleven, "011"), 5) && fits(start_config(eleven, "011"), 6));
    assert(fits(start_config(eleven, ""), 4) && !fits(start_config(eleven, ""), 3));

    // El tableau de una rama: sin ventanas ilegales, y es una ejecución que acepta.
    std::vector<Config> branch = accepting_branch(eleven, "011", 6, 3);
    assert(branch.size() == 4);
    Tableau table = tableau_of(cells, branch, 7);
    assert(illegal_windows(legal, table) == 0);
    assert(first_row_is_start(eleven, cells, table, "011") && has_accept(eleven, cells, table));
    assert(accepting_steps(eleven, cells, table, "011") == 3);
    // Un solo símbolo cambiado lejos del cabezal ya deja ventanas ilegales.
    Tableau broken = table;
    broken[2][1] = cells.index("1");
    assert(illegal_windows(legal, broken) > 0);
    assert(accepting_steps(eleven, cells, broken, "011") == -1);

    // El lema de las ventanas, con todas las configuraciones que caben en filas de 4 a 6 celdas.
    long rows = 0;
    for (std::size_t t = 4; t <= 6; t++) {
        for (const Ntm* n : {&eleven, &back, &left, &loop}) {
            rows += check_lemma(*n, t);
        }
    }
    rows += check_lemma(zeros, 5);
    // Y con máquinas al azar.
    std::mt19937 rng(13);
    for (int k = 0; k < 30; k++) {
        Ntm n = random_ntm(rng, 1 + k % 3);
        assert(legal_windows(n) == windows_from_steps(n, 6));
        check_properties(n);
        rows += check_lemma(n, 4) + check_lemma(n, 5);
    }

    std::cout << "test_tableau: ok (el lema de las ventanas con " << rows << " filas)\n";
    return 0;
}
