// Held-Karp en cuatro ciudades, casilla por casilla, y cuánto trabajo ahorra frente a las permutaciones.
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "held_karp.h"

namespace {

std::string subset_name(std::size_t mask, int n) {
    std::string text = "{";
    for (int v = 1; v < n; v++) {
        if ((mask & (std::size_t{1} << (v - 1))) != 0) {
            if (text.size() > 1) text += ",";
            text += std::to_string(v);
        }
    }
    return text + "}";
}

tsp::Costs random_costs(int n, std::mt19937& gen) {
    tsp::Costs cost(tsp::idx(n), std::vector<long long>(tsp::idx(n), 0));
    for (auto& row : cost) {
        for (long long& c : row) c = static_cast<long long>(gen() % 100) + 1;
    }
    return cost;
}

}  // namespace

int main() {
    const tsp::Costs cost = {{0, 10, 15, 20}, {5, 0, 9, 10}, {6, 13, 0, 12}, {8, 8, 9, 0}};
    std::cout << "Costos:\n";
    for (const auto& row : cost) {
        for (long long c : row) std::cout << std::setw(4) << c;
        std::cout << '\n';
    }
    const auto table = tsp::held_karp_table(cost);
    std::cout << "\nmáscara  subconjunto  termina en 1  en 2  en 3\n";
    for (std::size_t mask = 1; mask < table.size(); mask++) {
        std::cout << std::setw(7) << mask << "  " << std::setw(11) << subset_name(mask, 4);
        for (int v = 1; v <= 3; v++) {
            const long long value = table[mask][tsp::idx(v)];
            std::cout << std::setw(v == 1 ? 14 : 6) << (value == tsp::NONE ? std::string("-") : std::to_string(value));
        }
        std::cout << '\n';
    }
    std::cout << "\nmejor recorrido, Held-Karp: " << tsp::held_karp(cost) << '\n';
    std::cout << "mejor recorrido, permutaciones: " << tsp::brute_force(cost) << '\n';

    std::cout << "\n n  recorridos (n-1)!  transiciones  n^2 2^n     mismo costo\n";
    std::mt19937 gen(15);
    for (int n = 4; n <= 11; n++) {
        const tsp::Costs random = random_costs(n, gen);
        long long tours = 0;
        long long transitions = 0;
        const long long by_brute = tsp::brute_force(random, &tours);
        const long long by_table = tsp::held_karp(random, &transitions);
        std::cout << std::setw(2) << n << std::setw(19) << tours << std::setw(14) << transitions << std::setw(9)
                  << n * n * (1LL << n) << std::setw(16) << (by_brute == by_table ? "sí" : "NO") << '\n';
    }
}