# Buscar una solución de PCP

En el problema de correspondencia de Post (PCP) se da un conjunto de fichas. Cada ficha tiene una cadena arriba
y otra abajo. Una **solución** es una secuencia de una o más fichas, que se pueden repetir, tal que la cadena
que se lee arriba, juntando las de todas las fichas en orden, es igual a la que se lee abajo.

Esta semana se demostró que ningún algoritmo decide si un conjunto de fichas tiene solución. Lo que sí se puede
programar es una búsqueda: probar secuencias cada vez más largas. Si la solución existe, la búsqueda la
encuentra. Si no existe, la búsqueda no puede saberlo en general, y por eso el programa de este laboratorio
recibe una cota $N$ y nunca responde "no tiene solución".

## Entrada

```text
dominoes: 3
1 111
10111 10
10 0
bound: 10
```

- `dominoes: k` dice cuántas fichas hay. Siguen $k$ líneas, una por ficha: la cadena de arriba, un espacio y la
  cadena de abajo. Las fichas se numeran desde 1, en el orden de la entrada.
- `bound: N` es la cota: la cantidad máxima de fichas de la solución, contando las repeticiones.
- No hay comentarios ni líneas vacías.

## Salida

Una sola línea:

- los números de las fichas de una solución de **a lo sumo $N$ fichas**, en orden y separados por espacios; o
- `sin solución hasta N`, con el valor de $N$ de la entrada, si no existe ninguna solución de a lo sumo $N$
  fichas.

Si hay varias soluciones, cualquiera sirve: no tiene que ser la más corta, solo respetar la cota. El juez usa un
verificador (`verificador.cpp`, pueden leerlo) que pone las fichas de su respuesta y compara las dos cadenas. La
respuesta `sin solución hasta N` solo se acepta si de verdad no hay una solución de a lo sumo $N$ fichas.

## Límites

- $1 \leq k \leq 50$ fichas. Puede haber fichas repetidas.
- Cada cadena tiene entre 1 y 20 caracteres visibles, sin espacios. La mayoría de los casos usa `0` y `1` o
  letras minúsculas. Dos casos usan además `#`, `*`, `$`, `_` y letras mayúsculas: son fichas construidas a
  partir de una máquina de Turing, como en los apuntes.
- $1 \leq N \leq 200$.
- En todos los casos, la cantidad de pares distintos (lado adelantado, exceso) que se alcanzan con a lo sumo $N$
  fichas es menor que 100 000. Sin esa promesa el problema no tendría un límite de tiempo razonable: hay
  conjuntos de tres fichas en los que esa cantidad crece exponencialmente con $N$.

## Ejemplo

Para la entrada de arriba, una salida correcta es:

```text
2 1 1 3
```

Arriba se lee $\mathtt{10111}\,\mathtt{1}\,\mathtt{1}\,\mathtt{10}$ y abajo
$\mathtt{10}\,\mathtt{111}\,\mathtt{111}\,\mathtt{0}$: las dos son $\mathtt{101111110}$. También es correcta
`2 1 1 3 2 1 1 3`, que repite la solución y tiene 8 fichas, porque no pasa de la cota 10.

Con las mismas fichas y `bound: 3`, la salida es:

```text
sin solución hasta 3
```

La instancia tiene solución, pero ninguna de 3 fichas o menos. Por eso la respuesta lleva la cota.

## Tiempo

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

Probar todas las secuencias no alcanza. Con $k$ fichas hay $k^n$ secuencias de $n$ fichas. El caso `09` tiene
tres fichas y su solución más corta tiene 45: son $3^{45}$ secuencias, un número de 22 cifras.

## La idea: el exceso

Mientras se ponen fichas, una de las dos cadenas va adelantada, y lo que ya coincidió no vuelve a importar. Si
arriba se lee $\mathtt{10111}$ y abajo $\mathtt{10}$, lo único que hay que recordar es que **arriba** va
adelantado con el **exceso** $\mathtt{111}$: la ficha siguiente tiene que empezar a cubrirlo desde abajo.

El estado de la búsqueda es entonces un par: qué lado va adelantado y con qué cadena. Poner una ficha lleva de
un estado a otro, o no se puede si las cadenas dejan de coincidir. Una solución es un camino que vuelve al
exceso vacío después de poner al menos una ficha.

```text
(nada)  --ficha 2-->  arriba 111  --ficha 1-->  arriba 1  --ficha 1-->  abajo 1  --ficha 3-->  (nada)
```

Con eso el problema es una búsqueda en un grafo, como las de Algoritmos:

1. **Busquen en anchura**, por niveles: el nivel $n$ tiene los estados a los que se llega con $n$ fichas. Paren
   en el nivel $N$.
2. **No repitan estados.** Si dos secuencias llevan al mismo exceso, lo que se puede hacer después es lo mismo
   para las dos: basta seguir con la primera que llegó. Guarden los estados vistos en un `std::unordered_map` o un
   `std::set`. El caso `11` tiene fichas repetidas y castiga a quien no lo haga.
3. Para escribir la secuencia, guarden por cada estado de qué estado vino y con qué ficha, y reconstruyan el
   camino al final.

## Cómo avanzar

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

1. Lean la entrada y escriban la función que pone una ficha a un estado: recibe el lado adelantado, el exceso y
   la ficha, y devuelve el estado nuevo o avisa que no se puede. Pruébenla a mano con el ejemplo.
2. Escriban la búsqueda en anchura hasta $N$ fichas, todavía sin conjunto de visitados, y pasen los casos
   pequeños.
3. Agreguen el conjunto de visitados. Antes de correr el juez, respondan: ¿por qué no se pierde ninguna solución
   al descartar un estado repetido? ¿Y por qué la solución que encuentra la búsqueda en anchura es una de las
   más cortas?
4. Respondan con la secuencia o con `sin solución hasta N`. Revisen los casos de borde: una sola ficha con las
   dos cadenas iguales, $N = 1$, ninguna ficha que pueda ir primera.
5. Prueben su programa con las fichas de una máquina de Turing. Desde `code/week-10`:

   ```sh
   build/tm_to_pcp machines/starts_01.tm 01 --pcp
   ```

   escribe las fichas de la máquina `starts_01.tm` con la entrada `01`, con dos líneas de comentario al
   inicio. Quiten los comentarios, agreguen `bound: 30` y busquen. ¿Qué se lee en la solución? Es el caso `12`.

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

Los casos traen, entre otros: una solución que usa exactamente $N$ fichas, la misma instancia con una cota
menor, una sola ficha, ninguna ficha que pueda empezar, una instancia en la que se pueden poner fichas para
siempre sin terminar, fichas repetidas, la instancia de solución larga y dos conjuntos de fichas que salen de
máquinas de Turing.

## Preguntas

Respondan en un archivo `respuestas.md`, en esta carpeta.

1. Expliquen en dos líneas por qué su programa, si se le quita la cota $N$, **reconoce** PCP y no lo
   **decide**. ¿Qué hace con un conjunto de fichas que tiene solución? ¿Y con uno que no tiene?
2. El caso `07` no tiene solución de ninguna longitud, y su búsqueda lo puede saber sin llegar a la cota. ¿Cómo?
   ¿Por qué eso no contradice que PCP sea indecidible?
3. ¿Por qué la salida dice `sin solución hasta N` y no "no tiene solución"? Den un caso de la carpeta `casos/`
   en el que la segunda frase sería falsa.

## Para seguir

Opcional, sin casos en el juez.

- Cuenten cuántos estados distintos visita su búsqueda en cada nivel con las fichas
  `110 1`, `1 0`, `0 110`. ¿Por cuánto se multiplica, más o menos, de un nivel al siguiente? ¿Hasta qué $N$
  llega su programa en 2 segundos?
- Busquen desde los dos extremos: una solución leída de derecha a izquierda es una solución del conjunto de
  fichas con todas las cadenas invertidas. ¿Cómo se juntan las dos búsquedas?
