// Mejora local con 2-opt sobre las capitales: de dónde sale, a dónde llega y qué tanto depende de
// dónde empieza. Las cifras de distancias en kilómetros son los metros divididos entre 1000.
#include <algorithm>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

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

namespace {

using geo::at;

void show_tour(const std::vector<geo::Place>& places, const tour::Tour& t) {
    std::cout << " ";
    for (int v : t) std::cout << ' ' << places[at(v)].name;
    std::cout << '\n';
}

double km(long long metres) { return static_cast<double>(metres) / 1000.0; }

}  // namespace

int main() {
    const auto all = geo::read_places("capitales.csv");
    const auto places = geo::first_places(all, 20);
    const auto d = geo::distance_matrix(places);
    std::cout << std::fixed << std::setprecision(1);

    auto t = tour::double_tree(d);
    std::cout << "Las primeras 20 filas. Árbol duplicado, " << km(tour::tour_length(d, t)) << " km:\n";
    show_tour(places, t);
    const auto moves = tour::two_opt_plain(d, t);
    for (const auto& move : moves) {
        std::cout << "  invertir de la posición " << move.i << " a la " << move.j << ": " << km(move.length_after) << " km\n";
    }
    std::cout << "Después de 2-opt:\n";
    show_tour(places, t);
    const long long optimum = tsp::held_karp(d);
    std::cout << "óptimo, con Held-Karp: " << km(optimum) << " km\n\n";

    std::cout << "2-opt desde 2000 recorridos al azar, las mismas 20 filas:\n";
    std::mt19937 rng(15);
    std::vector<long long> finals;
    for (int run = 0; run < 2000; run++) {
        tour::Tour start(places.size());
        for (std::size_t i = 0; i < start.size(); i++) start[i] = static_cast<int>(i);
        for (std::size_t i = start.size() - 1; i > 0; i--) std::swap(start[i], start[rng() % (i + 1)]);
        tour::two_opt_plain(d, start);
        finals.push_back(tour::tour_length(d, start));
    }
    std::sort(finals.begin(), finals.end());
    const auto count_best = std::count(finals.begin(), finals.end(), optimum);
    std::cout << "  mejor " << km(finals.front()) << " km, mediana " << km(finals[finals.size() / 2]) << " km, peor "
              << km(finals.back()) << " km\n";
    std::cout << "  llegaron al óptimo: " << count_best << " de " << finals.size() << '\n';
    std::cout << std::setprecision(3) << "  peor largo / óptimo: "
              << static_cast<double>(finals.back()) / static_cast<double>(optimum) << '\n';
}