// Buscar frente a comprobar, con SUBSET-SUM.
//  - search_subset_sum prueba todos los certificados posibles con el verificador: es la
//    demostración de que NP está contenida en EXPTIME, hecha programa.
//  - subset_sum_table es la programación dinámica de Algoritmos: llena una tabla con una
//    casilla por cada suma posible, y por eso su costo depende del valor del objetivo.
//  - trial_division decide si un número es primo probando divisores.
#ifndef SEARCH_H
#define SEARCH_H

#include <cstddef>
#include <optional>
#include <vector>

#include "verifiers.h"

// Recorre los 2^n subconjuntos en orden y devuelve el primero que el verificador acepta, si
// hay alguno. tried recibe cuántos certificados se probaron. Requiere n < 63.
inline std::optional<std::vector<int>> search_subset_sum(const std::vector<long long>& numbers, long long target,
                                                         long long* tried) {
    std::size_t n = numbers.size();
    *tried = 0;
    for (unsigned long long mask = 0; mask < (1ULL << n); mask++) {
        std::vector<int> chosen;
        for (std::size_t i = 0; i < n; i++) {
            if ((mask >> i) & 1ULL) {
                chosen.push_back(static_cast<int>(i) + 1);
            }
        }
        (*tried)++;
        if (verify_subset_sum(numbers, target, chosen)) {
            return chosen;
        }
    }
    return std::nullopt;
}

// Decide SUBSET-SUM con la tabla de sumas alcanzables: reachable[c] dice si algún subconjunto
// de los números vistos hasta ahora suma c. cells recibe cuántas casillas se calcularon:
// n · (target + 1).
inline bool subset_sum_table(const std::vector<long long>& numbers, long long target, long long* cells) {
    std::vector<bool> reachable(static_cast<std::size_t>(target) + 1, false);
    reachable[0] = true;
    *cells = 0;
    for (long long x : numbers) {
        // De mayor a menor, para no usar el mismo número dos veces.
        for (long long c = target; c >= 0; c--) {
            (*cells)++;
            if (c >= x && reachable[static_cast<std::size_t>(c - x)]) {
                reachable[static_cast<std::size_t>(c)] = true;
            }
        }
    }
    return reachable[static_cast<std::size_t>(target)];
}

// Decide si x es primo probando los divisores 2, 3, ..., hasta la raíz de x.
// divisions recibe cuántas divisiones se hicieron.
inline bool trial_division(unsigned long long x, long long* divisions) {
    *divisions = 0;
    if (x < 2) {
        return false;
    }
    for (unsigned long long d = 2; d * d <= x; d++) {
        (*divisions)++;
        if (x % d == 0) {
            return false;
        }
    }
    return true;
}

// La cantidad de bits de x en binario, sin ceros a la izquierda: ⌊log2 x⌋ + 1. El 0 ocupa un bit.
inline int bit_length(unsigned long long x) {
    int bits = 1;
    while (x > 1) {
        x /= 2;
        bits++;
    }
    return bits;
}

#endif
