// PATH con memoria logarítmica, si alguien adivina el camino.
//
//     guess_path archivo.graph destino nodo nodo...
//
// Los nodos de la línea de comandos son las elecciones de la máquina no determinista: el
// siguiente nodo del camino, una por paso. El programa las lee una sola vez, de izquierda a
// derecha, y solo guarda dos cosas: el nodo actual y un contador de pasos.
#include <iostream>
#include <stdexcept>
#include <string>

#include "graph.h"
#include "savitch.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: guess_path archivo.graph destino nodo...\n";
        return 2;
    }
    try {
        Graph g = load_graph(argv[1]);
        int target = node_index(g, argv[2]);
        int n = static_cast<int>(g.nodes.size());

        // Toda la memoria de trabajo: dos números entre 0 y n.
        int current = g.start;
        int steps = 0;

        std::cout << "paso 0: en " << g.nodes[current] << '\n';
        for (int i = 3; i < argc && current != target; i++) {
            int guess = node_index(g, argv[i]);
            if (steps == n - 1) {
                std::cout << "rechaza: ya dio " << steps << " pasos, y un camino sin repetir nodos no tiene más\n";
                return 0;
            }
            if (!has_edge(g, current, guess)) {
                std::cout << "rechaza: no hay arista de " << g.nodes[current] << " a " << g.nodes[guess] << '\n';
                return 0;
            }
            current = guess;
            steps++;
            std::cout << "paso " << steps << ": en " << g.nodes[current] << '\n';
        }
        std::cout << (current == target ? "acepta: llegó a " + g.nodes[target] : "rechaza: se acabaron las elecciones")
                  << '\n';
        std::cout << "memoria de trabajo: 2 números de " << bits_for(n + 1) << " bits, para un grafo de " << n
                  << " nodos\n";
    } catch (const std::runtime_error& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 1;
    }
    return 0;
}
