// Pruebas de la reducción: la fórmula del tableau es satisfacible exactamente cuando la
// máquina acepta con una ejecución que cabe en el tableau, y de la asignación sale esa ejecución.
// Usa minisat; las fórmulas quedan en build/.
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "cook_levin.h"
#include "random_ntm.h"
#include "three_sat.h"

struct Totals {
    long formulas = 0;
    long satisfiable = 0;
};

// ¿Acepta N la cadena w con una ejecución que cabe en el tableau de t × t? A lo sumo t - 1
// pasos, y el cabezal dentro de las primeras t - 3 celdas (desde 0: hasta la t - 4).
static bool accepts_in_tableau(const Ntm& n, const std::string& w, std::size_t t) {
    bool by_levels = !accepting_branch(n, w, t - 1, t - 4).empty();
    bool by_branches = accepts_within(n, start_config(n, w), t - 1, t - 4);
    assert(by_levels == by_branches);
    return by_levels;
}

static void check_counts(const TableauFormula& formula, std::size_t t) {
    const Counts& got = formula.counts;
    Counts want = predicted_counts(static_cast<long>(t), got.symbols, got.legal);
    assert(got.cell_vars == want.cell_vars && got.window_vars == want.window_vars);
    assert(got.cell_clauses == want.cell_clauses && got.start_clauses == want.start_clauses);
    assert(got.move_clauses == want.move_clauses && got.accept_clauses == want.accept_clauses);
    assert(formula.cnf.num_vars == want.cell_vars + want.window_vars);
    long clauses = want.cell_clauses + want.start_clauses + want.move_clauses + want.accept_clauses;
    assert(static_cast<long>(formula.cnf.clauses.size()) == clauses);
}

// El teorema, con una máquina, una entrada y un lado.
static bool check(const Ntm& n, const std::string& w, std::size_t t, Totals& totals) {
    Cells cells = cells_of(n);
    TableauFormula formula = tableau_formula(n, w, t);
    check_counts(formula, t);
    Assignment model;
    bool sat = minisat_sat(formula.cnf, "build/test_cook_levin", &model);
    assert(sat == accepts_in_tableau(n, w, t));
    totals.formulas++;
    if (sat) {
        totals.satisfiable++;
        assert(satisfies(formula.cnf, model));
        Tableau table = decode_tableau(cells, t, model);
        assert(illegal_windows(legal_windows(n), table) == 0);
        int steps = accepting_steps(n, cells, table, w);
        assert(steps >= 0 && steps <= static_cast<int>(t) - 1);
    }
    return sat;
}

// La otra dirección, construida a mano: de una rama que acepta, una asignación que cumple la fórmula.
static void check_branch_gives_model(const Ntm& n, const std::string& w, std::size_t t) {
    Cells cells = cells_of(n);
    std::vector<Config> branch = accepting_branch(n, w, t - 1, t - 4);
    assert(!branch.empty());
    Tableau table = tableau_of(cells, branch, t);
    TableauFormula formula = tableau_formula(n, w, t);
    std::set<Window> legal = legal_windows(n);
    Assignment value(formula.cnf.num_vars + 1, false);
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            value[cell_var(t, cells.size(), i, j, table[i - 1][j - 1])] = true;
        }
    }
    // Las variables de ventana, en el orden en que add_move_clauses las crea.
    int z = static_cast<int>(formula.counts.cell_vars);
    for (std::size_t i = 1; i < t; i++) {
        for (std::size_t j = 1; j + 2 <= t; j++) {
            Window here = {table[i - 1][j - 1], table[i - 1][j], table[i - 1][j + 1],
                           table[i][j - 1], table[i][j], table[i][j + 1]};
            for (const Window& window : legal) {
                value[++z] = window == here;
            }
        }
    }
    assert(z == formula.cnf.num_vars);
    assert(satisfies(formula.cnf, value));
}

static std::vector<std::string> binary_strings(std::size_t max_length) {
    std::vector<std::string> all = {""};
    for (std::size_t first = 0; first < all.size(); first++) {
        if (all[first].size() < max_length) {
            all.push_back(all[first] + "0");
            all.push_back(all[first] + "1");
        }
    }
    return all;
}

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");
    Totals totals;

    // La numeración de las variables: x_{1,1,s} son las primeras |C|, y siguen por filas.
    assert(cell_var(7, 8, 1, 1, 0) == 1 && cell_var(7, 8, 1, 1, 7) == 8);
    assert(cell_var(7, 8, 1, 2, 3) == 12 && cell_var(7, 8, 2, 1, 0) == 57 && cell_var(7, 8, 7, 7, 7) == 392);

    // El ejemplo de los apuntes: contains_11 con 011. Acepta en 3 pasos y el cabezal llega
    // a la cuarta celda: hace falta t = 7. Con t = 6 la ejecución no cabe.
    assert(check(eleven, "011", 7, totals));
    assert(!check(eleven, "011", 6, totals));
    assert(!check(eleven, "010", 7, totals));
    check_branch_gives_model(eleven, "011", 7);
    check_branch_gives_model(back, "101", 7);
    check_branch_gives_model(left, "0", 5);

    // Las cuentas de los apuntes para contains_11, con t = 5, 10 y 20.
    {
        Counts c5 = predicted_counts(5, 8, 193);
        Counts c10 = predicted_counts(10, 8, 193);
        Counts c20 = predicted_counts(20, 8, 193);
        assert(c5.cell_vars + c5.window_vars == 2516);
        assert(c5.cell_clauses + c5.start_clauses + c5.move_clauses + c5.accept_clauses == 14639);
        assert(c10.cell_vars + c10.window_vars == 14696);
        assert(c10.cell_clauses + c10.start_clauses + c10.move_clauses + c10.accept_clauses == 86359);
        assert(c20.cell_vars + c20.window_vars == 69206);
        assert(c20.cell_clauses + c20.start_clauses + c20.move_clauses + c20.accept_clauses == 407999);
        check_counts(tableau_formula(eleven, "11", 5), 5);
        check_counts(tableau_formula(eleven, "11", 10), 10);
    }

    // Las máquinas de machines/ con cadenas cortas y varios lados.
    std::vector<std::string> inputs = binary_strings(2);
    inputs.insert(inputs.end(), {"011", "110", "101"});
    for (const std::string& w : inputs) {
        bool has_11 = w.find("11") != std::string::npos;
        bool has_01 = w.find("01") != std::string::npos;
        for (std::size_t t = w.size() + 3 > 4 ? w.size() + 3 : 4; t <= 7; t++) {
            // contains_11 acepta un paso después de leer el 11, con el cabezal una celda más allá:
            // si el 11 empieza en la celda k (desde 0), hace falta t >= k + 6.
            assert(check(eleven, w, t, totals) == (has_11 && t >= w.find("11") + 6));
            assert(check(left, w, t, totals) == (!w.empty() && w[0] == '0' && t >= 5));
            assert(!check(loop, w, t, totals));
        }
        check(back, w, w.size() + 3 > 4 ? w.size() + 3 : 4, totals);
        assert(check(back, w, 7, totals) == has_01);
    }
    // La máquina determinista de 0^n 1^n: con 01 acepta en 5 pasos y el cabezal llega a la
    // cuarta celda, así que hace falta t = 7.
    assert(!check(zeros, "01", 6, totals));
    assert(check(zeros, "01", 7, totals));
    assert(check(zeros, "", 5, totals) && !check(zeros, "", 4, totals));
    assert(!check(zeros, "10", 7, totals));

    // Máquinas al azar: la fórmula y el recorrido del árbol de ejecuciones siempre coinciden.
    std::mt19937 rng(2013);
    int random_sat = 0, random_unsat = 0;
    for (int k = 0; k < 36; k++) {
        Ntm n = random_ntm(rng, 1 + k % 3);
        for (const std::string& w : {std::string(""), std::string("1"), std::string("01"), std::string("110")}) {
            std::size_t t = w.size() + 3 + static_cast<std::size_t>(rng() % 3);
            (check(n, w, t < 4 ? 4 : t, totals) ? random_sat : random_unsat)++;
        }
    }
    assert(totals.satisfiable > 40 && totals.formulas - totals.satisfiable > 40);
    assert(random_sat > 10 && random_unsat > 10);  // hay de los dos tipos

    // Pasar la fórmula del tableau a 3-SAT no cambia la respuesta.
    for (std::size_t t : {6u, 7u}) {
        Cnf three = to_three_sat(tableau_formula(eleven, "011", t).cnf);
        assert(is_three_sat(three));
        assert(minisat_sat(three, "build/test_cook_levin") == (t == 7));
    }

    std::cout << "test_cook_levin: ok (" << totals.formulas << " fórmulas, " << totals.satisfiable
              << " satisfacibles)\n";
    return 0;
}
