// Corre los cinco verificadores con las instancias de los apuntes, cada una con certificados
// buenos, malos y mal formados.
#include <iostream>
#include <string>
#include <vector>

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

static std::string list(const std::vector<int>& values) {
    std::string text;
    for (int v : values) {
        text += (text.empty() ? "" : " ") + std::to_string(v);
    }
    return text.empty() ? "(vacío)" : text;
}

static void show(const std::string& certificate, bool ok, const std::string& why) {
    std::cout << "  c = " << certificate << std::string(certificate.size() < 14 ? 14 - certificate.size() : 1, ' ')
              << (ok ? "válido" : "inválido") << (why.empty() ? "" : "   " + why) << '\n';
}

int main() {
    Graph g = example_digraph();
    std::cout << "HAMPATH: grafo dirigido con 5 vértices y los arcos\n ";
    for (const auto& [u, v] : g.edges) {
        std::cout << ' ' << u << "→" << v;
    }
    std::cout << "\n  s = 1, t = 5\n";
    show(list({1, 2, 3, 4, 5}), verify_hampath(g, 1, 5, {1, 2, 3, 4, 5}), "");
    show(list({1, 3, 2, 4, 5}), verify_hampath(g, 1, 5, {1, 3, 2, 4, 5}), "");
    show(list({1, 3, 4, 5}), verify_hampath(g, 1, 5, {1, 3, 4, 5}), "tiene 4 vértices y no 5");
    show(list({1, 2, 2, 4, 5}), verify_hampath(g, 1, 5, {1, 2, 2, 4, 5}), "repite el vértice 2");
    show(list({1, 2, 3, 4, 6}), verify_hampath(g, 1, 5, {1, 2, 3, 4, 6}), "el vértice 6 no existe");
    show(list({1, 2, 4, 3, 5}), verify_hampath(g, 1, 5, {1, 2, 4, 3, 5}), "no hay arco 4→3");
    show(list({2, 3, 4, 5, 1}), verify_hampath(g, 1, 5, {2, 3, 4, 5, 1}), "es un camino hamiltoniano, pero no de s a t");

    Graph h = example_graph();
    std::cout << "\nCLIQUE: grafo no dirigido con 6 vértices y las aristas\n ";
    for (const auto& [u, v] : h.edges) {
        std::cout << ' ' << u << "-" << v;
    }
    std::cout << "\n  k = 4\n";
    show(list({1, 2, 3, 4}), verify_clique(h, 4, {1, 2, 3, 4}), "");
    show(list({4, 2, 1, 3}), verify_clique(h, 4, {4, 2, 1, 3}), "el orden no importa");
    show(list({1, 2, 3, 5}), verify_clique(h, 4, {1, 2, 3, 5}), "falta la arista 1-5");
    show(list({1, 2, 3, 3}), verify_clique(h, 4, {1, 2, 3, 3}), "repite el vértice 3");
    show(list({1, 2, 3}), verify_clique(h, 4, {1, 2, 3}), "son 3 vértices y se pedían 4");

    std::vector<long long> numbers = example_numbers();
    std::cout << "\nSUBSET-SUM: los números";
    for (long long x : numbers) {
        std::cout << ' ' << x;
    }
    std::cout << ", objetivo 28. El certificado son posiciones.\n";
    show(list({1, 2, 4, 6}), verify_subset_sum(numbers, 28, {1, 2, 4, 6}), "8 + 13 + 5 + 2 = 28");
    show(list({3, 4, 6}), verify_subset_sum(numbers, 28, {3, 4, 6}), "21 + 5 + 2 = 28");
    show(list({1, 3}), verify_subset_sum(numbers, 28, {1, 3}), "8 + 21 = 29");
    show(list({4, 4, 4, 2}), verify_subset_sum(numbers, 28, {4, 4, 4, 2}), "5 + 5 + 5 + 13 = 28, pero repite la posición 4");
    show(list({1, 2, 4, 7}), verify_subset_sum(numbers, 28, {1, 2, 4, 7}), "no hay posición 7");

    Cnf f = example_formula();
    std::cout << "\nSAT: φ = (x1 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (¬x3 ∨ ¬x1). El certificado son literales.\n";
    show(list({1, 2, -3}), verify_sat(f, {1, 2, -3}), "");
    show(list({-3, 2, 1}), verify_sat(f, {-3, 2, 1}), "el orden no importa");
    show(list({-1, -2, 3}), verify_sat(f, {-1, -2, 3}), "");
    show(list({1, -2, -3}), verify_sat(f, {1, -2, -3}), "la segunda cláusula queda falsa");
    show(list({1, 2}), verify_sat(f, {1, 2}), "x3 no tiene valor");
    show(list({1, -1, 2, -3}), verify_sat(f, {1, -1, 2, -3}), "x1 tiene dos valores");
    show(list({1, 2, -4}), verify_sat(f, {1, 2, -4}), "no hay variable x4");

    std::cout << "\nCOMPOSITES: x = 8633. El certificado es un divisor.\n";
    show("89", verify_composite(8633, 89), "8633 = 89 · 97");
    show("97", verify_composite(8633, 97), "");
    show("7", verify_composite(8633, 7), "8633 = 7 · 1233 + 2");
    show("1", verify_composite(8633, 1), "1 divide a todos: no demuestra nada");
    show("8633", verify_composite(8633, 8633), "x se divide a sí mismo: tampoco");
    int accepted = 0;
    for (unsigned long long d = 0; d <= 8641; d++) {
        accepted += verify_composite(8641, d) ? 1 : 0;
    }
    std::cout << "  Con x = 8641, de los certificados 0, 1, ..., 8641 el verificador acepta " << accepted << ".\n";
}
