// Mide las permutaciones frente a Held-Karp. Con -O2, una corrida, en la máquina del momento.
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "held_karp.h"

namespace {

template <typename Work>
double seconds_of(Work work) {
    const auto start = std::chrono::steady_clock::now();
    work();
    return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}

}  // namespace

int main() {
    std::mt19937 gen(20);
    std::printf("%3s %14s %14s %16s\n", "n", "permutaciones", "Held-Karp", "memoria de tabla");
    for (int n = 8; n <= 20; n += (n < 12 ? 1 : 2)) {
        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;
        }
        long long a = 0;
        long long b = 0;
        const double t_table = seconds_of([&] { b = tsp::held_karp(cost); });
        const double megabytes = static_cast<double>((1ULL << (n - 1)) * static_cast<unsigned long long>(n) * 8) / 1e6;
        if (n <= 12) {
            const double t_brute = seconds_of([&] { a = tsp::brute_force(cost); });
            std::printf("%3d %12.3f s %12.3f s %13.1f MB  %s\n", n, t_brute, t_table, megabytes, a == b ? "iguales" : "DISTINTOS");
        } else {
            std::printf("%3d %14s %12.3f s %13.1f MB\n", n, "-", t_table, megabytes);
        }
    }
}