// Pruebas de la reducción de 3-SAT a HAMPATH: el tamaño del grafo, la dirección que se
// demuestra (de una asignación sale un camino) y, con fórmulas chicas, las dos direcciones.
#include <cassert>
#include <fstream>
#include <iostream>
#include <random>

#include "hampath.h"

static Cnf read_file(const std::string& path) {
    std::ifstream in(path);
    assert(in);
    return read_dimacs(in);
}

// Comprueba la reducción con una fórmula: todas sus asignaciones y la búsqueda.
static bool check(const Cnf& f, bool also_pure) {
    HamInstance h = build_hampath(f);
    int l = f.num_vars;
    int k = static_cast<int>(f.clauses.size());
    assert(h.graph.size() == (l + 1) + l * (3 * k + 3) + k);  // puntas, filas con sus extremos, cláusulas

    // De cada asignación que cumple la fórmula sale un camino hamiltoniano.
    bool satisfiable = false;
    Assignment value(l + 1, false);
    for (unsigned long mask = 0; mask < (1ul << l); mask++) {
        for (int i = 1; i <= l; i++) {
            value[i] = (mask >> (i - 1)) & 1;
        }
        if (satisfies(f, value)) {
            satisfiable = true;
            std::vector<int> path = path_from_assignment(h, f, value);
            assert(is_hamiltonian_path(h, path));
            assert(assignment_from_path(h, path) == value);
        }
    }
    // La búsqueda encuentra un camino exactamente cuando la fórmula es satisfacible, y del
    // camino se lee una asignación que la cumple.
    HamSearch search(h, true);
    bool found = search.run();
    assert(found == satisfiable);
    if (found) {
        assert(is_hamiltonian_path(h, search.path));
        assert(satisfies(f, assignment_from_path(h, search.path)));
    }
    if (also_pure) {
        HamSearch pure(h, false);
        assert(pure.run() == satisfiable);  // la fuerza bruta sin podas dice lo mismo
    }
    return satisfiable;
}

int main() {
    // Los ejemplos de los apuntes.
    Cnf two = read_file("formulas/two_clauses.cnf");
    HamInstance h = build_hampath(two);
    assert(h.graph.size() == 33 && h.graph.edges.size() == 72);
    assert(check(two, false));
    Cnf eight = read_file("formulas/all_eight.cnf");
    assert(build_hampath(eight).graph.size() == 93 && build_hampath(eight).graph.edges.size() == 216);
    assert(!check(eight, false));

    // Fórmulas muy chicas: también con la fuerza bruta sin podas.
    std::mt19937 rng(7);
    int sat_count = 0, total = 0;
    for (int round = 0; round < 60; round++) {
        Cnf f;
        f.num_vars = 1 + static_cast<int>(rng() % 2);
        int clauses = 1 + static_cast<int>(rng() % 2);
        for (int c = 0; c < clauses; c++) {
            Clause clause;
            int size = 1 + static_cast<int>(rng() % 3);
            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);
        }
        sat_count += check(f, true);
        total++;
    }
    // Fórmulas un poco más grandes, con cláusulas de 1 a 3 literales para que varias no se puedan cumplir.
    for (int round = 0; round < 150; round++) {
        Cnf f;
        f.num_vars = 2 + static_cast<int>(rng() % 2);
        int clauses = 3 + static_cast<int>(rng() % 5);
        for (int c = 0; c < clauses; c++) {
            Clause clause;
            int size = 1 + static_cast<int>(rng() % 2) + static_cast<int>(rng() % 2);
            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);
        }
        sat_count += check(f, false);
        total++;
    }
    assert(sat_count > 40 && total - sat_count > 40);

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