// La reducción de cobertura de vértices a suma de subconjuntos: la tabla, las respuestas y otras bases.
#include <iomanip>
#include <iostream>
#include <random>
#include "subset_sum.h"

namespace {

void show_table(const SubsetSumInstance& s) {
    std::cout << "  " << std::left << std::setw(12) << "número" << "arriba";
    for (std::size_t j = s.edges.size(); j-- > 0;) std::cout << " e" << j;
    std::cout << "   decimal\n";
    for (std::size_t i = 0; i < s.numbers.size(); i++) {
        std::string label;
        if (i < static_cast<std::size_t>(s.vertices)) label = "nodo " + std::to_string(i);
        else label = "holgura e" + std::to_string(i - static_cast<std::size_t>(s.vertices));
        // setw cuenta bytes: estas etiquetas son solo ASCII.
        std::cout << "  " << std::setw(12) << label;
        std::cout << std::setw(6) << s.numbers[i] / power_of(s.base, s.edges.size());
        for (std::size_t j = s.edges.size(); j-- > 0;) std::cout << "  " << (s.numbers[i] / power_of(s.base, j)) % s.base;
        std::cout << "   " << s.numbers[i] << '\n';
    }
    std::cout << "  " << std::setw(12) << "objetivo" << std::setw(6) << s.target / power_of(s.base, s.edges.size());
    for (std::size_t j = s.edges.size(); j-- > 0;) std::cout << "  " << (s.target / power_of(s.base, j)) % s.base;
    std::cout << "   " << s.target << '\n';
}

void show_answer(const Graph& g, int k) {
    SubsetSumInstance s = reduce_to_subset_sum(g, k);
    auto chosen = brute_subset_sum(s.numbers, s.target);
    std::cout << "  k = " << k << ": cobertura mínima de tamaño " << min_vertex_cover(g).size() << ", suma: ";
    if (!chosen) {
        std::cout << "ninguna elección llega al objetivo " << s.target << '\n';
        return;
    }
    std::cout << "se llega con";
    for (std::size_t i : *chosen) std::cout << ' ' << s.numbers[i];
    std::cout << "\n    nodos elegidos:";
    for (int v : cover_from_subset(s, *chosen)) std::cout << ' ' << v;
    std::cout << '\n';
}

// Busca un grafo pequeño en el que otra base dé una respuesta falsa.
void search_other_base(Number base) {
    std::mt19937 random(14);
    const int rounds = 4000;
    for (int round = 0; round < rounds; round++) {
        int n = 2 + static_cast<int>(random() % 4);
        Graph g(static_cast<std::size_t>(n));
        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                if (random() % 2) add_edge(g, u, v);
            }
        }
        int cover = static_cast<int>(min_vertex_cover(g).size());
        for (int k = 0; k <= n; k++) {
            SubsetSumInstance s = reduce_to_subset_sum(g, k, base);
            if (brute_subset_sum(s.numbers, s.target).has_value() != (cover <= k)) {
                std::cout << "  base " << base << ": hay una respuesta falsa\n";
                return;
            }
        }
    }
    std::cout << "  base " << base << ": ninguna respuesta falsa en " << rounds << " grafos al azar\n";
}

// Dos aristas separadas, en base 2: el objetivo ya no dice "2 en cada dígito".
void show_base_two() {
    Graph g = make_graph(4, {{0, 1}, {2, 3}});
    SubsetSumInstance s = reduce_to_subset_sum(g, 0, 2);
    std::cout << "  aristas 0-1 y 2-3, k = 0, cobertura mínima " << min_vertex_cover(g).size() << '\n';
    std::cout << "  números:";
    for (Number x : s.numbers) std::cout << ' ' << x;
    std::cout << ", objetivo " << s.target << '\n';
    auto chosen = brute_subset_sum(s.numbers, s.target);
    std::cout << "  la suma dice " << (chosen ? "sí" : "no") << ", con";
    for (std::size_t i : *chosen) std::cout << " el número " << s.numbers[i] << " (posición " << i << ")";
    std::cout << '\n';
}

}  // namespace

int main() {
    Graph g = make_graph(4, {{0, 1}, {0, 2}, {1, 2}, {2, 3}});
    std::cout << "Grafo de 4 nodos con aristas";
    std::vector<std::pair<int, int>> edges = edge_list(g);
    for (std::size_t j = 0; j < edges.size(); j++) std::cout << " e" << j << "=" << edges[j].first << "-" << edges[j].second;
    std::cout << "\n\nLa tabla con k = 2, en base 4:\n";
    show_table(reduce_to_subset_sum(g, 2));

    std::cout << "\nRespuestas:\n";
    for (int k = 0; k <= 5; k++) show_answer(g, k);

    std::cout << "\nEn base 2 los dígitos se pisan:\n";
    show_base_two();

    std::cout << "\nBúsqueda de respuestas falsas en otras bases:\n";
    search_other_base(2);
    search_other_base(3);
    search_other_base(4);
}