# Laboratorio de la semana 12: un solucionador genérico Hay dos sesiones de 2 horas. Cada una está pensada para unos 90 minutos de trabajo. Los comandos se corren desde `code/week-12`. Las ideas están en los apuntes, en la sección "El laboratorio, paso a paso". | Archivo | Qué es | ¿Lo cambian? | |---|---|---| | `compare.h` | El tipo `Trip` y los tres comparadores que se piden | No | | `compare.c` | Los comparadores | **Sí** | | `sort_trips.c` | Ordena viajes por el criterio que recibe, con una tabla de funciones | No | | `array_ops.h` | La interfaz de `array_map`, `array_filter`, `array_fold`, `array_count_if` y `count_above` | No | | `array_ops.c` | Esas funciones | **Sí** | | `ops_tests.c` | Sus pruebas con `assert` | **Sí** | | `backtrack.h` | La interfaz del backtracker: el `struct` `Problem` y `backtrack` | No | | `backtrack.c` | El backtracker | **Sí** | | `coloring.c` | Un problema completo, resuelto con el backtracker. Es el modelo | No | | `queens.h`, `queens_main.c` | La interfaz de N reinas y un programa que la usa | No | | `queens.c` | Los callbacks de N reinas por escribir; la búsqueda ya está armada | **Sí** | | `board.h`, `board.c` | El tablero de sudoku: el lector y `board_can_place`, ya hechos | No | | `sudoku.h`, `sudoku_main.c` | La interfaz del sudoku y un programa que la usa | No | | `sudoku.c` | Los callbacks del sudoku por escribir; la búsqueda ya está armada | **Sí** | | `data/` | Tableros de sudoku, en el formato de la semana 11 | No | ```sh make lab # compila todo en build/lab/ make test-lab # comprueba todo el laboratorio; falla hasta que terminen ``` `make test-lab` corre pruebas de las dos sesiones. En la primera, fíjense solo en `Comparators` y `ArrayOps`. Se puede correr un grupo solo: ```sh LAB_DIR=lab python3 -m unittest test_lab.Comparators ``` Todo se compila con ASan y UBSan. Un overflow escribe un `runtime error` en la salida, y eso también hace fallar la prueba. ## Sesión 1: comparadores, map, filter, fold y contexto ### Parte 1: comparadores (unos 25 minutos) Lean `compare.h` y `sort_trips.c`. Respondan por escrito, sin ejecutar nada: 1. En `sort_trips.c`, ¿qué tipo tiene `chosen`? ¿Qué se tendría que cambiar para agregar un criterio? 2. ¿Por qué `qsort` necesita `sizeof(trips[0])`, si ya recibe el arreglo? Luego escriban los tres comparadores de `compare.c`. **No resten**: una prueba usa `INT_MIN` e `INT_MAX`, y otra compara tarifas que difieren en menos de 1. Pruébenlos así: ```sh make lab build/lab/sort_trips pasajeros build/lab/sort_trips tarifa build/lab/sort_trips ruta ``` ### Parte 2: map, filter y fold (unos 35 minutos) En `array_ops.c`, escriban `array_map`, `array_filter` y `array_fold`. En `ops_tests.c` ya está la prueba de `array_map`, como modelo. Agreguen una de `array_filter` y otra de `array_fold`, cada una con un arreglo vacío. Las funciones que pasan como callback en las pruebas son `static`, en ese mismo archivo. ```sh make lab build/lab/ops_tests ``` ### Parte 3: contexto (unos 25 minutos) 1. Escriban `array_count_if`. No mira el contexto: solo se lo pasa al callback. 2. Escriban `count_above`, con un callback `static` que recibe el umbral por el contexto. Sin variables globales: una prueba lo revisa. ¿Dónde vive el umbral mientras corre `array_count_if`? ¿Por qué es seguro? 3. Prueben `count_above` en `ops_tests.c`. Corran `LAB_DIR=lab python3 -m unittest test_lab.Comparators test_lab.ArrayOps`. **Si no alcanza el tiempo:** lo que falte de esta sesión lo terminan antes de la siguiente, porque la sesión 2 da todo esto por sabido. ## Sesión 2: un backtracker que resuelve de todo ### Parte 1: leer (unos 15 minutos) Lean `backtrack.h` completo y luego `coloring.c`. Respondan por escrito: 1. ¿Qué es un paso en `coloring.c`? ¿Qué es una opción? 2. ¿Dónde vive el contador de soluciones? ¿Por qué no se necesita una variable global? 3. ¿Por qué `coloring_on_solution` copia los colores? ¿Qué quedaría en `state.color` al terminar la búsqueda? ### Parte 2: el backtracker (unos 20 minutos) Escriban `backtrack` en `backtrack.c`, a partir del pseudocódigo de los apuntes. Son unas 20 líneas. No debe saber nada de reinas ni de sudokus: una prueba lo revisa. Compruébenlo con el problema ya resuelto: ```sh make lab build/lab/coloring LAB_DIR=lab python3 -m unittest test_lab.Engine ``` Antes de correrlo, calculen a mano cuántas soluciones debe haber: el resultado está en los apuntes. ### Parte 3: N reinas (unos 25 minutos) En `queens.c`, escriban los cinco callbacks. Lo que está debajo del comentario ya está hecho: léanlo, y fíjense en que arma un `Problem` como el de `coloring.c`. ```sh make lab build/lab/queens_main 4 build/lab/queens_main 8 ``` Comprueben a mano la solución que escribe para 4 reinas, dibujando el tablero. Con 8, son 92 soluciones. ### Parte 4: sudoku (unos 30 minutos) En `sudoku.c`, escriban los cinco callbacks. **No cambien `backtrack.c`**. Un paso es una celda vacía, y la opción es un dígito menos 1. ```sh make lab build/lab/sudoku_main lab/data/facil.txt build/lab/sudoku_main lab/data/sin_solucion.txt make test-lab ``` **Si no alcanza el tiempo:** el sudoku es lo que se puede terminar antes de la próxima clase. Es casi lo mismo que N reinas, y es la prueba de que el backtracker es genérico. ## Si sobra tiempo 1. Agreguen a `sort_trips.c` un criterio nuevo: una función y una fila de la tabla. ¿Cuántas líneas cambian? 2. Resuelvan otro problema con el mismo `backtrack.c`, en un archivo nuevo: los subconjuntos de un arreglo que suman un valor. ¿Qué es el paso, y qué es la opción? 3. Midan cuántos nodos ahorra poner primero las celdas con menos opciones. Basta con ordenar las listas de celdas vacías antes de buscar, sin tocar `backtrack.c`.