# Laboratorio de la semana 10: Buscaminas Dos sesiones de 2 horas, cada una pensada para unos 90 minutos de trabajo. Los comandos se corren desde `code/week-10`. Las ideas están en los apuntes, sobre todo en "El laboratorio, paso a paso". | Archivo | Qué es | ¿Lo cambian? | |---|---|---| | `image.h`, `image.c` | El módulo de imágenes de la semana 6, terminado | No | | `regions.h` | La interfaz de `flood_fill` y `count_regions` | No | | `regions.c` | Las dos funciones, por escribir | **Sí** | | `regions_tests.c` | Pruebas con `assert` de las regiones | **Sí**, agreguen | | `fill_demo.c` | Muestra una imagen, cuenta sus regiones y pinta una | No | | `board.h` | La interfaz del tablero, con un tipo opaco | No | | `board.c` | Lo marcado arriba, por escribir; lo demás está hecho | **Sí** | | `board_tests.c` | Pruebas con `assert` del tablero | **Sí**, agreguen | | `minesweeper.c` | El juego de terminal | No | | `big_board.c` | Abre una esquina de un tablero grande sin minas | No | | `images/` | `islands.pgm`, `sun.pgm` y `tiny.pgm` | No | | `game_seed7_input.txt`, `game_seed7_output.txt` | Una partida fija y lo que debe escribir | No | ```sh make lab # compila todo en build/lab/ build/lab/regions_tests # sus pruebas de regiones build/lab/board_tests # sus pruebas del tablero build/lab/fill_demo lab/images/islands.pgm 2 2 255 build/lab/minesweeper 8 8 10 42 # filas, columnas, minas y semilla make test-lab # comprueba todo el laboratorio; falla hasta que terminen ``` Todo se compila con ASan: si un bloque no se libera, el programa termina con un informe y un código de error, y la prueba falla. `board_tests` se detiene en el primer `assert` que no se cumple: es normal que falle la parte de la sesión 2 mientras están en la sesión 1. Las líneas como `(void) img;` solo evitan una advertencia mientras un parámetro no se usa: bórrenlas cuando escriban la función. # Sesión 1 ## Parte 1: leer (unos 20 minutos) Lean `image.h`, `regions.h` y `board.h` completos. En `board.c`, lean el `struct`, `in_bounds`, `cell_at`, `board_from_rows`, `board_random`, `board_cell_char` y `board_print`. Lean también `board_tests.c`. Respondan por escrito, sin ejecutar nada. 1. `regions.c` no puede escribir `img->pixels`. ¿Por qué? ¿Qué funciones tiene que usar en su lugar? 2. Con `rows = 2` y `cols = 3`, ¿en qué posición de `cells` está la celda `(1, 2)`? 3. `count_neighbors` es `static`, y quien usa el módulo nunca la llama. ¿Cómo sabe entonces quien usa `board.h` que los conteos están listos? 4. `count_regions` recibe un `const Image *`. ¿Por qué eso le impide usar lo pintado como marca de visitado? 5. ¿Qué hace `board_random` para que la misma semilla dé el mismo tablero en dos computadoras distintas? ## Parte 2: `flood_fill` (unos 15 minutos) Escriban `flood_fill` en `regions.c`, con una función auxiliar `static` recursiva. Es lo mismo que `fill` en `grid_fill.c`, pero con píxeles y a través de `image_get`, `image_set`, `image_width` e `image_height`. Recuerden el caso del valor igual: `flood_fill` debe terminar también si la región ya vale `new_value`. ## Parte 3: `count_regions` (unos 25 minutos) Escriban `count_regions`. A diferencia de `count_islands.c`, cuenta las regiones de **todos** los valores, y no puede cambiar la imagen. Necesita: 1. Un bloque `visited` de `ancho * alto` marcas, pedido con `calloc` y liberado al final. Esta función es su owner. 2. Una función auxiliar `static` que marque una región, con el valor de esa región como parámetro. 3. Dos ciclos anidados: cada píxel sin marcar empieza una región nueva. Agreguen a `regions_tests.c` al menos una prueba: una imagen con un hueco, por ejemplo. ```sh build/lab/regions_tests build/lab/fill_demo lab/images/islands.pgm 2 2 255 build/lab/fill_demo lab/images/sun.pgm 0 0 230 ``` Antes de correr `fill_demo` con `islands.pgm`, cuenten a mano las regiones de la imagen. ¿Por qué baja en uno el conteo después de pintar? ## Parte 4: el tablero en memoria dinámica (unos 30 minutos) En `board.c`, escriban: 1. `board_new`: dos bloques, el `struct` y las celdas. Revisen los tamaños como lo hace `valid_size` en `image.c`, y si falla el segundo `malloc`, liberen el primero. Dejen las celdas en cero: por eso `CELL_HIDDEN` vale 0. 2. `board_free`, que acepte `NULL`. 3. `count_neighbors`: para cada celda, recorran las ocho vecinas con dos ciclos de -1 a 1. Salten la celda misma y las que caen fuera, con `in_bounds`. Una mina también lleva su conteo. Corran `build/lab/board_tests`: deben pasar las dos primeras pruebas, y la tercera sigue fallando. Agreguen una prueba de `count_neighbors` con un tablero de una sola fila. **Si no alcanza el tiempo:** lo que no terminen lo terminan antes de la sesión 2. La sesión 2 necesita que `board_new`, `board_free` y `count_neighbors` funcionen. # Sesión 2 ## Parte 5: `board_reveal` (unos 35 minutos) Escriban `board_reveal` y su función auxiliar recursiva. El pseudocódigo está en los apuntes. Decidan en qué orden van estas revisiones, y escríbanlo en un comentario: - La celda está fuera del tablero. - La celda ya está abierta o tiene bandera. - La celda es una mina. - La celda tiene minas vecinas. Si el juego ya terminó, `board_reveal` no hace nada. Y cada celda sin mina que se abre suma uno a `opened`. ## Parte 6: victoria y derrota (unos 20 minutos) Escriban `board_state` con los campos `exploded` y `opened`. Corran `build/lab/board_tests` y comparen con una partida fija: ```sh build/lab/minesweeper 5 5 3 7 < lab/game_seed7_input.txt ``` Lo que escribe debe ser igual a `lab/game_seed7_output.txt`. Después jueguen una partida de verdad, y escriban una prueba de una derrota en `board_tests.c`. ## Parte 7: un tablero de 1000 × 1000 (unos 30 minutos) Corran estos comandos y anoten qué pasa en cada uno. `big_board` es el programa compilado con ASan, y `big_board_plain` es el mismo, sin sanitizers. ```sh build/lab/big_board 100 100 build/lab/big_board 1000 1000 build/lab/big_board_plain 100 100 build/lab/big_board_plain 1000 1000 ulimit -s ``` Respondan por escrito: 1. ¿Qué pasó, y en qué función? ¿`board_new` tuvo algún problema con las celdas? ¿Cómo lo saben? 2. Sin minas, ¿cuántos marcos de su función recursiva pueden quedar apilados como máximo en un tablero de N × N? Justifíquenlo con el orden en que su función recorre las vecinas. 3. Busquen, probando tamaños, el mayor N que funciona con `big_board` y con `big_board_plain`. Con ese N y lo que dice `ulimit -s`, estimen cuántos bytes ocupa un marco en cada caso. ¿Por qué pueden salir distintos? 4. Corran `(ulimit -s 400000; build/lab/big_board_plain 1000 1000)`. ¿Qué cambió? ¿Por qué no es esta la solución del problema? 5. ¿Qué cambiarían en `board_reveal` para que un tablero de 1000 × 1000 funcione con la pila de siempre? Al final, `make test-lab`. **Si no alcanza el tiempo:** las preguntas 3 a 5 se pueden terminar antes de la próxima clase. ## Si sobra tiempo 1. Reescriban `board_reveal` con una pila propia, como `fill_stack.c`, y corran `big_board 1000 1000`. 2. Hagan que la primera celda abierta nunca sea una mina: si lo es, muevan esa mina a otra celda. ¿Qué conteos hay que recalcular? 3. Escriban `count_regions_diagonal`, que también una los píxeles por las diagonales. ¿Cuánto cambia el conteo de `islands.pgm`?