// Pruebas de lo que los apuntes afirman sobre la geografía generalizada.
#include <cassert>
#include <cstdio>
#include <random>
#include <stdexcept>
#include <string>

#include "geography.h"

static Graph random_graph(std::mt19937& rng, int n, int percent) {
    Graph g;
    for (int i = 0; i < n; i++) {
        g.nodes.push_back("n" + std::to_string(i));
        g.edges.emplace_back();
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (u != v && static_cast<int>(rng() % 100) < percent) {
                g.edges[u].push_back(v);
            }
        }
    }
    g.start = static_cast<int>(rng() % n);
    return g;
}

static Graph complete_graph(int n) {
    Graph g;
    for (int i = 0; i < n; i++) {
        g.nodes.push_back("n" + std::to_string(i));
        g.edges.emplace_back();
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (u != v) {
                g.edges[u].push_back(v);
            }
        }
    }
    return g;
}

int main() {
    // El grafo de las ciudades sigue la regla del juego: hay arista de u a v exactamente cuando
    // v empieza con la letra en que termina u.
    Graph cities = load_graph("machines/cities.graph");
    assert(cities.nodes.size() == 9);
    assert(cities.nodes[cities.start] == "lima");
    for (std::size_t u = 0; u < cities.nodes.size(); u++) {
        for (std::size_t v = 0; v < cities.nodes.size(); v++) {
            bool by_rule = u != v && cities.nodes[u].back() == cities.nodes[v].front();
            bool in_file = false;
            for (int w : cities.edges[u]) {
                in_file = in_file || static_cast<std::size_t>(w) == v;
            }
            assert(by_rule == in_file);
        }
    }
    GameStats city_stats;
    int city_move = winning_first_move(cities, city_stats);
    assert(first_player_wins_by_table(cities) == (city_move != -1));
    assert(city_stats.max_path <= 9);

    // El juego de cinco nodos que se resuelve a mano en los apuntes.
    Graph small = load_graph("machines/small_game.graph");
    GameStats small_stats;
    int small_move = winning_first_move(small, small_stats);
    assert(small_move != -1 && small.nodes[small_move] == "b");
    assert(small_stats.max_path == 4);  // el camino a, b, d, e
    {
        // La otra primera jugada, c, pierde: el rival responde e.
        std::vector<bool> visited(small.nodes.size(), false);
        visited[node_index(small, "a")] = true;
        visited[node_index(small, "c")] = true;
        GameStats s;
        assert(mover_wins(small, node_index(small, "c"), visited, 2, s));
    }

    // Bordes: un nodo sin aristas, y un ciclo de dos nodos (volver al inicio no se puede).
    Graph alone;
    alone.nodes = {"a"};
    alone.edges = {{}};
    assert(!first_player_wins(alone));
    Graph two;
    two.nodes = {"a", "b"};
    two.edges = {{1}, {0}};
    assert(first_player_wins(two));

    // En el grafo completo de n nodos la partida dura siempre n - 1 jugadas: gana el primero
    // exactamente cuando n es par.
    for (int n = 1; n <= 9; n++) {
        Graph k = complete_graph(n);
        GameStats s;
        assert((winning_first_move(k, s) != -1) == (n % 2 == 0));
        assert(s.max_path == n);
    }

    // La búsqueda que guarda solo el camino y la tabla de 2^n · n casillas dan lo mismo.
    // Además, la jugada que devuelve la búsqueda gana de verdad.
    std::mt19937 rng(1414);
    int wins = 0;
    const int total = 4000;
    for (int k = 0; k < total; k++) {
        int n = 1 + static_cast<int>(rng() % 9);
        Graph g = random_graph(rng, n, 15 + static_cast<int>(rng() % 50));
        GameStats s;
        int move = winning_first_move(g, s);
        assert((move != -1) == first_player_wins_by_table(g));
        assert(s.max_path <= n);
        if (move != -1) {
            std::vector<bool> visited(g.nodes.size(), false);
            visited[g.start] = true;
            visited[move] = true;
            GameStats after;
            assert(!mover_wins(g, move, visited, 2, after));
            wins++;
        }
    }
    assert(wins > total / 10 && wins < total - total / 10);

    // Un grafo mal escrito no se carga.
    bool failed = false;
    try {
        load_graph("errors/unknown_node.graph");
    } catch (const std::runtime_error& e) {
        failed = std::string(e.what()).find("arista mal escrita") != std::string::npos;
    }
    assert(failed);

    std::printf("test_geography: los grafos de la clase y %d grafos al azar (en %d gana el primer jugador)\n", total,
                wins);
    return 0;
}
