// La comparación de la semana: largo y tiempo de cada método con 10, 15, 20 y 26 ciudades. Cada
// tiempo es el menor de tres corridas, con -O2. El 2-opt de aquí es el lento de tour.h.
#include <algorithm>
#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string>

#include "../week-10/held_karp.h"
#include "bound.h"
#include "geo.h"
#include "tour.h"

namespace {

struct Measured {
    long long length;
    double seconds;
};

Measured measure(int runs, const std::function<long long()>& method) {
    Measured best{0, 1e18};
    for (int r = 0; r < runs; r++) {
        const auto start = std::chrono::steady_clock::now();
        best.length = method();
        const std::chrono::duration<double> elapsed = std::chrono::steady_clock::now() - start;
        best.seconds = std::min(best.seconds, elapsed.count());
    }
    return best;
}

void row(const std::string& name, const Measured& m, long long reference) {
    std::cout << "  " << std::left << std::setw(26) << name << std::right << std::setw(9) << std::fixed
              << std::setprecision(1) << static_cast<double>(m.length) / 1000.0 << " km" << std::setw(9)
              << std::setprecision(3) << static_cast<double>(m.length) / static_cast<double>(reference)
              << std::setw(10) << m.seconds << " s\n";
}

}  // namespace

int main() {
    const auto all = geo::read_places("capitales.csv");
    for (int n : {10, 15, 20, 26}) {
        const auto d = geo::distance_matrix(geo::first_places(all, n));
        // El óptimo viene de la búsqueda con cota de árbol, que es exacta. Es el divisor de la razón.
        const auto exact = measure(n >= 20 ? 1 : 3, [&] { return bound::solve(d, bound::Pruning::spanning).cost; });
        std::cout << "n = " << n << "                       largo     / óptimo    tiempo\n";
        row("árbol de expansión mínima", measure(3, [&] { return tour::minimum_spanning_tree(d).weight; }), exact.length);
        row("árbol duplicado", measure(3, [&] { return tour::tour_length(d, tour::double_tree(d)); }), exact.length);
        row("duplicado + 2-opt", measure(3, [&] {
            auto t = tour::double_tree(d);
            tour::two_opt_plain(d, t);
            return tour::tour_length(d, t);
        }), exact.length);
        row("vecino más cercano", measure(3, [&] { return tour::tour_length(d, tour::nearest_neighbor(d)); }), exact.length);
        row("vecino + 2-opt", measure(3, [&] {
            auto t = tour::nearest_neighbor(d);
            tour::two_opt_plain(d, t);
            return tour::tour_length(d, t);
        }), exact.length);
        if (n <= 20) row("Held-Karp", measure(3, [&] { return tsp::held_karp(d); }), exact.length);
        row("búsqueda con cota", exact, exact.length);
        std::cout << '\n';
    }
}