// El árbol duplicado, paso a paso, con ocho capitales.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

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

namespace {

using geo::at;

std::vector<geo::Place> chosen_places() {
    const auto all = geo::read_places("capitales.csv");
    std::vector<geo::Place> places;
    for (const std::string name : {"Lima", "Callao", "Huacho", "Huancayo", "Ica", "Ayacucho", "Cusco", "Arequipa"}) {
        for (const auto& place : all) {
            if (place.name == name) places.push_back(place);
        }
    }
    return places;
}

std::string km(long long metres) {
    const long long tenths = (metres + 50) / 100;
    return std::to_string(tenths / 10) + "," + std::to_string(tenths % 10) + " km";
}

}  // namespace

int main() {
    const auto places = chosen_places();
    const auto d = geo::distance_matrix(places);
    const int n = static_cast<int>(places.size());
    const auto tree = tour::minimum_spanning_tree(d);

    std::cout << "Aristas del árbol de expansión mínima, con raíz en " << places[0].name << ":\n";
    for (int v = 0; v < n; v++) {
        for (int child : tree.children[at(v)]) {
            std::cout << "  " << places[at(v)].name << " - " << places[at(child)].name << ": " << km(d[at(v)][at(child)]) << '\n';
        }
    }
    std::cout << "peso del árbol: " << km(tree.weight) << "\n\n";

    const auto walk = tour::euler_walk(tree);
    std::cout << "Caminata, cada arista dos veces:\n ";
    for (int v : walk) std::cout << ' ' << places[at(v)].name;
    std::cout << "\nlargo de la caminata: " << km(tour::walk_length(d, walk)) << "\n\n";

    const auto shortened = tour::shortcut(walk, n);
    std::cout << "Atajando las repeticiones:\n ";
    for (int v : shortened) std::cout << ' ' << places[at(v)].name;
    std::cout << " y de vuelta a " << places[at(shortened[0])].name << '\n';
    const long long length = tour::tour_length(d, shortened);
    const long long optimum = tsp::held_karp(d);
    std::cout << "largo del recorrido: " << km(length) << '\n';
    std::cout << "óptimo, con Held-Karp: " << km(optimum) << '\n';
    std::cout << "dos veces el árbol: " << km(2 * tree.weight) << "\n\n";
}