// Buscar frente a comprobar. Para SUBSET-SUM, cuenta cuántos certificados prueba la búsqueda
// exhaustiva y cuántas sumas hace el verificador con un solo certificado.
// Son conteos de operaciones, no tiempos: no dependen de la computadora.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <optional>
#include <vector>

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

int main() {
    std::vector<long long> numbers = example_numbers();
    for (long long target : {28LL, 4LL}) {
        long long tried = 0;
        std::optional<std::vector<int>> found = search_subset_sum(numbers, target, &tried);
        std::cout << "Números 8 13 21 5 17 2, objetivo " << target << ": ";
        if (found) {
            std::cout << "certificado";
            for (int i : *found) {
                std::cout << ' ' << i;
            }
            std::cout << ", hallado después de probar " << tried << " de 64\n";
        } else {
            std::cout << "ningún certificado sirve; se probaron los " << tried << "\n";
        }
    }

    // Instancias sin solución: los números son pares y el objetivo es impar. La búsqueda no
    // puede detenerse antes de probar todos los subconjuntos.
    std::cout << "\nInstancias sin solución: los números 2, 4, ..., 2n y un objetivo impar, cerca de la mitad de la suma\n";
    std::cout << " n   certificados que prueba la búsqueda   sumas del verificador con un certificado\n";
    for (std::size_t n = 4; n <= 16; n += 4) {
        std::vector<long long> evens;
        std::vector<int> everything;
        for (std::size_t i = 1; i <= n; i++) {
            evens.push_back(2 * static_cast<long long>(i));
            everything.push_back(static_cast<int>(i));
        }
        long long target = static_cast<long long>(n * (n + 1) / 2) | 1LL;
        long long tried = 0;
        std::optional<std::vector<int>> found = search_subset_sum(evens, target, &tried);
        long long additions = 0;
        bool ok = verify_subset_sum(evens, target, everything, &additions);
        std::cout << std::setw(2) << n << std::setw(24) << tried << std::setw(38) << additions
                  << (found || ok ? "   (inesperado: hay solución)" : "") << '\n';
    }
}
