Semana 14 — Espacio

Objetivos

  • Medir el espacio que usa una máquina y relacionarlo con el tiempo.
  • Enunciar y demostrar el teorema de Savitch, y concluir que PSPACE=NPSPACE\mathsf{PSPACE} = \mathsf{NPSPACE}.
  • Explicar por qué TQBF y los juegos de dos jugadores son PSPACE-completos.
  • Definir L y NL y decir por qué alcanzabilidad en un grafo es el problema central de NL.

Sesión A — Complejidad en espacio · Teorema de Savitch · PSPACE

Lectura: Apuntes, semana 14.

Apoyo: Sipser, sec. 8.1 (Savitch’s Theorem) y 8.2 (The Class PSPACE). Barak, capítulo 17 (Space bounded computation).

Temas:

  • El espacio se reutiliza y el tiempo no: esa es toda la diferencia.
  • SPACE(f(n))\mathsf{SPACE}(f(n)) y NSPACE(f(n))\mathsf{NSPACE}(f(n)). SAT se decide con espacio lineal, probando las asignaciones una por una.
  • Tiempo y espacio: una máquina que usa espacio f(n)f(n) y se detiene tiene a lo sumo 2O(f(n))2^{O(f(n))} configuraciones, así que tarda a lo sumo eso.
  • La cadena P⊆NP⊆PSPACE⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME}. Solo se sabe que P≠EXPTIME\mathsf{P} \neq \mathsf{EXPTIME}.
  • Teorema de Savitch: NSPACE(f(n))⊆SPACE(f(n)2)\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2). La idea: para saber si se llega de una configuración a otra en tt pasos, probar cada configuración intermedia y resolver dos mitades, reutilizando el espacio.
  • La recursión tiene profundidad log⁡t\log t y cada nivel guarda una configuración: de ahí el cuadrado.
  • Consecuencia: PSPACE=NPSPACE\mathsf{PSPACE} = \mathsf{NPSPACE}. En espacio, el no determinismo cuesta poco. En tiempo, no se sabe.
  • Error común: aplicar el argumento de Savitch al tiempo. Las dos mitades reutilizan el espacio, pero sus tiempos se suman.

Sesión B — PSPACE-completitud: TQBF y juegos · L y NL

Lectura: Apuntes, semana 14.

Apoyo: Sipser, sec. 8.3 (PSPACE-completeness) y 8.4 a 8.6 (The Classes L and NL, NL-completeness, NL equals coNL). Barak, capítulo 17.

Temas:

  • Fórmulas booleanas cuantificadas: ∃x ∀y ∃z φ\exists x\, \forall y\, \exists z\, \varphi. SAT es el caso con solo ∃\exists.
  • TQBF está en PSPACE: una recursión que evalúa los dos valores de cada variable y reutiliza el espacio.
  • TQBF es PSPACE-completo: la idea es la de Savitch escrita como fórmula, con un ∀\forall que evita duplicar el tamaño. Se explica la idea; los detalles quedan en los apuntes.
  • Un juego es una fórmula cuantificada: “existe mi jugada tal que para toda jugada tuya existe…”.
  • Geografía generalizada: las reglas, un ejemplo, y por qué decidir quién gana es PSPACE-completo.
  • Por qué los juegos parecen más difíciles que los rompecabezas: un certificado de victoria es una estrategia entera, no una lista de jugadas.
  • Espacio menor que la entrada: una cinta de entrada de solo lectura y una de trabajo. L y NL.
  • PATH está en NL: adivinar el camino recordando solo el nodo actual y un contador. PATH es NL-completo, y NL⊆P\mathsf{NL} \subseteq \mathsf{P}.
  • NL=coNL\mathsf{NL} = \mathsf{coNL}, enunciado. En espacio, el complemento no cuesta; en NP no se sabe.
  • Error común: contar la entrada como espacio usado. En L y NL solo cuenta la cinta de trabajo.

Laboratorio — Práctica 4 · Opcional: quién gana en geografía generalizada

La sesión es para la Práctica 4 (semanas 12 y 13). Como ejercicio opcional:

  1. Leer un grafo dirigido y un nodo inicial, y decir si el primer jugador tiene una estrategia ganadora.
  2. Resolverlo con una búsqueda recursiva que guarda solo el camino actual: espacio polinomial y tiempo exponencial.
  3. Si gana, imprimir su primera jugada.
  4. Medir el tiempo con grafos de 10, 15 y 20 nodos y anotar cómo crece.

Preguntas de repaso

  1. Demuestren que una máquina que usa espacio f(n)≥nf(n) \geq n y siempre se detiene corre en tiempo 2O(f(n))2^{O(f(n))}.
  2. En la demostración de Savitch, ¿qué se guarda en cada nivel de la recursión y cuántos niveles hay?
  3. Evalúen a mano ∀x ∃y ((x∨y)∧(¬x∨¬y))\forall x\, \exists y\, ((x \lor y) \land (\lnot x \lor \lnot y)) y ∃y ∀x ((x∨y)∧(¬x∨¬y))\exists y\, \forall x\, ((x \lor y) \land (\lnot x \lor \lnot y)). ¿Por qué importa el orden?
  4. Escriban como fórmula cuantificada “el primer jugador gana en a lo sumo tres jugadas”.
  5. ¿Por qué el algoritmo de BFS para PATH no muestra que PATH está en L?

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (20)Errores (3)Pruebas (4)Laboratorio (4)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

eval_qbf.cppDescargar eval_qbf.cpp
// Evalúa fórmulas booleanas cuantificadas con la recursión de la clase.
//
//     eval_qbf [--tree] archivo.qbf...
//
// Por cada archivo imprime la fórmula, su valor, cuántas llamadas hizo la recursión y cuántas
// estuvieron activas a la vez. Con --tree imprime además el árbol de la recursión.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "qbf.h"

// La misma recursión que evaluate, de qbf.h, pero imprime lo que va probando.
static bool evaluate_and_print(const Qbf& f, std::vector<bool>& values, std::size_t i) {
    std::string indent(2 * i, ' ');
    if (i == f.variables.size()) {
        return matrix_value(f, values);
    }
    bool is_last = i + 1 == f.variables.size();
    bool exists = f.quantifiers[i] == 'E';
    bool result = !exists;
    for (int value = 0; value <= 1; value++) {
        values[i] = value == 1;
        std::cout << indent << f.variables[i] << " = " << value;
        if (!is_last) {
            std::cout << '\n';
        }
        bool sub = evaluate_and_print(f, values, i + 1);
        if (is_last) {
            std::cout << "   ψ = " << (sub ? "verdadero" : "falso") << '\n';
        }
        if (sub == exists) {
            result = exists;  // ∃ encontró un valor que sirve, o ∀ uno que falla
            break;
        }
    }
    std::cout << indent << (exists ? "∃" : "∀") << f.variables[i] << ": " << (result ? "verdadero" : "falso") << '\n';
    return result;
}

int main(int argc, char** argv) {
    bool tree = false;
    std::vector<std::string> paths;
    for (int i = 1; i < argc; i++) {
        std::string arg = argv[i];
        if (arg == "--tree") {
            tree = true;
        } else {
            paths.push_back(arg);
        }
    }
    if (paths.empty()) {
        std::cerr << "uso: eval_qbf [--tree] archivo.qbf...\n";
        return 2;
    }
    try {
        for (std::size_t k = 0; k < paths.size(); k++) {
            Qbf f = load_qbf(paths[k]);
            if (k > 0) {
                std::cout << '\n';
            }
            std::cout << paths[k] << ": " << to_text(f) << '\n';
            if (tree) {
                std::vector<bool> values(f.variables.size(), false);
                evaluate_and_print(f, values, 0);
            }
            EvalStats stats;
            bool value = is_true(f, stats);
            std::cout << "valor: " << (value ? "verdadero" : "falso") << "   llamadas: " << stats.calls
                      << "   llamadas activas a la vez: " << stats.max_depth << '\n';
        }
    } catch (const std::runtime_error& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 1;
    }
    return 0;
}
fields.hDescargar fields.h
// Lectura de los archivos de la semana: campos `nombre: valores`, comentarios con # y una
// lista de líneas al final. Son las reglas comunes de code/formats.md.
#ifndef FIELDS_H
#define FIELDS_H

#include <istream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

// Las palabras de una línea, separadas por espacios.
inline std::vector<std::string> split_words(const std::string& line) {
    std::vector<std::string> words;
    std::istringstream in(line);
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// La siguiente línea que no es comentario ni está vacía. Devuelve false al final de la entrada.
inline bool next_line(std::istream& in, std::string& line) {
    while (std::getline(in, line)) {
        if (!line.empty() && line.back() == '\r') {
            line.pop_back();
        }
        if (line.empty() || line[0] == '#') {
            continue;
        }
        if (!split_words(line).empty()) {
            return true;
        }
    }
    return false;
}

// Lee el campo `name:` y devuelve sus valores. Lanza std::runtime_error si la línea es otra.
inline std::vector<std::string> read_field(std::istream& in, const std::string& name) {
    std::string line;
    if (!next_line(in, line)) {
        throw std::runtime_error("falta el campo " + name + ":");
    }
    std::vector<std::string> words = split_words(line);
    if (words[0] != name + ":") {
        throw std::runtime_error("se esperaba el campo " + name + ": y se leyó \"" + line + "\"");
    }
    words.erase(words.begin());
    return words;
}

#endif
formula_game.hDescargar formula_game.h
// De una fórmula cuantificada a un grafo de geografía generalizada: la reducción que muestra
// que la geografía generalizada es PSPACE-difícil.
//
// La fórmula debe tener la forma ∃x1 ∀x2 ∃x3 … ∃xk ψ, con k impar, los cuantificadores
// alternados y ψ en CNF. normalize_for_game lleva cualquier fórmula de qbf.h a esa forma.
#ifndef FORMULA_GAME_H
#define FORMULA_GAME_H

#include <cstddef>
#include <cstdlib>
#include <stdexcept>
#include <string>
#include <vector>

#include "graph.h"
#include "qbf.h"

// ¿El prefijo empieza con ∃, alterna y termina con ∃?
inline bool has_game_form(const Qbf& f) {
    if (f.variables.empty() || f.variables.size() % 2 == 0) {
        return false;
    }
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        if (f.quantifiers[i] != (i % 2 == 0 ? 'E' : 'A')) {
            return false;
        }
    }
    return true;
}

// Una fórmula con el mismo valor y la forma que pide el juego. Donde el cuantificador que toca
// no es el de la variable siguiente, intercala una variable nueva, d1, d2…, que no aparece en
// ninguna cláusula: quien la elige no cambia nada.
inline Qbf normalize_for_game(const Qbf& f) {
    Qbf g;
    std::vector<int> new_index(f.variables.size(), 0);
    int dummies = 0;
    auto add_dummy = [&g, &dummies, &f]() {
        std::string name;
        bool taken = true;
        while (taken) {
            name = "d" + std::to_string(++dummies);
            taken = false;
            for (const std::string& used : f.variables) {
                taken = taken || used == name;
            }
        }
        g.quantifiers.push_back(g.variables.size() % 2 == 0 ? 'E' : 'A');
        g.variables.push_back(name);
    };
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        char expected = g.variables.size() % 2 == 0 ? 'E' : 'A';
        if (f.quantifiers[i] != expected) {
            add_dummy();
        }
        g.variables.push_back(f.variables[i]);
        g.quantifiers.push_back(f.quantifiers[i]);
        new_index[i] = static_cast<int>(g.variables.size());
    }
    if (g.variables.size() % 2 == 0) {
        add_dummy();  // el último cuantificador debe ser ∃ (también si no había variables)
    }
    for (const std::vector<int>& clause : f.clauses) {
        std::vector<int> renamed;
        for (int literal : clause) {
            int index = new_index[static_cast<std::size_t>(std::abs(literal)) - 1];
            renamed.push_back(literal > 0 ? index : -index);
        }
        g.clauses.push_back(renamed);
    }
    return g;
}

// El grafo de la reducción. Por cada variable x, un rombo de cuatro nodos:
//
//     x.in → x.T → x.out        x.T: se eligió x verdadera
//     x.in → x.F → x.out        x.F: se eligió x falsa
//
// El x.out de cada rombo va al x.in del siguiente, y el último va al nodo `matrix`.
// De `matrix` sale una arista a un nodo por cláusula (cl1, cl2…); de cada cláusula, una a un
// nodo por literal (cl1/1, cl1/2…); y de cada literal, una al nodo de su rombo que lo hace
// verdadero: x.T si el literal es x, x.F si es ¬x. La partida empieza en el x.in del primer rombo.
inline Graph geography_from_formula(const Qbf& f) {
    if (!has_game_form(f)) {
        throw std::runtime_error("la fórmula no tiene la forma ∃ ∀ ∃ … ∃: pásenla antes por normalize_for_game");
    }
    Graph g;
    auto add_node = [&g](const std::string& name) {
        g.nodes.push_back(name);
        g.edges.emplace_back();
        return static_cast<int>(g.nodes.size()) - 1;
    };
    std::size_t k = f.variables.size();
    std::vector<int> in(k), when_true(k), when_false(k), out(k);
    for (std::size_t i = 0; i < k; i++) {
        in[i] = add_node(f.variables[i] + ".in");
        when_true[i] = add_node(f.variables[i] + ".T");
        when_false[i] = add_node(f.variables[i] + ".F");
        out[i] = add_node(f.variables[i] + ".out");
        g.edges[in[i]] = {when_true[i], when_false[i]};
        g.edges[when_true[i]] = {out[i]};
        g.edges[when_false[i]] = {out[i]};
        if (i > 0) {
            g.edges[out[i - 1]] = {in[i]};
        }
    }
    int matrix = add_node("matrix");
    g.edges[out[k - 1]] = {matrix};
    for (std::size_t j = 0; j < f.clauses.size(); j++) {
        std::string clause_name = "cl" + std::to_string(j + 1);
        int clause_node = add_node(clause_name);
        g.edges[matrix].push_back(clause_node);
        for (std::size_t l = 0; l < f.clauses[j].size(); l++) {
            int literal = f.clauses[j][l];
            std::size_t variable = static_cast<std::size_t>(std::abs(literal)) - 1;
            int literal_node = add_node(clause_name + "/" + std::to_string(l + 1));
            g.edges[clause_node].push_back(literal_node);
            g.edges[literal_node] = {literal > 0 ? when_true[variable] : when_false[variable]};
        }
    }
    g.start = in[0];
    return g;
}

#endif
formula_to_geography.cppDescargar formula_to_geography.cpp
// La reducción del juego de la fórmula a la geografía generalizada.
//
//     formula_to_geography archivo.qbf
//
// Escribe en la salida estándar el grafo, en formato .graph, con la fórmula como comentario.
// El primer jugador gana en ese grafo si y solo si la fórmula es verdadera.
#include <iostream>
#include <stdexcept>

#include "formula_game.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: formula_to_geography archivo.qbf\n";
        return 2;
    }
    try {
        Qbf f = load_qbf(argv[1]);
        Qbf game = normalize_for_game(f);
        std::cout << "# " << to_text(f) << '\n';
        if (!has_game_form(f)) {
            std::cout << "# con la forma del juego: " << to_text(game) << '\n';
        }
        write_graph(std::cout, geography_from_formula(game));
    } catch (const std::runtime_error& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 1;
    }
    return 0;
}
geography.cppDescargar geography.cpp
// Decide quién gana una partida de geografía generalizada.
//
//     geography [--moves] archivo.graph      (con - lee el grafo de la entrada estándar)
//
// Imprime si el primer jugador tiene estrategia ganadora y una primera jugada ganadora.
// Con --moves imprime además, por cada primera jugada posible, si gana o pierde.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "geography.h"

int main(int argc, char** argv) {
    bool moves = false;
    std::string path;
    for (int i = 1; i < argc; i++) {
        std::string arg = argv[i];
        if (arg == "--moves") {
            moves = true;
        } else {
            path = arg;
        }
    }
    if (path.empty()) {
        std::cerr << "uso: geography [--moves] archivo.graph\n";
        return 2;
    }
    try {
        Graph g = path == "-" ? read_graph(std::cin) : load_graph(path);
        std::cout << g.nodes.size() << " nodos, " << edge_count(g) << " aristas, empieza en " << g.nodes[g.start]
                  << '\n';
        if (moves) {
            std::vector<bool> visited(g.nodes.size(), false);
            visited[g.start] = true;
            for (int next : g.edges[g.start]) {
                if (next == g.start) {
                    continue;
                }
                GameStats stats;
                visited[next] = true;
                bool rival_wins = mover_wins(g, next, visited, 2, stats);
                visited[next] = false;
                std::cout << "  " << g.nodes[g.start] << " → " << g.nodes[next] << ": "
                          << (rival_wins ? "pierde" : "gana") << " el primer jugador\n";
            }
        }
        GameStats stats;
        int move = winning_first_move(g, stats);
        if (move == -1) {
            std::cout << "el primer jugador no tiene estrategia ganadora\n";
        } else {
            std::cout << "el primer jugador gana; una primera jugada ganadora: " << g.nodes[move] << '\n';
        }
        std::cout << "posiciones examinadas: " << stats.calls << "   camino más largo guardado: " << stats.max_path
                  << " nodos\n";
    } catch (const std::runtime_error& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 1;
    }
    return 0;
}
geography.hDescargar geography.h
// Geografía generalizada: una ficha empieza en el nodo de partida, que cuenta como visitado.
// Los jugadores se turnan para moverla por una arista a un nodo no visitado. Pierde quien no
// puede mover.
//
// La búsqueda es recursiva y en profundidad. Guarda solo el camino actual: `visited` marca
// los nodos del camino y nada más, porque cada llamada desmarca su nodo al volver.
#ifndef GEOGRAPHY_H
#define GEOGRAPHY_H

#include <algorithm>
#include <vector>

#include "graph.h"

struct GameStats {
    long long calls = 0;  // posiciones examinadas: el tiempo
    int max_path = 0;     // el camino más largo que estuvo guardado, en nodos: el espacio
};

// ¿Tiene estrategia ganadora quien debe mover con la ficha en `current`?
// `visited` marca los nodos del camino, incluido `current`; `path_length` es cuántos son.
inline bool mover_wins(const Graph& g, int current, std::vector<bool>& visited, int path_length, GameStats& stats) {
    stats.calls++;
    stats.max_path = std::max(stats.max_path, path_length);
    for (int next : g.edges[current]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = true;
        bool rival_wins = mover_wins(g, next, visited, path_length + 1, stats);
        visited[next] = false;  // al volver, el espacio queda libre para la jugada siguiente
        if (!rival_wins) {
            return true;  // una jugada que deja al rival sin estrategia: no hace falta mirar más
        }
    }
    return false;  // no hay jugadas, o todas le dejan una estrategia ganadora al rival
}

// El resultado para el primer jugador: -1 si no tiene estrategia ganadora y, si la tiene,
// una primera jugada ganadora (la primera que aparece en la lista de aristas).
inline int winning_first_move(const Graph& g, GameStats& stats) {
    std::vector<bool> visited(g.nodes.size(), false);
    visited[g.start] = true;
    stats.calls++;
    stats.max_path = std::max(stats.max_path, 1);
    for (int next : g.edges[g.start]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = true;
        bool rival_wins = mover_wins(g, next, visited, 2, stats);
        visited[next] = false;
        if (!rival_wins) {
            return next;
        }
    }
    return -1;
}

inline bool first_player_wins(const Graph& g) {
    GameStats stats;
    return winning_first_move(g, stats) != -1;
}

// El mismo resultado por otro camino, para las pruebas: una tabla con una casilla por cada
// par (conjunto de visitados, nodo actual). Son 2^n · n casillas: tiempo y espacio exponenciales.
// Solo para grafos de hasta 20 nodos.
inline bool first_player_wins_by_table(const Graph& g) {
    int n = static_cast<int>(g.nodes.size());
    // memo[mask * n + v]: 0 sin calcular, 1 gana quien mueve, 2 pierde.
    std::vector<char> memo((std::size_t{1} << n) * static_cast<std::size_t>(n), 0);
    struct Solver {
        const Graph& g;
        int n;
        std::vector<char>& memo;
        bool wins(unsigned mask, int v) {
            char& cell = memo[static_cast<std::size_t>(mask) * static_cast<std::size_t>(n) + static_cast<std::size_t>(v)];
            if (cell != 0) {
                return cell == 1;
            }
            bool result = false;
            for (int next : g.edges[v]) {
                if ((mask >> next) & 1U) {
                    continue;
                }
                if (!wins(mask | (1U << next), next)) {
                    result = true;
                }
            }
            memo[static_cast<std::size_t>(mask) * static_cast<std::size_t>(n) + static_cast<std::size_t>(v)] = result ? 1 : 2;
            return result;
        }
    };
    Solver solver{g, n, memo};
    return solver.wins(1U << g.start, g.start);
}

#endif
graph.hDescargar graph.h
// Grafo dirigido con un nodo de partida: G = (V, E) y un nodo s.
// Es la entrada de la geografía generalizada y de PATH. Formato .graph de la semana:
//
//     # comentario
//     nodes: a b c d
//     start: a
//     edges:
//     a b
//     b c
//
// Después de `edges:` va una arista por línea, `origen destino`.
#ifndef GRAPH_H
#define GRAPH_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "fields.h"

struct Graph {
    std::vector<std::string> nodes;       // V: los nombres, en el orden del archivo
    std::vector<std::vector<int>> edges;  // E: edges[u] son los destinos de las aristas que salen de u
    int start = 0;                        // s, como posición en nodes
};

inline std::size_t edge_count(const Graph& g) {
    std::size_t m = 0;
    for (const std::vector<int>& out : g.edges) {
        m += out.size();
    }
    return m;
}

// La posición de un nodo por su nombre. Lanza std::runtime_error si no existe.
inline int node_index(const Graph& g, const std::string& name) {
    for (std::size_t i = 0; i < g.nodes.size(); i++) {
        if (g.nodes[i] == name) {
            return static_cast<int>(i);
        }
    }
    throw std::runtime_error("el nodo " + name + " no está en nodes");
}

inline Graph read_graph(std::istream& in) {
    Graph g;
    g.nodes = read_field(in, "nodes");
    if (g.nodes.empty()) {
        throw std::runtime_error("el grafo no tiene nodos");
    }
    std::map<std::string, int> index;
    for (std::size_t i = 0; i < g.nodes.size(); i++) {
        if (index.count(g.nodes[i]) != 0) {
            throw std::runtime_error("el nodo " + g.nodes[i] + " está repetido");
        }
        index[g.nodes[i]] = static_cast<int>(i);
    }
    g.edges.assign(g.nodes.size(), {});
    std::vector<std::string> start = read_field(in, "start");
    if (start.size() != 1 || index.count(start[0]) == 0) {
        throw std::runtime_error("start: lleva un nodo de nodes");
    }
    g.start = index[start[0]];
    if (!read_field(in, "edges").empty()) {
        throw std::runtime_error("después de edges: las aristas van una por línea");
    }
    std::string line;
    while (next_line(in, line)) {
        std::vector<std::string> words = split_words(line);
        if (words.size() != 2 || index.count(words[0]) == 0 || index.count(words[1]) == 0) {
            throw std::runtime_error("arista mal escrita: \"" + line + "\"");
        }
        g.edges[index[words[0]]].push_back(index[words[1]]);
    }
    return g;
}

inline Graph load_graph(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        throw std::runtime_error(path + ": no se pudo abrir");
    }
    try {
        return read_graph(in);
    } catch (const std::runtime_error& e) {
        throw std::runtime_error(path + ": " + e.what());
    }
}

inline void write_graph(std::ostream& out, const Graph& g) {
    out << "nodes:";
    for (const std::string& name : g.nodes) {
        out << ' ' << name;
    }
    out << "\nstart: " << g.nodes[g.start] << "\nedges:\n";
    for (std::size_t u = 0; u < g.nodes.size(); u++) {
        for (int v : g.edges[u]) {
            out << g.nodes[u] << ' ' << g.nodes[v] << '\n';
        }
    }
}

#endif
guess_path.cppDescargar guess_path.cpp
// 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;
}
qbf_growth.cppDescargar qbf_growth.cpp
// Tiempo y espacio de la recursión de TQBF con una familia de fórmulas verdaderas:
//
//     ∀x1 ∃y1 ∀x2 ∃y2 … ∀xk ∃yk  ((x1 ∨ y1) ∧ (¬x1 ∨ ¬y1) ∧ … ∧ (xk ∨ yk) ∧ (¬xk ∨ ¬yk))
//
// Cada par de cláusulas dice que yi es distinta de xi. Las llamadas crecen exponencialmente
// con k; las llamadas activas a la vez, linealmente.
#include <cstdio>
#include <string>

#include "qbf.h"

static Qbf different_pairs(int k) {
    Qbf f;
    for (int i = 1; i <= k; i++) {
        f.variables.push_back("x" + std::to_string(i));
        f.quantifiers.push_back('A');
        f.variables.push_back("y" + std::to_string(i));
        f.quantifiers.push_back('E');
        f.clauses.push_back({2 * i - 1, 2 * i});
        f.clauses.push_back({-(2 * i - 1), -(2 * i)});
    }
    return f;
}

int main() {
    std::printf("%s\n\n", to_text(different_pairs(2)).c_str());
    std::printf(" k   variables   valor       llamadas   activas a la vez\n");
    for (int k = 1; k <= 12; k++) {
        Qbf f = different_pairs(k);
        EvalStats stats;
        bool value = is_true(f, stats);
        std::printf("%2d   %9d   %-9s %10lld   %16d\n", k, 2 * k, value ? "verdadero" : "falso", stats.calls,
                    stats.max_depth);
    }
    return 0;
}
qbf.hDescargar qbf.h
// Fórmulas booleanas cuantificadas en forma prenex, con la parte sin cuantificadores en CNF:
//
//     φ = Q1 x1 Q2 x2 … Qm xm ψ,   con cada Qi igual a ∃ o a ∀ y ψ una conjunción de cláusulas.
//
// El struct tiene las tres partes: las variables en el orden del prefijo, el cuantificador de
// cada una y las cláusulas. Además: leer y escribir el formato .qbf de la semana y evaluar la
// fórmula con la recursión que muestra que TQBF está en PSPACE.
#ifndef QBF_H
#define QBF_H

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "fields.h"

struct Qbf {
    std::vector<std::string> variables;     // x1 … xm, en el orden del prefijo
    std::vector<char> quantifiers;          // quantifiers[i] es 'E' (∃) o 'A' (∀), el de variables[i]
    std::vector<std::vector<int>> clauses;  // ψ: el literal xi es i (desde 1) y ¬xi es -i
};

// ------------------------------------------------------------
// Leer y escribir el formato .qbf
// ------------------------------------------------------------
//
//     # ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y))
//     prefix: A x E y
//     clauses:
//     x y
//     -x -y
//
// `prefix:` lleva el prefijo de izquierda a derecha: una letra, A o E, y el nombre de la variable.
// Después de `clauses:` va una cláusula por línea; un literal negado lleva un guion delante.

inline Qbf read_qbf(std::istream& in) {
    Qbf f;
    std::vector<std::string> prefix = read_field(in, "prefix");
    if (prefix.size() % 2 != 0) {
        throw std::runtime_error("prefix: lleva pares de cuantificador y variable");
    }
    std::map<std::string, int> index;
    for (std::size_t i = 0; i < prefix.size(); i += 2) {
        if (prefix[i] != "A" && prefix[i] != "E") {
            throw std::runtime_error("el cuantificador es A o E, y se leyó " + prefix[i]);
        }
        const std::string& name = prefix[i + 1];
        if (name[0] == '-') {
            throw std::runtime_error("el nombre de una variable no empieza con guion: " + name);
        }
        if (index.count(name) != 0) {
            throw std::runtime_error("la variable " + name + " está cuantificada dos veces");
        }
        f.variables.push_back(name);
        f.quantifiers.push_back(prefix[i][0]);
        index[name] = static_cast<int>(f.variables.size());
    }
    if (!read_field(in, "clauses").empty()) {
        throw std::runtime_error("después de clauses: las cláusulas van una por línea");
    }
    std::string line;
    while (next_line(in, line)) {
        std::vector<int> clause;
        for (const std::string& word : split_words(line)) {
            bool negated = word[0] == '-';
            std::string name = negated ? word.substr(1) : word;
            if (index.count(name) == 0) {
                throw std::runtime_error("la variable " + name +
                                         " no tiene cuantificador: la fórmula no está totalmente cuantificada");
            }
            clause.push_back(negated ? -index[name] : index[name]);
        }
        f.clauses.push_back(clause);
    }
    return f;
}

inline Qbf load_qbf(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        throw std::runtime_error(path + ": no se pudo abrir");
    }
    try {
        return read_qbf(in);
    } catch (const std::runtime_error& e) {
        throw std::runtime_error(path + ": " + e.what());
    }
}

inline void write_qbf(std::ostream& out, const Qbf& f) {
    out << "prefix:";
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        out << ' ' << f.quantifiers[i] << ' ' << f.variables[i];
    }
    out << "\nclauses:\n";
    for (const std::vector<int>& clause : f.clauses) {
        for (std::size_t k = 0; k < clause.size(); k++) {
            int literal = clause[k];
            out << (k > 0 ? " " : "") << (literal < 0 ? "-" : "") << f.variables[std::abs(literal) - 1];
        }
        out << '\n';
    }
}

// La fórmula como se escribe en la pizarra: ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y)).
inline std::string to_text(const Qbf& f) {
    std::string text;
    for (std::size_t i = 0; i < f.variables.size(); i++) {
        text += (f.quantifiers[i] == 'E' ? "∃" : "∀") + f.variables[i] + " ";
    }
    if (f.clauses.empty()) {
        return text + "(verdadero)";
    }
    text += "(";
    for (std::size_t j = 0; j < f.clauses.size(); j++) {
        text += (j > 0 ? " ∧ (" : "(");
        for (std::size_t k = 0; k < f.clauses[j].size(); k++) {
            int literal = f.clauses[j][k];
            text += (k > 0 ? " ∨ " : "");
            text += (literal < 0 ? "¬" : "") + f.variables[std::abs(literal) - 1];
        }
        text += ")";
    }
    return text + ")";
}

// ------------------------------------------------------------
// Evaluar
// ------------------------------------------------------------

// ψ con una asignación completa: todas las cláusulas tienen algún literal verdadero.
inline bool matrix_value(const Qbf& f, const std::vector<bool>& values) {
    for (const std::vector<int>& clause : f.clauses) {
        bool satisfied = false;
        for (int literal : clause) {
            bool value = values[std::abs(literal) - 1];
            satisfied = satisfied || (literal > 0 ? value : !value);
        }
        if (!satisfied) {
            return false;
        }
    }
    return true;
}

// Lo que se mide de una evaluación.
struct EvalStats {
    long long calls = 0;   // llamadas a evaluate: el tiempo
    int max_depth = 0;     // llamadas activas a la vez, como máximo: el espacio
};

// El valor de Qi xi … Qm xm ψ cuando x1 … x(i-1) ya tienen los valores de `values`.
// Prueba xi = 0 y xi = 1 en el mismo vector: la segunda prueba reutiliza el espacio de la primera.
inline bool evaluate(const Qbf& f, std::vector<bool>& values, std::size_t i, EvalStats& stats) {
    stats.calls++;
    stats.max_depth = std::max(stats.max_depth, static_cast<int>(i) + 1);
    if (i == f.variables.size()) {
        return matrix_value(f, values);
    }
    values[i] = false;
    bool with_false = evaluate(f, values, i + 1, stats);
    if (f.quantifiers[i] == 'E' && with_false) {
        return true;   // ∃: basta un valor
    }
    if (f.quantifiers[i] == 'A' && !with_false) {
        return false;  // ∀: basta un valor que falle
    }
    values[i] = true;
    return evaluate(f, values, i + 1, stats);
}

inline bool is_true(const Qbf& f, EvalStats& stats) {
    std::vector<bool> values(f.variables.size(), false);
    return evaluate(f, values, 0, stats);
}

inline bool is_true(const Qbf& f) {
    EvalStats stats;
    return is_true(f, stats);
}

// El mismo valor por otro camino, para las pruebas: la tabla con el valor de ψ en las 2^m
// asignaciones, que se pliega de la última variable a la primera (∃ es "o", ∀ es "y").
// Guarda 2^m valores: es justo el espacio que la recursión evita.
inline bool is_true_by_table(const Qbf& f) {
    std::size_t m = f.variables.size();
    std::vector<bool> table(std::size_t{1} << m);
    std::vector<bool> values(m);
    for (std::size_t row = 0; row < table.size(); row++) {
        for (std::size_t i = 0; i < m; i++) {
            values[i] = ((row >> (m - 1 - i)) & 1) != 0;  // x1 es el bit más alto
        }
        table[row] = matrix_value(f, values);
    }
    for (std::size_t i = m; i-- > 0;) {
        std::vector<bool> folded(table.size() / 2);
        for (std::size_t row = 0; row < folded.size(); row++) {
            bool a = table[2 * row];
            bool b = table[2 * row + 1];
            folded[row] = f.quantifiers[i] == 'E' ? (a || b) : (a && b);
        }
        table = folded;
    }
    return table[0];
}

#endif
savitch_demo.cppDescargar savitch_demo.cpp
// La recursión de Savitch frente a BFS, con números.
//
//     savitch_demo                      la tabla con los caminos de 4, 8, 16 y 32 nodos
//     savitch_demo archivo.graph nodo   ¿se llega del nodo de partida a ese nodo?
//
// En el camino v0 → v1 → … → v(n-1) se pregunta si de v0 se llega a v(n-1).
// Lo que guarda cada algoritmo se cuenta en bits, con ⌈log2 n⌉ bits por nodo:
//   Savitch: por cada llamada activa, tres nodos (origen, destino y punto medio) y el exponente de t.
//   BFS: un bit de visitado por nodo, más los nodos de la cola.
#include <cstdio>
#include <iostream>
#include <stdexcept>
#include <string>

#include "savitch.h"

static Graph path_graph(int n) {
    Graph g;
    for (int i = 0; i < n; i++) {
        g.nodes.push_back("v" + std::to_string(i));
        g.edges.emplace_back();
        if (i > 0) {
            g.edges[i - 1].push_back(i);
        }
    }
    g.start = 0;
    return g;
}

static long long savitch_bits(long long n, long long t, int depth) {
    int exponent_bits = bits_for(bits_for(t) + 1);
    return static_cast<long long>(depth) * (3 * bits_for(n) + exponent_bits);
}

static void compare(const Graph& g, int target, bool header) {
    long long n = static_cast<long long>(g.nodes.size());
    long long t = power_of_two_at_least(n);
    SavitchStats savitch;
    bool by_savitch = can_yield(g, g.start, target, t, 1, savitch);
    BfsStats bfs;
    bool by_bfs = bfs_reaches(g, g.start, target, bfs);
    if (by_savitch != by_bfs) {
        throw std::runtime_error("las dos respuestas no coinciden");
    }
    if (header) {
        std::printf("   n     t   llega   Savitch: llamadas  activas  bits   BFS: aristas  cola  bits\n");
    }
    std::printf("%4lld  %4lld   %-5s   %17lld  %7d  %4lld   %12lld  %4d  %4lld\n", n, t, by_bfs ? "sí" : "no",
                savitch.calls, savitch.max_depth, savitch_bits(n, t, savitch.max_depth), bfs.steps, bfs.max_queue,
                n + static_cast<long long>(bfs.max_queue) * bits_for(n));
}

int main(int argc, char** argv) {
    try {
        if (argc == 3) {
            Graph g = load_graph(argv[1]);
            compare(g, node_index(g, argv[2]), true);
            return 0;
        }
        bool header = true;
        for (int n : {4, 8, 16, 32}) {
            compare(path_graph(n), n - 1, header);
            header = false;
        }
    } catch (const std::runtime_error& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 1;
    }
    return 0;
}
savitch.hDescargar savitch.h
// La recursión del teorema de Savitch sobre un grafo explícito, comparada con BFS.
//
// can_yield(g, u, v, t) responde si hay un camino de u a v con a lo sumo t aristas, con t una
// potencia de 2. No marca nodos visitados: prueba cada nodo como punto medio y resuelve las
// dos mitades, una después de la otra, en el mismo espacio.
#ifndef SAVITCH_H
#define SAVITCH_H

#include <algorithm>
#include <queue>
#include <vector>

#include "graph.h"

struct SavitchStats {
    long long calls = 0;  // llamadas a can_yield: el tiempo
    int max_depth = 0;    // llamadas activas a la vez, como máximo: el espacio
};

inline bool has_edge(const Graph& g, int u, int v) {
    return std::find(g.edges[u].begin(), g.edges[u].end(), v) != g.edges[u].end();
}

inline bool can_yield(const Graph& g, int u, int v, long long t, int depth, SavitchStats& stats) {
    stats.calls++;
    stats.max_depth = std::max(stats.max_depth, depth);
    if (t == 1) {
        return u == v || has_edge(g, u, v);
    }
    int n = static_cast<int>(g.nodes.size());
    for (int middle = 0; middle < n; middle++) {
        // Las dos llamadas usan el mismo espacio: la segunda empieza cuando la primera terminó.
        if (can_yield(g, u, middle, t / 2, depth + 1, stats) && can_yield(g, middle, v, t / 2, depth + 1, stats)) {
            return true;
        }
    }
    return false;
}

// La menor potencia de 2 que es mayor o igual que n.
inline long long power_of_two_at_least(long long n) {
    long long t = 1;
    while (t < n) {
        t *= 2;
    }
    return t;
}

// Cuántos bits hacen falta para escribir un número entre 0 y n - 1.
inline int bits_for(long long n) {
    int bits = 1;
    while ((1LL << bits) < n) {
        bits++;
    }
    return bits;
}

struct BfsStats {
    long long steps = 0;  // aristas examinadas: el tiempo
    int max_queue = 0;    // nodos en la cola a la vez, como máximo
};

// ¿Hay un camino de u a v? Con la marca de visitados y la cola de siempre.
inline bool bfs_reaches(const Graph& g, int u, int v, BfsStats& stats) {
    std::vector<bool> visited(g.nodes.size(), false);
    std::queue<int> pending;
    visited[u] = true;
    pending.push(u);
    stats.max_queue = 1;
    while (!pending.empty()) {
        int x = pending.front();
        pending.pop();
        if (x == v) {
            return true;
        }
        for (int y : g.edges[x]) {
            stats.steps++;
            if (!visited[y]) {
                visited[y] = true;
                pending.push(y);
                stats.max_queue = std::max(stats.max_queue, static_cast<int>(pending.size()));
            }
        }
    }
    return false;
}

#endif
machines/cities.graphDescargar machines/cities.graph
# Geografía con nueve ciudades del Perú. Hay una arista de una ciudad a otra cuando la segunda
# empieza con la letra en que termina la primera. La partida empieza en lima.
nodes: lima arequipa abancay ayacucho andahuaylas yurimaguas sullana satipo oxapampa
start: lima
edges:
lima arequipa
lima abancay
lima ayacucho
lima andahuaylas
arequipa abancay
arequipa ayacucho
arequipa andahuaylas
abancay yurimaguas
ayacucho oxapampa
andahuaylas sullana
andahuaylas satipo
yurimaguas sullana
yurimaguas satipo
sullana arequipa
sullana abancay
sullana ayacucho
sullana andahuaylas
satipo oxapampa
oxapampa arequipa
oxapampa abancay
oxapampa ayacucho
oxapampa andahuaylas
machines/exists_forall.qbfDescargar machines/exists_forall.qbf
# ∃y ∀x ((x ∨ y) ∧ (¬x ∨ ¬y)): hay una y distinta de las dos x. Falsa.
prefix: E y A x
clauses:
x y
-x -y
machines/forall_exists.qbfDescargar machines/forall_exists.qbf
# ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y)): para cada x hay una y distinta. Verdadera.
prefix: A x E y
clauses:
x y
-x -y
machines/sat_example.qbfDescargar machines/sat_example.qbf
# Solo ∃: es una instancia de SAT. Satisfacible con x = 1, y = 0, z = 1.
prefix: E x E y E z
clauses:
x y
-x -y
-x z
y z
machines/small_game.graphDescargar machines/small_game.graph
# Un juego de cinco nodos para resolver a mano.
nodes: a b c d e
start: a
edges:
a b
a c
b d
c d
c e
d a
d e
machines/three_moves.qbfDescargar machines/three_moves.qbf
# ∃x ∀y ∃z ((x ∨ y) ∧ (¬y ∨ z) ∧ (¬x ∨ ¬z ∨ y)): un juego de tres jugadas. Verdadera.
prefix: E x A y E z
clauses:
x y
-y z
-x -z y
machines/two_routes.graphDescargar machines/two_routes.graph
# Para PATH: de s se llega a t, y de t no se llega a s.
nodes: s a b c t u
start: s
edges:
s a
a b
b a
b c
c t
u s
u t
machines/unsat_example.qbfDescargar machines/unsat_example.qbf
# Solo ∃, y no satisfacible: las cuatro cláusulas prohíben las cuatro asignaciones.
prefix: E x E y
clauses:
x y
x -y
-x y
-x -y

Errores

Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.

errors/bad_quantifier.qbfDescargar errors/bad_quantifier.qbf
# Error intencional: el cuantificador se escribe A o E.
prefix: forall x E y
clauses:
x y
errors/free_variable.qbfDescargar errors/free_variable.qbf
# Error intencional: z no tiene cuantificador, así que la fórmula no es verdadera ni falsa.
prefix: A x E y
clauses:
x y
-x z
errors/unknown_node.graphDescargar errors/unknown_node.graph
# Error intencional: la arista usa un nodo que no está en nodes.
nodes: a b
start: a
edges:
a b
b c

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_formula_game.cppDescargar test_formula_game.cpp
// Pruebas de la reducción del juego de la fórmula a la geografía generalizada: el primer
// jugador gana en el grafo exactamente cuando la fórmula es verdadera.
#include <cassert>
#include <cstdio>
#include <random>
#include <set>
#include <string>

#include "formula_game.h"
#include "geography.h"

static std::size_t literal_count(const Qbf& f) {
    std::size_t total = 0;
    for (const std::vector<int>& clause : f.clauses) {
        total += clause.size();
    }
    return total;
}

static void check(const Qbf& f) {
    Qbf game = normalize_for_game(f);
    assert(has_game_form(game));
    assert(is_true(game) == is_true(f));  // las variables nuevas no cambian el valor
    assert(game.variables.size() <= 2 * f.variables.size() + 1);
    Graph g = geography_from_formula(game);
    // Tamaño: cuatro nodos por variable, uno para la matriz, uno por cláusula y uno por literal.
    assert(g.nodes.size() == 4 * game.variables.size() + 1 + game.clauses.size() + literal_count(game));
    assert(std::set<std::string>(g.nodes.begin(), g.nodes.end()).size() == g.nodes.size());
    assert(first_player_wins(g) == is_true(f));
}

int main() {
    // Las dos fórmulas de la clase.
    Qbf forall_exists = load_qbf("machines/forall_exists.qbf");
    Qbf exists_forall = load_qbf("machines/exists_forall.qbf");
    assert(!has_game_form(forall_exists) && !has_game_form(exists_forall));
    assert(to_text(normalize_for_game(forall_exists)) == "∃d1 ∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y))");
    assert(to_text(normalize_for_game(exists_forall)) == "∃y ∀x ∃d1 ((x ∨ y) ∧ (¬x ∨ ¬y))");
    Graph g1 = geography_from_formula(normalize_for_game(forall_exists));
    Graph g2 = geography_from_formula(normalize_for_game(exists_forall));
    assert(g1.nodes.size() == 19 && g2.nodes.size() == 19);
    assert(edge_count(g1) == 25);
    assert(first_player_wins(g1));
    assert(!first_player_wins(g2));

    // El juego de tres jugadas ya tiene la forma pedida.
    Qbf three = load_qbf("machines/three_moves.qbf");
    assert(has_game_form(three));
    Graph g3 = geography_from_formula(three);
    assert(g3.nodes.size() == 23);
    assert(first_player_wins(g3) && is_true(three));

    check(load_qbf("machines/sat_example.qbf"));
    check(load_qbf("machines/unsat_example.qbf"));
    check(Qbf{});  // sin variables ni cláusulas: verdadera

    // Fórmulas al azar con hasta 5 variables y hasta 5 cláusulas.
    std::mt19937 rng(2014);
    const int total = 1500;
    int trues = 0;
    for (int k = 0; k < total; k++) {
        Qbf f;
        int m = 1 + static_cast<int>(rng() % 5);
        for (int i = 0; i < m; i++) {
            f.variables.push_back("x" + std::to_string(i + 1));
            f.quantifiers.push_back(rng() % 2 == 0 ? 'E' : 'A');
        }
        int clauses = static_cast<int>(rng() % 6);
        for (int j = 0; j < clauses; j++) {
            std::vector<int> clause;
            int size = 1 + static_cast<int>(rng() % 3);
            for (int l = 0; l < size; l++) {
                int variable = 1 + static_cast<int>(rng() % m);
                clause.push_back(rng() % 2 == 0 ? variable : -variable);
            }
            f.clauses.push_back(clause);
        }
        check(f);
        trues += is_true(f);
    }
    assert(trues > total / 10 && trues < total - total / 10);
    std::printf("test_formula_game: las fórmulas de la clase y %d fórmulas al azar (%d verdaderas)\n", total, trues);
    return 0;
}
test_geography.cppDescargar test_geography.cpp
// 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;
}
test_qbf.cppDescargar test_qbf.cpp
// Pruebas de lo que los apuntes afirman sobre las fórmulas cuantificadas.
#include <cassert>
#include <cstdio>
#include <random>
#include <sstream>
#include <stdexcept>
#include <string>

#include "qbf.h"

static bool fails_to_load(const std::string& path, const std::string& piece) {
    try {
        load_qbf(path);
    } catch (const std::runtime_error& e) {
        return std::string(e.what()).find(piece) != std::string::npos;
    }
    return false;
}

// Una fórmula al azar con m variables y a lo sumo max_clauses cláusulas de 1 a 3 literales.
static Qbf random_qbf(std::mt19937& rng, int m, int max_clauses) {
    Qbf f;
    for (int i = 0; i < m; i++) {
        f.variables.push_back("x" + std::to_string(i + 1));
        f.quantifiers.push_back(rng() % 2 == 0 ? 'E' : 'A');
    }
    int clauses = static_cast<int>(rng() % (max_clauses + 1));
    for (int j = 0; j < clauses; j++) {
        std::vector<int> clause;
        int size = 1 + static_cast<int>(rng() % 3);
        for (int l = 0; l < size; l++) {
            int variable = 1 + static_cast<int>(rng() % m);
            clause.push_back(rng() % 2 == 0 ? variable : -variable);
        }
        f.clauses.push_back(clause);
    }
    return f;
}

int main() {
    // Las dos fórmulas de la clase: el orden de los cuantificadores cambia el valor.
    Qbf forall_exists = load_qbf("machines/forall_exists.qbf");
    Qbf exists_forall = load_qbf("machines/exists_forall.qbf");
    assert(to_text(forall_exists) == "∀x ∃y ((x ∨ y) ∧ (¬x ∨ ¬y))");
    assert(to_text(exists_forall) == "∃y ∀x ((x ∨ y) ∧ (¬x ∨ ¬y))");
    assert(is_true(forall_exists));
    assert(!is_true(exists_forall));
    assert(forall_exists.clauses.size() == exists_forall.clauses.size());  // la misma ψ

    // Con solo ∃, la fórmula es verdadera exactamente cuando ψ es satisfacible.
    Qbf sat = load_qbf("machines/sat_example.qbf");
    assert(is_true(sat));
    std::vector<bool> witness = {true, false, true};  // x = 1, y = 0, z = 1
    assert(matrix_value(sat, witness));
    assert(!is_true(load_qbf("machines/unsat_example.qbf")));

    // El juego de tres jugadas.
    assert(is_true(load_qbf("machines/three_moves.qbf")));

    // Lo que se mide: con m variables hay a lo sumo m + 1 llamadas activas a la vez.
    EvalStats stats;
    is_true(forall_exists, stats);
    assert(stats.max_depth == 3);
    assert(stats.calls == 6);
    EvalStats unsat_stats;
    is_true(load_qbf("machines/unsat_example.qbf"), unsat_stats);
    assert(unsat_stats.calls == 7);  // el árbol completo: 1 + 2 + 4
    assert(unsat_stats.max_depth == 3);

    // Una fórmula sin cláusulas es verdadera; una con variables sin cuantificador no es una entrada.
    Qbf empty;
    assert(is_true(empty));
    assert(fails_to_load("errors/free_variable.qbf", "no está totalmente cuantificada"));
    assert(fails_to_load("errors/bad_quantifier.qbf", "el cuantificador es A o E"));

    // Escribir y volver a leer da la misma fórmula.
    std::ostringstream out;
    write_qbf(out, sat);
    std::istringstream in(out.str());
    Qbf again = read_qbf(in);
    assert(again.variables == sat.variables && again.quantifiers == sat.quantifiers && again.clauses == sat.clauses);

    // La recursión y la tabla de 2^m filas dan el mismo valor en fórmulas al azar.
    std::mt19937 rng(14);
    int trues = 0;
    const int total = 3000;
    for (int k = 0; k < total; k++) {
        int m = 1 + static_cast<int>(rng() % 7);
        Qbf f = random_qbf(rng, m, 8);
        EvalStats s;
        bool value = is_true(f, s);
        assert(value == is_true_by_table(f));
        assert(s.max_depth <= m + 1);
        assert(s.calls <= (2LL << m) - 1);
        trues += value;
    }
    assert(trues > total / 10 && trues < total - total / 10);

    std::printf("test_qbf: las fórmulas de la clase y %d fórmulas al azar (%d verdaderas)\n", total, trues);
    return 0;
}
test_savitch.cppDescargar test_savitch.cpp
// Pruebas de la recursión de Savitch sobre grafos: responde lo mismo que BFS y su profundidad
// es log2 t + 1.
#include <cassert>
#include <cstdio>
#include <queue>
#include <random>
#include <string>
#include <vector>

#include "savitch.h"

// La distancia de u a v en aristas, o -1 si no se llega.
static int distance(const Graph& g, int u, int v) {
    std::vector<int> dist(g.nodes.size(), -1);
    std::queue<int> pending;
    dist[u] = 0;
    pending.push(u);
    while (!pending.empty()) {
        int x = pending.front();
        pending.pop();
        for (int y : g.edges[x]) {
            if (dist[y] == -1) {
                dist[y] = dist[x] + 1;
                pending.push(y);
            }
        }
    }
    return dist[v];
}

int main() {
    assert(power_of_two_at_least(1) == 1 && power_of_two_at_least(5) == 8 && power_of_two_at_least(8) == 8);
    assert(bits_for(2) == 1 && bits_for(8) == 3 && bits_for(9) == 4 && bits_for(1024) == 10);

    // El grafo de PATH de los apuntes.
    Graph routes = load_graph("machines/two_routes.graph");
    int s = node_index(routes, "s");
    int t = node_index(routes, "t");
    SavitchStats stats;
    assert(can_yield(routes, s, t, 8, 1, stats));
    assert(stats.max_depth == 4);  // t = 8, 4, 2, 1
    SavitchStats back;
    assert(!can_yield(routes, t, s, 8, 1, back));
    assert(distance(routes, s, t) == 4);
    SavitchStats short_stats;
    assert(!can_yield(routes, s, t, 2, 1, short_stats));  // con 2 aristas no alcanza
    assert(can_yield(routes, s, t, 4, 1, short_stats));

    // can_yield(u, v, t) es verdadero exactamente cuando la distancia de u a v es a lo sumo t.
    std::mt19937 rng(8);
    int checked = 0;
    for (int k = 0; k < 300; k++) {
        int n = 1 + static_cast<int>(rng() % 7);
        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 (rng() % 100 < 25) {
                    g.edges[u].push_back(v);
                }
            }
        }
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                int d = distance(g, u, v);
                for (long long steps = 1; steps <= 8; steps *= 2) {
                    SavitchStats st;
                    bool expected = d != -1 && d <= steps;
                    assert(can_yield(g, u, v, steps, 1, st) == expected);
                    int levels = 1;
                    for (long long x = steps; x > 1; x /= 2) {
                        levels++;
                    }
                    assert(st.max_depth <= levels);
                    checked++;
                }
                BfsStats bfs;
                assert(bfs_reaches(g, u, v, bfs) == (d != -1));
            }
        }
    }
    std::printf("test_savitch: el grafo de la clase y %d consultas en grafos al azar\n", checked);
    return 0;
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/geography/MakefileDescargar lab/geography/Makefile
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk
lab/geography/README.mdDescargar lab/geography/README.md
# Quién gana en geografía generalizada

Ejercicio opcional de la semana 14: la sesión de laboratorio es para la Práctica 4.

La geografía generalizada se juega en un grafo dirigido con un nodo de partida:

- Una ficha empieza en el nodo de partida, que **cuenta como visitado**.
- Los dos jugadores se turnan. En su turno, un jugador mueve la ficha por una arista a un nodo **no
  visitado**, que queda visitado.
- El jugador que no puede mover **pierde**.

Tienen que decidir si el primer jugador tiene una estrategia ganadora: una manera de jugar con la que gana
haga lo que haga el otro. Si la tiene, además dicen con qué jugada empieza.

El problema es PSPACE-completo, como se demuestra en los apuntes. No se conoce ningún algoritmo de tiempo
polinomial, y no se les pide uno. Se les pide la búsqueda que muestra que el problema **está** en PSPACE: una
recursión que guarda solo el camino actual.

## Entrada

Un grafo en el formato `.graph` de la semana, que sigue las reglas comunes de
[`code/formats.md`](../../../formats.md):

```text
# Un juego de cinco nodos.
nodes: a b c d e
start: a
edges:
a b
a c
b d
c d
c e
d a
d e
```

- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea, también entre
  las aristas.
- Puede haber líneas vacías antes de `edges:`. Después de `edges:` no hay líneas vacías.
- `nodes:`, `start:` y `edges:` vienen siempre en ese orden. `nodes:` lleva los nombres de los nodos,
  separados por espacios, y `start:`, el nodo de partida.
- Después de `edges:` hay una arista por línea, `origen destino`, en cualquier orden. Puede no haber ninguna.

## Salida

Una sola línea:

- `gana v`, si el primer jugador tiene una estrategia ganadora, donde `v` es el nodo al que mueve en su
  **primera jugada** de una estrategia ganadora;
- `pierde`, si no la tiene.

Puede haber varias primeras jugadas ganadoras. **Se acepta cualquiera**: el juez usa un verificador, que
comprueba que `v` es un nodo no visitado al que se llega con una arista desde el nodo de partida y que, después
de esa jugada, el segundo jugador no tiene estrategia ganadora. No hace falta que coincida con la de
`casos/NN.out`.

## Límites

- Entre 1 y 20 nodos.
- El nombre de un nodo tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#` ni termina con
  `:`. Un nombre puede ser prefijo de otro (`q1` y `q11`), y puede ser una palabra del formato o de la salida:
  un nodo se puede llamar `nodes`, `edges` o `gana`.
- No hay aristas repetidas ni aristas de un nodo a sí mismo.
- La entrada siempre es un grafo válido: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba, la salida es:

```text
gana b
```

Si el primer jugador mueve a `b`, el segundo solo puede mover a `d`. Desde `d`, la arista a `a` no sirve,
porque `a` ya está visitado; el primer jugador mueve a `e`, y el segundo se queda sin jugada. En cambio, la
jugada `c` pierde: el segundo responde `e`, y el primero no puede mover. Aquí `gana b` es la única respuesta
correcta.

Un caso que suele fallar es `casos/05.in`, con las aristas `a b`, `b c` y `c a` y la partida en `a`: la
respuesta es `pierde`, porque la arista de `c` a `a` vuelve al nodo de partida, que ya está visitado.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Con 20 nodos hay grafos en los que cualquier búsqueda de este tipo tarda demasiado: el problema es
PSPACE-completo y no hay milagros. Los casos del juez están elegidos para que la búsqueda esperada termine a
tiempo:

- En todos los casos, una búsqueda que **deja de probar jugadas en cuanto encuentra una ganadora** examina
  menos de 3 millones de posiciones. Lo comprobamos con el orden de las aristas de la entrada y con varios
  órdenes al azar, porque el número depende del orden en que se prueban las jugadas. La solución de referencia
  hace eso, y su caso más lento tardó 0,15 s en el entorno del curso.
- Una búsqueda que **sigue probando las demás jugadas** aunque ya encontró una ganadora da la misma respuesta,
  pero recorre todos los caminos sin nodos repetidos que salen del nodo de partida. En el caso 13, el grafo
  completo de 13 nodos, son más de 1300 millones de posiciones. Esa solución da `TLE` en los casos 13 a 20.
- Pasar el grafo y el conjunto de visitados **por valor** hace que cada llamada los copie enteros. Una
  solución así, que por lo demás era correcta y cortaba al encontrar una jugada ganadora, tardó 6 s en el caso
  15 y dio `TLE`. Usen **una sola** copia de las marcas de visitado, pasada por referencia: cada llamada marca
  su nodo y lo desmarca al volver.

## Cómo avanzar

```sh
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

1. Lean el grafo. Lean por líneas, con `std::getline`, y separen las palabras de cada línea. Guarden cada nodo
   por su posición en la lista de `nodes:`, para no comparar nombres durante la búsqueda. El esqueleto trae un
   `struct Graph` con una propuesta de tipos.
2. Escriban la función recursiva `mover_wins`: ¿tiene estrategia ganadora quien debe mover con la ficha en
   este nodo? La tiene si **alguna** de sus jugadas lleva a una posición en la que el otro **no** la tiene. Si
   no hay jugadas, no la tiene. Lo único que guarda la búsqueda es qué nodos están en el camino actual.
3. Respondan por el primer jugador: prueben cada jugada desde el nodo de partida y, si alguna gana, imprímanla.
   Empiecen con `casos/01.in` y con los casos del 02 al 05, que son los bordes: un solo nodo, un nodo de
   partida sin aristas, un ciclo que vuelve a la partida.
4. Midan cómo crece el tiempo. La sección siguiente dice cómo.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

Los casos 10 y 11 son los grafos que la reducción de los apuntes construye para las fórmulas
$\forall x\, \exists y\, ((x \lor y) \land (\lnot x \lor \lnot y))$, que es verdadera, y
$\exists y\, \forall x\, ((x \lor y) \land (\lnot x \lor \lnot y))$, que es falsa. Su programa, sin saber nada
de fórmulas, las está evaluando.

## Cómo crece el tiempo

El paso 4 es una medición. El grafo completo de $n$ nodos, con una arista de cada nodo a cada uno de los
otros, es un buen caso de prueba porque en él nadie se queda sin jugada antes de tiempo: toda partida dura
$n - 1$ jugadas. Escriban un programa pequeño que lo genere en formato `.graph`, o háganlo en el shell:

```sh
n=15
{ echo "nodes: $(seq -s ' ' 1 $n)"; echo "start: 1"; echo "edges:"
  for u in $(seq 1 $n); do for v in $(seq 1 $n); do [ $u != $v ] && echo "$u $v"; done; done; } > k$n.graph
time build/solution < k$n.graph
```

Para contar posiciones sin tocar su programa pueden usar el de los apuntes, que lee el mismo formato:
`../../build/geography k15.graph` (antes corran `make` en `code/week-14`).

Estas son las mediciones de la solución de referencia. Las posiciones no dependen de la máquina. Los tiempos
sí: son la mediana de tres corridas en el contenedor del curso, compilando con `-O2`, en una laptop que estaba
ocupada con otras tareas. En la suya van a salir otros números.

| Nodos | Respuesta | Posiciones examinadas | Tiempo |
|---|---|---|---|
| 10 | `gana` | 1266 | 0,004 s |
| 15 | `pierde` | 2 127 245 | 0,034 s |
| 20 | `gana` | 612 646 886 | 11,6 s |

De 10 a 15 nodos las posiciones se multiplican por unas 1700, y de 15 a 20 por unas 290. Cinco nodos más
cuestan cientos de veces más: eso es tiempo exponencial. El grafo completo de 20 nodos ya no entra en 2
segundos, y por eso el caso más grande de ese tipo que hay en el juez es el de 16 nodos.

El espacio, en cambio, casi no se mueve: el camino más largo que la búsqueda tiene guardado es de 10, 15 y 20
nodos.

Anoten sus propias mediciones y respondan:

1. ¿Por cuánto se multiplica el tiempo de su programa de 10 a 15 nodos, y de 15 a 20? Si el de 20 tarda
   demasiado, midan con 16, 17 y 18.
2. Sin la poda, la búsqueda recorre todos los caminos sin nodos repetidos que salen del nodo de partida. En el
   grafo completo de $n$ nodos son

   $$
   \sum_{k=0}^{n-1} \frac{(n-1)!}{(n-1-k)!},
   $$

   un camino por cada lista ordenada de $k$ nodos distintos elegidos entre los otros $n - 1$. Para $n = 10$
   da 986 410. Calculen el valor para $n = 15$ y estimen cuánto tardaría su programa sin la poda.
3. ¿Por qué las filas de 10 y de 20 nodos dicen `gana` y la de 15, `pierde`?

## Para seguir

- Guarden en una tabla el resultado de cada par (conjunto de nodos visitados, nodo actual), con el conjunto
  como una máscara de bits. Con 20 nodos son $2^{20} \cdot 20$ casillas. ¿Cuánto tarda ahora el grafo completo
  de 20 nodos? ¿Cuánta memoria ocupa la tabla, y cuánta ocuparía con 40 nodos? Esa versión cambia espacio por
  tiempo, y ya no muestra que el problema está en PSPACE.
- Impriman la estrategia completa del primer jugador, y no solo su primera jugada: qué responde ante cada
  jugada posible del rival. Cuenten cuántas líneas ocupa en `casos/06.in`.
lab/geography/solution.cppDescargar lab/geography/solution.cpp
// Geografía generalizada: ¿tiene estrategia ganadora el primer jugador?
// Lee un grafo dirigido con un nodo de partida e imprime `gana <nodo>`, con una primera
// jugada ganadora, o `pierde`.
#include <iostream>
#include <string>
#include <vector>

// El grafo G = (V, E) y el nodo de partida. Los tipos son una propuesta: cada nodo se guarda
// por su posición en la lista, para no comparar nombres durante la búsqueda. Pueden cambiarlos.
struct Graph {
    std::vector<std::string> nodes;       // V: los nombres, en el orden de la entrada
    std::vector<std::vector<int>> edges;  // E: edges[u] son los destinos de las aristas que salen de nodes[u]
    int start = 0;                        // el nodo de partida, como posición en nodes
};

// ¿Tiene estrategia ganadora quien debe mover con la ficha en current?
// visited marca los nodos del camino actual, incluido current.
// Por hacer: probar cada jugada a un nodo no visitado. Marcar el nodo, preguntar si el rival
// gana desde ahí, y desmarcarlo al volver. Recibir visited por referencia: una sola copia.
bool mover_wins(const Graph& g, int current, std::vector<bool>& visited) {
    (void)g;
    (void)current;
    (void)visited;
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    Graph g;
    std::string line;
    // Por hacer: leer nodes:, start: y edges: línea por línea, saltando los comentarios.
    while (std::getline(std::cin, line)) {
    }
    // Por hacer: probar cada primera jugada con mover_wins e imprimir `gana <nodo>` o `pierde`.
    // Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
    std::vector<bool> visited(g.nodes.size(), false);
    return mover_wins(g, g.start, visited) ? 1 : 0;
}
lab/geography/verificador.cppDescargar lab/geography/verificador.cpp
// Verificador del laboratorio: verificador caso.in caso.out salida
// Termina con 0 si la salida es correcta. Cuando el primer jugador gana puede haber varias
// primeras jugadas ganadoras: se acepta cualquiera, y se comprueba que de verdad gana.
#include <cstddef>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

struct Graph {
    std::vector<std::string> nodes;
    std::vector<std::vector<int>> edges;
    int start = 0;
};

static Graph read_graph(std::istream& in, std::map<std::string, int>& index) {
    Graph g;
    bool in_edges = false;
    std::string line;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == '#') {
            continue;
        }
        std::istringstream words(line);
        std::string first;
        std::string second;
        if (!(words >> first)) {
            continue;
        }
        if (in_edges) {
            words >> second;
            g.edges[index[first]].push_back(index[second]);
        } else if (first == "nodes:") {
            while (words >> second) {
                index[second] = static_cast<int>(g.nodes.size());
                g.nodes.push_back(second);
            }
            g.edges.assign(g.nodes.size(), {});
        } else if (first == "start:") {
            words >> second;
            g.start = index[second];
        } else if (first == "edges:") {
            in_edges = true;
        }
    }
    return g;
}

// ¿Gana quien debe mover con la ficha en current?
static bool mover_wins(const Graph& g, int current, std::vector<char>& visited) {
    for (int next : g.edges[current]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = 1;
        bool rival_wins = mover_wins(g, next, visited);
        visited[next] = 0;
        if (!rival_wins) {
            return true;
        }
    }
    return false;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador caso.in caso.out salida\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    std::ifstream expected(argv[2]);
    std::ifstream output(argv[3]);
    std::map<std::string, int> index;
    Graph g = read_graph(input, index);

    std::string want;
    expected >> want;
    std::vector<std::string> got;
    std::string word;
    while (output >> word) {
        got.push_back(word);
    }
    if (got.empty()) {
        std::cout << "la salida está vacía\n";
        return 1;
    }
    if (got[0] != "gana" && got[0] != "pierde") {
        std::cout << "la primera palabra debe ser gana o pierde, y salió " << got[0] << '\n';
        return 1;
    }
    if (got[0] != want) {
        std::cout << "esperaba " << want << ", salió " << got[0] << '\n';
        return 1;
    }
    if (want == "pierde") {
        if (got.size() != 1) {
            std::cout << "después de pierde no va nada\n";
            return 1;
        }
        return 0;
    }
    if (got.size() != 2) {
        std::cout << "después de gana va un nodo, y nada más\n";
        return 1;
    }
    if (index.count(got[1]) == 0) {
        std::cout << got[1] << " no es un nodo del grafo\n";
        return 1;
    }
    int move = index[got[1]];
    bool is_edge = false;
    for (int next : g.edges[g.start]) {
        is_edge = is_edge || next == move;
    }
    if (!is_edge || move == g.start) {
        std::cout << "no hay jugada de " << g.nodes[g.start] << " a " << got[1] << '\n';
        return 1;
    }
    std::vector<char> visited(g.nodes.size(), 0);
    visited[g.start] = 1;
    visited[move] = 1;
    if (mover_wins(g, move, visited)) {
        std::cout << "la jugada " << got[1] << " no es ganadora: el rival tiene una respuesta que gana\n";
        return 1;
    }
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 14: complejidad en espacio. Fórmulas cuantificadas, geografía generalizada y la
# recursión de Savitch.
# Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos, con sanitizers
#   make clean     borra lo generado
#
# Las pruebas leen las fórmulas y los grafos de machines/ y de errors/, así que se corren desde
# esta carpeta. El laboratorio está en lab/geography y tiene su propio Makefile: estas reglas
# no lo tocan.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = eval_qbf qbf_growth geography savitch_demo formula_to_geography guess_path
TESTS = test_qbf test_geography test_savitch test_formula_game
HEADERS = fields.h qbf.h graph.h geography.h savitch.h formula_game.h

.PHONY: all test clean

all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)

$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
	@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
	@echo "Todas las pruebas pasaron."

clean:
	rm -rf $(BUILD)