// Pruebas de la reducción de SAT a 3-SAT: la forma de la salida, los tamaños y que la
// respuesta se conserva, con fuerza bruta y con minisat.
#include <cassert>
#include <iostream>
#include <random>

#include "three_sat.h"

int main() {
    // La cláusula de cinco literales de la pregunta de repaso: 2 variables nuevas, 3 cláusulas.
    Cnf five;
    five.num_vars = 5;
    five.add({1, 2, 3, 4, 5});
    Cnf out = to_three_sat(five);
    assert(out.num_vars == 7);
    assert((out.clauses == std::vector<Clause>{{1, 2, 6}, {-6, 3, 7}, {-7, 4, 5}}));
    assert(is_three_sat(out));

    // Una cláusula de k >= 4 literales distintos: k - 3 variables nuevas y k - 2 cláusulas.
    for (int k = 4; k <= 30; k++) {
        Cnf f;
        f.num_vars = k;
        Clause all;
        for (int v = 1; v <= k; v++) {
            all.push_back(v % 2 == 0 ? -v : v);
        }
        f.add(all);
        Cnf g = to_three_sat(f);
        assert(g.num_vars == k + (k - 3) && static_cast<int>(g.clauses.size()) == k - 2);
        assert(is_three_sat(g));
    }

    // Las cláusulas cortas: 0, 1 y 2 literales dan 8, 4 y 2 cláusulas.
    for (int k = 0; k <= 2; k++) {
        Cnf f;
        f.num_vars = 2;
        Clause c;
        for (int v = 1; v <= k; v++) {
            c.push_back(v);
        }
        f.add(c);
        Cnf g = to_three_sat(f);
        assert(static_cast<int>(g.clauses.size()) == (k == 0 ? 8 : k == 1 ? 4 : 2));
        assert(g.num_vars == 2 + 3 - k);
        assert(is_three_sat(g));
        assert(brute_force_sat(f) == brute_force_sat(g));
    }

    // Literales repetidos y cláusulas que siempre se cumplen.
    Cnf odd;
    odd.num_vars = 2;
    odd.add({1, 1, -2, 1});
    odd.add({1, -1, 2});
    Cnf cleaned = to_three_sat(odd);
    assert(cleaned.clauses.size() == 2 && cleaned.num_vars == 3);

    // No es equivalente: la salida tiene asignaciones de las variables viejas que la cumplen
    // solo con ciertos valores de las nuevas. Con (x1 ∨ ... ∨ x5) y solo x5 verdadera, hace
    // falta y1 = y2 = verdadero.
    Assignment value = {false, false, false, false, false, true, true, true};
    assert(satisfies(out, value));
    value[6] = false;
    assert(!satisfies(out, value));

    // Fórmulas al azar con cláusulas de 0 a 7 literales: la respuesta se conserva.
    std::mt19937 rng(3);
    int sat_count = 0, total = 400;
    for (int round = 0; round < total; round++) {
        Cnf f;
        f.num_vars = 3 + static_cast<int>(rng() % 4);
        int clauses = 1 + static_cast<int>(rng() % 9);
        for (int c = 0; c < clauses; c++) {
            unsigned roll = rng() % 20;
            int size = roll == 0 ? 0 : 1 + static_cast<int>(rng() % 7);
            Clause clause;
            for (int k = 0; k < size; k++) {
                int v = 1 + static_cast<int>(rng() % static_cast<unsigned>(f.num_vars));
                clause.push_back(rng() % 2 == 0 ? v : -v);
            }
            f.add(clause);
        }
        Cnf g = to_three_sat(f);
        assert(is_three_sat(g));
        bool expected = brute_force_sat(f);
        sat_count += expected;
        if (g.num_vars <= 16) {
            assert(brute_force_sat(g) == expected);
        }
        Assignment model;
        assert(minisat_sat(g, "build/test_three_sat", &model) == expected);
        if (expected) {
            // La asignación de la salida, recortada a las variables viejas, cumple la entrada.
            assert(satisfies(g, model));
            assert(satisfies(f, model));
        }
    }
    assert(sat_count > 50 && total - sat_count > 50);

    std::cout << "test_three_sat: ok (" << total << " fórmulas al azar, " << sat_count << " satisfacibles)\n";
    return 0;
}
