# 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`.
