// La reducción de cobertura de vértices a suma de subconjuntos, con un dígito en base 4 por arista.
// Los números son unsigned long long, así que esto solo corre con pocas aristas. Una reducción de verdad
// escribiría números de cualquier largo: esa longitud es el tema de la sección.
#pragma once
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <optional>
#include <string>
#include <vector>
#include "graph.h"

using Number = unsigned long long;

struct SubsetSumInstance {
    std::vector<Number> numbers;  // primero uno por nodo, después uno de holgura por arista
    Number target = 0;
    int vertices = 0;
    std::vector<std::pair<int, int>> edges;
    Number base = 4;
};

inline Number power_of(Number base, std::size_t exponent) {
    Number value = 1;
    for (std::size_t i = 0; i < exponent; i++) value *= base;
    return value;
}

// base = 4 es la reducción correcta. Otras bases solo sirven para ver cómo se rompe.
inline SubsetSumInstance reduce_to_subset_sum(const Graph& g, int k, Number base = 4) {
    SubsetSumInstance out;
    out.base = base;
    out.vertices = static_cast<int>(g.size());
    out.edges = edge_list(g);
    const std::size_t e = out.edges.size();
    assert(e <= 28);
    // Con k mayor que V, la respuesta no cambia si se toma k = V: V nodos ya cubren todo.
    k = std::min(k, out.vertices);
    const Number top = power_of(base, e);
    out.numbers.assign(g.size(), top);
    for (std::size_t j = 0; j < e; j++) {
        out.numbers[static_cast<std::size_t>(out.edges[j].first)] += power_of(base, j);
        out.numbers[static_cast<std::size_t>(out.edges[j].second)] += power_of(base, j);
    }
    for (std::size_t j = 0; j < e; j++) out.numbers.push_back(power_of(base, j));
    out.target = static_cast<Number>(k) * top;
    for (std::size_t j = 0; j < e; j++) out.target += 2 * power_of(base, j);
    return out;
}

// Los dígitos de un número en la base de la instancia: el más alto primero, sin partir el de arriba.
inline std::string digits_text(Number value, Number base, std::size_t edges) {
    std::string text = std::to_string(value / power_of(base, edges));
    for (std::size_t j = edges; j-- > 0;) {
        text += " " + std::to_string((value / power_of(base, j)) % base);
    }
    return text;
}

// El verificador: el certificado es la lista de posiciones elegidas.
inline bool sums_to_target(const SubsetSumInstance& s, const std::vector<std::size_t>& chosen) {
    Number total = 0;
    for (std::size_t i : chosen) total += s.numbers[i];
    return total == s.target;
}

// Fuerza bruta: 2ⁿ subconjuntos. Devuelve las posiciones de uno que sume el objetivo.
inline std::optional<std::vector<std::size_t>> brute_subset_sum(const std::vector<Number>& numbers, Number target) {
    const std::size_t n = numbers.size();
    assert(n < 40);
    for (unsigned long long mask = 0; mask < (1ULL << n); mask++) {
        Number total = 0;
        for (std::size_t i = 0; i < n; i++) {
            if ((mask >> i) & 1) total += numbers[i];
        }
        if (total == target) {
            std::vector<std::size_t> chosen;
            for (std::size_t i = 0; i < n; i++) {
                if ((mask >> i) & 1) chosen.push_back(i);
            }
            return chosen;
        }
    }
    return std::nullopt;
}

// Programación dinámica de la semana 7, en O(nW): reachable[c] dice si alguna elección suma c.
// Los números tienen que ser positivos.
inline bool subset_sum_dp(const std::vector<Number>& numbers, Number target) {
    std::vector<char> reachable(static_cast<std::size_t>(target) + 1, 0);
    reachable[0] = 1;
    for (Number x : numbers) {
        if (x > target) continue;
        for (std::size_t c = static_cast<std::size_t>(target); c >= static_cast<std::size_t>(x); c--) {
            if (reachable[c - static_cast<std::size_t>(x)]) reachable[c] = 1;
        }
    }
    return reachable[static_cast<std::size_t>(target)] != 0;
}

// De una cobertura de tamaño a lo sumo k a una elección que suma el objetivo: se completa hasta tener
// exactamente k nodos, y cada arista con un solo extremo elegido toma su holgura.
inline std::vector<std::size_t> subset_from_cover(const SubsetSumInstance& s, const std::vector<int>& cover, int k) {
    std::vector<char> inside(static_cast<std::size_t>(s.vertices), 0);
    for (int v : cover) inside[static_cast<std::size_t>(v)] = 1;
    int have = static_cast<int>(cover.size());
    k = std::min(k, s.vertices);
    for (std::size_t v = 0; have < k; v++) {
        if (!inside[v]) {
            inside[v] = 1;
            have++;
        }
    }
    std::vector<std::size_t> chosen;
    for (std::size_t v = 0; v < inside.size(); v++) {
        if (inside[v]) chosen.push_back(v);
    }
    for (std::size_t j = 0; j < s.edges.size(); j++) {
        int ends = inside[static_cast<std::size_t>(s.edges[j].first)] + inside[static_cast<std::size_t>(s.edges[j].second)];
        if (ends == 1) chosen.push_back(static_cast<std::size_t>(s.vertices) + j);
    }
    return chosen;
}

// De una elección que suma el objetivo a una cobertura: los números de nodo elegidos.
inline std::vector<int> cover_from_subset(const SubsetSumInstance& s, const std::vector<std::size_t>& chosen) {
    std::vector<int> cover;
    for (std::size_t i : chosen) {
        if (i < static_cast<std::size_t>(s.vertices)) cover.push_back(static_cast<int>(i));
    }
    return cover;
}