// Pruebas de los verificadores (sesión B). Para cada problema se comprueban los certificados
// de los apuntes y, en instancias pequeñas, la definición de NP: la instancia está en el
// lenguaje si y solo si el verificador acepta algún certificado.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <numeric>
#include <optional>
#include <random>
#include <utility>
#include <vector>

#include "examples.h"
#include "search.h"
#include "verifiers.h"

// ¿Hay un camino hamiltoniano de s a t? Decidido sin el verificador, con una tabla:
// reach[S][v] dice si hay un camino que empieza en s, visita exactamente los vértices de S
// y termina en v.
static bool has_hampath(const Graph& g, int s, int t) {
    std::size_t n = static_cast<std::size_t>(g.n);
    std::vector<std::vector<bool>> arc(n, std::vector<bool>(n, false));
    for (const auto& [u, v] : g.edges) {
        arc[static_cast<std::size_t>(u) - 1][static_cast<std::size_t>(v) - 1] = true;
    }
    std::vector<std::vector<bool>> reach(std::size_t{1} << n, std::vector<bool>(n, false));
    reach[std::size_t{1} << (s - 1)][static_cast<std::size_t>(s) - 1] = true;
    for (std::size_t set = 1; set < (std::size_t{1} << n); set++) {
        for (std::size_t v = 0; v < n; v++) {
            if (!reach[set][v]) {
                continue;
            }
            for (std::size_t u = 0; u < n; u++) {
                if (arc[v][u] && ((set >> u) & 1) == 0) {
                    reach[set | (std::size_t{1} << u)][u] = true;
                }
            }
        }
    }
    return reach[(std::size_t{1} << n) - 1][static_cast<std::size_t>(t) - 1];
}

static void test_hampath() {
    Graph g = example_digraph();
    assert(verify_hampath(g, 1, 5, {1, 2, 3, 4, 5}));
    assert(verify_hampath(g, 1, 5, {1, 3, 2, 4, 5}));
    assert(!verify_hampath(g, 1, 5, {1, 3, 4, 5}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 2, 4, 5}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 3, 4, 6}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 3, 4, 0}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 4, 3, 5}));
    assert(!verify_hampath(g, 1, 5, {2, 3, 4, 5, 1}));
    assert(verify_hampath(g, 2, 1, {2, 3, 4, 5, 1}));
    assert(!verify_hampath(g, 1, 5, {}));
    // El arco tiene dirección: 2→1 no existe.
    assert(!verify_hampath(g, 5, 1, {5, 4, 3, 2, 1}));
    // Exactamente dos de las 120 permutaciones son certificados para s = 1, t = 5.
    std::vector<int> order = {1, 2, 3, 4, 5};
    int valid = 0;
    do {
        valid += verify_hampath(g, 1, 5, order) ? 1 : 0;
    } while (std::next_permutation(order.begin(), order.end()));
    assert(valid == 2);

    // Un solo vértice: el camino de un vértice es hamiltoniano.
    Graph single;
    single.n = 1;
    assert(verify_hampath(single, 1, 1, {1}));
    assert(!verify_hampath(single, 1, 1, {1, 1}));

    // Grafos al azar: algún certificado es aceptado si y solo si el camino existe.
    std::mt19937 random(12);
    int yes = 0;
    for (int round = 0; round < 300; round++) {
        Graph h;
        h.n = 2 + static_cast<int>(random() % 5);
        for (int u = 1; u <= h.n; u++) {
            for (int v = 1; v <= h.n; v++) {
                if (u != v && random() % 100 < 35) {
                    h.edges.push_back({u, v});
                }
            }
        }
        int s = 1 + static_cast<int>(random() % static_cast<unsigned>(h.n));
        int t = 1 + static_cast<int>(random() % static_cast<unsigned>(h.n));
        std::vector<int> path(static_cast<std::size_t>(h.n));
        std::iota(path.begin(), path.end(), 1);
        bool some_certificate = false;
        do {
            some_certificate = some_certificate || verify_hampath(h, s, t, path);
        } while (std::next_permutation(path.begin(), path.end()));
        assert(some_certificate == has_hampath(h, s, t));
        yes += some_certificate ? 1 : 0;
    }
    assert(yes > 20 && yes < 280);
}

static void test_clique() {
    Graph g = example_graph();
    assert(verify_clique(g, 4, {1, 2, 3, 4}));
    assert(verify_clique(g, 4, {4, 2, 1, 3}));
    assert(!verify_clique(g, 4, {1, 2, 3, 5}));
    assert(!verify_clique(g, 4, {1, 2, 3, 3}));
    assert(!verify_clique(g, 4, {1, 2, 3}));
    assert(!verify_clique(g, 4, {1, 2, 3, 7}));
    assert(verify_clique(g, 2, {5, 6}));
    assert(verify_clique(g, 2, {6, 5}));
    assert(verify_clique(g, 1, {6}));
    assert(verify_clique(g, 0, {}));
    // No hay clique de 5 vértices: ninguno de los 6 subconjuntos de tamaño 5 sirve.
    for (int out = 1; out <= 6; out++) {
        std::vector<int> five;
        for (int v = 1; v <= 6; v++) {
            if (v != out) {
                five.push_back(v);
            }
        }
        assert(!verify_clique(g, 5, five));
    }
}

static void test_subset_sum() {
    std::vector<long long> numbers = example_numbers();
    long long additions = 0;
    assert(verify_subset_sum(numbers, 28, {1, 2, 4, 6}, &additions) && additions == 4);
    assert(verify_subset_sum(numbers, 28, {3, 4, 6}));
    assert(!verify_subset_sum(numbers, 28, {1, 3}));
    assert(!verify_subset_sum(numbers, 28, {4, 4, 4, 2}));
    assert(!verify_subset_sum(numbers, 28, {1, 2, 4, 7}));
    assert(!verify_subset_sum(numbers, 28, {0, 1, 2, 4, 6}));
    // Con objetivo 4 no hay solución, pero 2 + 2 = 4 si se deja repetir la posición 6.
    assert(!verify_subset_sum(numbers, 4, {6, 6}));
    assert(verify_subset_sum(numbers, 0, {}));
    assert(!verify_subset_sum(numbers, 28, {}));

    long long tried = 0;
    std::optional<std::vector<int>> found = search_subset_sum(numbers, 28, &tried);
    assert(found && *found == (std::vector<int>{1, 2, 4, 6}) && tried == 44);
    assert(!search_subset_sum(numbers, 4, &tried) && tried == 64);

    // La tabla de los apuntes: números pares y objetivo impar, la búsqueda prueba los 2^n.
    for (std::size_t n = 4; n <= 16; n += 4) {
        std::vector<long long> evens;
        for (std::size_t i = 1; i <= n; i++) {
            evens.push_back(2 * static_cast<long long>(i));
        }
        long long target = static_cast<long long>(n * (n + 1) / 2) | 1LL;
        assert(target % 2 == 1);
        assert(!search_subset_sum(evens, target, &tried));
        assert(tried == (1LL << n));
    }
}

// Evalúa la fórmula directamente, con bits[i] como valor de x_(i+1).
static bool evaluate(const Cnf& f, unsigned bits) {
    for (const std::vector<int>& clause : f.clauses) {
        bool satisfied = false;
        for (int literal : clause) {
            bool value = ((bits >> (std::abs(literal) - 1)) & 1U) != 0;
            satisfied = satisfied || (literal > 0 ? value : !value);
        }
        if (!satisfied) {
            return false;
        }
    }
    return true;
}

// Cuántas de las 2^n asignaciones acepta el verificador; comprueba que coincide con evaluar.
static int count_models(const Cnf& f) {
    int models = 0;
    for (unsigned bits = 0; bits < (1U << f.variables); bits++) {
        std::vector<int> assignment;
        for (int i = 1; i <= f.variables; i++) {
            assignment.push_back(((bits >> (i - 1)) & 1U) != 0 ? i : -i);
        }
        assert(verify_sat(f, assignment) == evaluate(f, bits));
        std::reverse(assignment.begin(), assignment.end());
        assert(verify_sat(f, assignment) == evaluate(f, bits));
        models += evaluate(f, bits) ? 1 : 0;
    }
    return models;
}

static void test_sat() {
    Cnf f = example_formula();
    assert(verify_sat(f, {1, 2, -3}));
    assert(verify_sat(f, {-3, 2, 1}));
    assert(verify_sat(f, {-1, -2, 3}));
    assert(!verify_sat(f, {1, -2, -3}));
    assert(!verify_sat(f, {1, 2}));
    assert(!verify_sat(f, {1, -1, 2, -3}));
    assert(!verify_sat(f, {1, 1, 2, -3}));
    assert(!verify_sat(f, {1, 2, -4}));
    assert(!verify_sat(f, {1, 2, 0}));
    assert(count_models(f) == 3);
    // La fórmula sin solución: el verificador no acepta ninguna de las 4 asignaciones.
    assert(count_models(example_unsatisfiable()) == 0);

    // Sin cláusulas, toda asignación completa sirve. Con una cláusula vacía, ninguna.
    Cnf empty;
    empty.variables = 2;
    assert(verify_sat(empty, {-1, 2}) && !verify_sat(empty, {2}));
    Cnf impossible;
    impossible.variables = 1;
    impossible.clauses = {{}};
    assert(!verify_sat(impossible, {1}) && !verify_sat(impossible, {-1}));
}

static void test_composites() {
    assert(verify_composite(8633, 89) && verify_composite(8633, 97));
    assert(89ULL * 97ULL == 8633ULL && 7ULL * 1233ULL + 2ULL == 8633ULL);
    assert(!verify_composite(8633, 7) && !verify_composite(8633, 1) && !verify_composite(8633, 8633));
    assert(!verify_composite(8633, 0));
    // x es compuesto si y solo si algún certificado es aceptado.
    for (unsigned long long x = 0; x <= 2000; x++) {
        bool some_certificate = false;
        for (unsigned long long d = 0; d <= x + 1; d++) {
            some_certificate = some_certificate || verify_composite(x, d);
        }
        long long divisions = 0;
        bool composite = x >= 2 && !trial_division(x, &divisions);
        assert(some_certificate == composite);
    }
    for (unsigned long long d = 0; d <= 8641; d++) {
        assert(!verify_composite(8641, d));
    }
}

int main() {
    test_hampath();
    test_clique();
    test_subset_sum();
    test_sat();
    test_composites();
    std::printf("test_verifiers: ok\n");
}
