// Pruebas de la reducción del juego de la fórmula a la geografía generalizada: el primer
// jugador gana en el grafo exactamente cuando la fórmula es verdadera.
#include <cassert>
#include <cstdio>
#include <random>
#include <set>
#include <string>

#include "formula_game.h"
#include "geography.h"

static std::size_t literal_count(const Qbf& f) {
    std::size_t total = 0;
    for (const std::vector<int>& clause : f.clauses) {
        total += clause.size();
    }
    return total;
}

static void check(const Qbf& f) {
    Qbf game = normalize_for_game(f);
    assert(has_game_form(game));
    assert(is_true(game) == is_true(f));  // las variables nuevas no cambian el valor
    assert(game.variables.size() <= 2 * f.variables.size() + 1);
    Graph g = geography_from_formula(game);
    // Tamaño: cuatro nodos por variable, uno para la matriz, uno por cláusula y uno por literal.
    assert(g.nodes.size() == 4 * game.variables.size() + 1 + game.clauses.size() + literal_count(game));
    assert(std::set<std::string>(g.nodes.begin(), g.nodes.end()).size() == g.nodes.size());
    assert(first_player_wins(g) == is_true(f));
}

int main() {
    // Las dos fórmulas de la clase.
    Qbf forall_exists = load_qbf("machines/forall_exists.qbf");
    Qbf exists_forall = load_qbf("machines/exists_forall.qbf");
    assert(!has_game_form(forall_exists) && !has_game_form(exists_forall));
    assert(to_text(normalize_for_game(forall_exists)) == "∃d1 ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y))");
    assert(to_text(normalize_for_game(exists_forall)) == "∃y ∀x ∃d1 ((x ∨ y) ∧ (¬x ∨ ¬y))");
    Graph g1 = geography_from_formula(normalize_for_game(forall_exists));
    Graph g2 = geography_from_formula(normalize_for_game(exists_forall));
    assert(g1.nodes.size() == 19 && g2.nodes.size() == 19);
    assert(edge_count(g1) == 25);
    assert(first_player_wins(g1));
    assert(!first_player_wins(g2));

    // El juego de tres jugadas ya tiene la forma pedida.
    Qbf three = load_qbf("machines/three_moves.qbf");
    assert(has_game_form(three));
    Graph g3 = geography_from_formula(three);
    assert(g3.nodes.size() == 23);
    assert(first_player_wins(g3) && is_true(three));

    check(load_qbf("machines/sat_example.qbf"));
    check(load_qbf("machines/unsat_example.qbf"));
    check(Qbf{});  // sin variables ni cláusulas: verdadera

    // Fórmulas al azar con hasta 5 variables y hasta 5 cláusulas.
    std::mt19937 rng(2014);
    const int total = 1500;
    int trues = 0;
    for (int k = 0; k < total; k++) {
        Qbf f;
        int m = 1 + static_cast<int>(rng() % 5);
        for (int i = 0; i < m; i++) {
            f.variables.push_back("x" + std::to_string(i + 1));
            f.quantifiers.push_back(rng() % 2 == 0 ? 'E' : 'A');
        }
        int clauses = static_cast<int>(rng() % 6);
        for (int j = 0; j < clauses; j++) {
            std::vector<int> clause;
            int size = 1 + static_cast<int>(rng() % 3);
            for (int l = 0; l < size; l++) {
                int variable = 1 + static_cast<int>(rng() % m);
                clause.push_back(rng() % 2 == 0 ? variable : -variable);
            }
            f.clauses.push_back(clause);
        }
        check(f);
        trues += is_true(f);
    }
    assert(trues > total / 10 && trues < total - total / 10);
    std::printf("test_formula_game: las fórmulas de la clase y %d fórmulas al azar (%d verdaderas)\n", total, trues);
    return 0;
}
