C Piscine — BSQ

El proyecto final de la piscine: Biggest SQuare. Leer un mapa de un fichero, encontrar el mayor cuadrado sin obstáculos y pintarlo. Un programa completo, con Makefile, varios ficheros de entrada, entrada estándar, validación estricta y una Moulinette que no perdona.

El enunciado — Programa bsq; funciones autorizadas open, close, read, write, malloc, free y exit. La primera línea del mapa trae el número de líneas y, como sus tres últimos caracteres, el carácter vacío, el de obstáculo y el de lleno. El programa sustituye vacíos por llenos para dibujar el mayor cuadrado posible; si hay empate, el más arriba y, entre esos, el más a la izquierda. Acepta de 1 a n ficheros (con una línea en blanco entre salidas) o, sin argumentos, un mapa por la entrada estándar. Cualquier mapa inválido es un map error.
$> cat example_file          $> ./bsq example_file
9.ox                         .....xxxxxxx...............
...........................  ....oxxxxxxx...............
....o......................  .....xxxxxxxo..............
............o..............  .....xxxxxxx...............
...........................  ....oxxxxxxx...............
....o......................  .....xxxxxxx...o...........
...............o...........  .....xxxxxxx...............
...........................  ......o..............o.....
......o..............o.....  ..o.......o................
..o.......o................
A diferencia de los rushes, este lo corrige la Moulinette. El código está en packs/piscine/019_bsq/repo/ y la salida de arriba es la del programa tal cual.

GGlosario de teoría

BSQ es el primer programa completo de la piscine, y la página usa palabras de cómo C habla con el sistema, de cómo se gestiona la memoria y de cómo se mide lo que cuesta un algoritmo. Aquí está cada una explicada desde cero y con un ejemplo sacado del propio BSQ. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Leer, escribir y guardar el mapa

Descriptor de fichero, entrada y salida estándar

Un descriptor es el número con el que el sistema identifica un fichero abierto por el programa. open devuelve uno nuevo (o -1 si falla) y desde ahí read, write y close trabajan con ese número, no con el nombre. Todo proceso nace con tres ya abiertos: el 0 es la entrada estándar (stdin), el 1 la salida estándar (stdout) y el 2 la salida de error (stderr).

BSQ aprovecha que la lectura no distingue de dónde viene el descriptor: sin argumentos llama a ft_map_from_fd(0), así que ./bsq < mapa y cat mapa | ./bsq funcionan con el mismo código que un fichero; con argumentos, ft_read_map solo añade el open y el close. Todo lo que escribe, incluido map error, va por el 1.

Llamada al sistema

Una función que no hace el trabajo ella misma sino que se lo pide al núcleo del sistema operativo: open, read, write y close lo son. Cada llamada supone cambiar del programa al núcleo y volver, así que tiene un coste fijo apreciable aunque mueva un solo byte.

Por eso ft_print_map escribe cada fila de una vez: según el comentario del código, en un mapa de 300×300 son 600 write (fila y salto) en lugar de 90 000, uno por celda.

Buffer

Una zona de memoria de tamaño fijo donde se dejan los datos de paso, entre quien los produce y quien los usa. read(fd, buf, n) llena como mucho n bytes y devuelve cuántos ha leído de verdad: 0 al final del fichero, -1 si hay error.

ft_read_file usa char buffer[256] y lee como mucho 255 bytes, para dejar sitio al '\0' que pone en buffer[n] antes de pegar el trozo con ft_strfreecat.

Terminador nulo

En C una cadena es una fila de char que acaba en el byte '\0'. No se guarda la longitud: el final se sabe porque ahí está el cero, y cada reserva necesita un byte más que los caracteres visibles.

ft_strfreecat reserva ft_strlen(s1) + ft_strlen(s2) + 1 por ese byte, y ft_strifcpy, fin - ini + 1. read no pone el cero: lo añade ft_read_file a mano.

Memoria dinámica: malloc y free

malloc(n) pide al sistema un bloque de n bytes que vive hasta que alguien lo devuelve con free; si no hay memoria, devuelve NULL. Hace falta cuando el tamaño no se conoce al compilar, como el de un mapa que llega de un fichero.

En BSQ cada fila del mapa es un bloque, el array de filas es otro y el t_map, otro más. La cadena con el fichero entero se va rehaciendo: ft_strfreecat reserva una nueva, copia y hace free de la anterior.

Fuga de memoria y valgrind

Una fuga (leak) es memoria reservada con malloc que ya no se puede liberar porque no queda ningún puntero hacia ella. Valgrind ejecuta el programa vigilando cada reserva y cada liberación, y al final dice lo que quedó sin liberar.

En BSQ todo camino de error pasa por ft_parse_error, que libera el split y la estructura. Con valgrind --leak-check=full, tanto un mapa válido seguido de un fichero que no existe como un mapa con filas desiguales acaban en «All heap blocks were freed -- no leaks are possible».

Centinela (el NULL final de un array)

Un valor especial que marca el final de una secuencia, para no tener que guardar su longitud aparte. El '\0' es el centinela de las cadenas; en un array de punteros se usa NULL.

ft_split devuelve un char ** acabado en NULL, y ft_arrlen y ft_free_split lo recorren hasta ahí. Por eso BSQ comprueba que haya exactamente height + 1 líneas antes de validar: si faltaran, el bucle hasta map[height] leería el NULL y seguiría fuera del array.

Split (partir una cadena)

Partir una cadena en trozos usando unos caracteres separadores, y devolver los trozos en un array. La versión de la piscine (C 07) junta los separadores seguidos: entre dos separadores pegados no sale un trozo vacío, sino nada.

ft_split(map_str, "\n") convierte el fichero en líneas: map[0] es la cabecera y las demás, las filas. Que funda los '\n' seguidos es cómodo, pero hace que una línea vacía en medio del mapa desaparezca en vez de dar error.

Cabecera (del mapa)

La primera línea de un fichero cuando no es dato sino descripción de lo que viene detrás. Es un patrón muy común en formatos de fichero: primero se dice cómo leer y después llegan los datos.

En BSQ la cabecera 9.ox dice: 9 filas, '.' vacío, 'o' obstáculo y 'x' lleno. Los símbolos se reconocen por su posición (los tres últimos caracteres), no por no ser dígitos.

ASCII y caracteres imprimibles

ASCII asigna un número de 0 a 127 a cada carácter. Del 32 (el espacio) al 126 (~) son imprimibles: se ven en pantalla. Por debajo del 32 están los de control ('\n' es el 10, el tabulador el 9) y el 127 es DEL.

ft_check_obj exige que los tres símbolos estén entre 32 y 126 y sean distintos. El enunciado recuerda que el espacio y los dígitos también son imprimibles, así que 2 #x (vacío el espacio) es una cabecera válida.

El algoritmo y su coste

Fuerza bruta

Resolver un problema probando todas las posibilidades, sin ninguna idea que descarte candidatos. Es fácil de escribir y de demostrar correcto, pero el coste se dispara.

En BSQ, la fuerza bruta pura sería: para cada casilla y para cada lado posible, revisar todo el cuadrado desde cero. ft_bsq_isolver parte de esa idea (cada casilla vacía es una posible esquina superior izquierda) pero no la aplica a ciegas: la poda.

Poda

Descartar candidatos sin examinarlos, porque se sabe de antemano que no pueden mejorar la mejor solución encontrada. Es lo que convierte una fuerza bruta en algo usable.

ft_bsq_isolver poda dos veces: empieza a probar desde el récord + 1 (un cuadrado igual o menor no serviría) y, si un cuadrado tiene un obstáculo, deja esa esquina (todos los mayores desde ahí también lo tendrían). ft_validate_sq lo señala poniendo *tmp = -1.

Coste cuadrático

Un coste que crece con el cuadrado del tamaño de la entrada: el doble de datos, cuatro veces el trabajo. Suele salir de repetir, para cada elemento nuevo, un trabajo proporcional a todo lo anterior. Se escribe O(n²).

La lectura de BSQ lo es: cada ft_strfreecat copia todo lo acumulado para añadir 255 bytes. Con un fichero de 1 MB son unas 4000 lecturas y, de media, medio megabyte copiado en cada una: unos 2000 millones de bytes copiados para leer un millón.

Programación dinámica

Resolver un problema guardando las soluciones de subproblemas pequeños y construyendo con ellas las de los grandes, en lugar de recalcularlas. Es la solución clásica de BSQ, aunque este código no la usa.

La idea: para cada casilla, el lado del mayor cuadrado que acaba en ella (esquina inferior derecha) es 0 si es obstáculo, y si no, 1 + el mínimo de los de arriba, izquierda y arriba-izquierda. Con el mapa

.....        1 1 1 1 1
..o..        1 2 0 1 2
.....        1 2 1 1 2
.....        1 2 2 2 2

el máximo es 2, y el primero en orden de lectura cae en la segunda fila, segunda columna: el cuadrado de las filas 1–2 y columnas 1–2, el mismo que pinta BSQ (xx... / xxo..). Una sola pasada, coste proporcional al número de casillas.

Desempate por orden de recorrido

Cuando varias soluciones son igual de buenas, la regla que elige una. Si el recorrido ya visita los candidatos en el orden de preferencia, basta con quedarse con el primero: no hace falta comparar posiciones.

BSQ recorre fila a fila y, en cada fila, de izquierda a derecha, y solo cambia el récord con map->sq[2] < *tmp (menor estricto). Un cuadrado del mismo tamaño encontrado después está más abajo o más a la derecha, y nunca sustituye al primero.

Problema de la valla (fencepost)

Para una valla de 10 tramos hacen falta 11 postes: los separadores son uno menos (o uno más) que las cosas que separan. Es la fuente de los errores «por uno» más comunes.

Con varios ficheros, BSQ pone una línea en blanco entre salidas: con 3 mapas, 2 líneas. Por eso main escribe el salto antes de cada mapa salvo el primero (if (i > 1)), y no después de cada uno.

C, compilación y reglas de 42

Struct y typedef

Un struct agrupa varias variables bajo un nombre; typedef le da un alias para no escribir struct s_map cada vez. Con un puntero a la estructura, los campos se leen con ->: map->height es (*map).height.

t_map reúne los símbolos, las filas, el ancho, el alto y el mejor cuadrado. Así cada función recibe un solo parámetro con todo el estado.

Arrays como parámetro

En C un array no se pasa entero a una función: se pasa la dirección de su primer elemento. Por eso escribir int i[2] en un parámetro es lo mismo que int *i, y la función puede leer y cambiar el array de quien la llama.

ft_validate_sq(t_map *map, int i[2], int *tmp) recibe la fila y la columna en i y el lado por puntero, para poder devolver el −1. Usar arrays de dos enteros (i[2], j[2]) es también un truco para respetar el límite de cinco variables por función de la Norma.

atoi

Convierte el principio de una cadena en un entero: salta espacios, lee un signo opcional y acumula dígitos hasta el primer carácter que no lo es. Decide ella sola dónde para.

BSQ usa su propio ft_atoi sobre la cabecera entera. Con 9.ox se para en el '.' y da 9; con 21ox (2 filas, vacío '1') sigue por el '1' y da 21.

Desbordamiento de entero

Un int de 32 bits va de −2 147 483 648 a 2 147 483 647. Si una operación con signo se sale de ese rango, el resultado es comportamiento indefinido: en la práctica suele dar la vuelta y salir un número sin sentido.

ft_atoi no lo comprueba: una cabecera con un número de 11 cifras desborda dentro de r * 10. El enunciado dice que la altura puede ser «cualquier valor de int válido», así que una altura mayor no tiene que funcionar, pero tampoco hay un control explícito.

Makefile y relink

make lee las reglas del Makefile (objetivo, dependencias y comandos) y solo rehace lo que esté más viejo que aquello de lo que depende. Relink es volver a enlazar el ejecutable sin que haya cambiado nada, y el enunciado lo prohíbe.

En BSQ, un segundo make responde make: Nothing to be done for 'all'. Como la regla patrón es %.o: %.c bsq.h, tocar bsq.h recompila todos los objetos y vuelve a enlazar, que es lo correcto.

Norma y norminette

La Norma es el estilo obligatorio de 42: funciones de 25 líneas como mucho, cuatro parámetros y cinco variables por función, sin for ni switch, cabecera de 42 en cada fichero… norminette es el programa que la comprueba, y un error es un 0.

Todos los .c y el .h de BSQ pasan norminette sin errores. La Norma explica varias decisiones del código, como el t_map que lo lleva todo o los índices en arrays i[2].

Moulinette

El corrector automático de 42: compila la entrega con cc -Wall -Wextra -Werror, la pasa por la norminette y la ejecuta contra sus propias pruebas. No se discute con ella: un fallo es un fallo.

A diferencia de los rushes, BSQ lo corrige la Moulinette, y el enunciado avisa de que es «muy estricta y meticulosa». Además hay defensa, en la que cada persona del grupo tiene que entender todo el proyecto.

bsq.ht_map

Entrega: bsq.hAutorizado: open, close, read, write, malloc, free, exit

Todo lo que se sabe de un mapa viaja en una sola estructura. Dos decisiones que conviene tener en la cabeza para leer el resto: map[0] es la cabecera (las filas van de map[1] a map[height]), y el mejor cuadrado se guarda como fila, columna y lado en sq[3].

/*
** obj[0] vacio, obj[1] obstaculo, obj[2] lleno (el orden de la cabecera).
** map[0] es la cabecera: las filas del mapa van de map[1] a map[height].
** sq[0] fila, sq[1] columna, sq[2] lado del mayor cuadrado encontrado.
*/
typedef struct s_map
{
	char	obj[3];
	char	**map;
	int		width;
	int		height;
	int		sq[3];
}	t_map;
Qué te obliga a aprender — A diseñar el estado antes que las funciones. Con una estructura bien pensada, cada función recibe un t_map * y la Norma (máximo cuatro parámetros) deja de ser un problema. Dejar la cabecera en map[0] evita copiar el mapa, a cambio de que todos los índices de fila empiecen en 1.

mainmain y ft_run_map

Entrega: bsq.cAutorizado: write

ft_run_map hace un mapa de principio a fin: si llega NULL (no se pudo leer o no es válido) solo escribe el error; si no, resuelve, pinta y libera. main decide de dónde vienen los mapas.

	if (argc < 2)
	{
		ft_run_map(ft_map_from_fd(0));
		return (0);
	}
	i = 1;
	while (i < argc)
	{
		if (i > 1)
			ft_putstr("\n");
		ft_run_map(ft_read_map(argv[i]));
		i++;
	}
Qué te obliga a aprender — El problema de la valla otra vez (C00): la línea en blanco va entre salidas, así que se escribe antes de cada mapa menos del primero. Y que cada mapa es independiente: un fichero que no existe en medio de la lista da su map error y el programa sigue con el siguiente.

leerft_read_file, ft_map_from_fd y ft_read_map

Entrega: ft_read_file_map.c, ft_str_utils.cAutorizado: open, read, close, malloc, free

La lectura es la misma idea que en el Rush 02 (de hecho ft_split.c es idéntico): leer a trozos de 255 bytes y pegarlos con ft_strfreecat, que devuelve un bloque nuevo y libera el anterior. La lectura está separada en dos niveles para que la entrada estándar y los ficheros compartan código: ft_map_from_fd trabaja con cualquier descriptor, y ft_read_map solo añade el open y el close.

	map_str = ft_strifcpy("", 0, 0);
	n = read(fd, buffer, sizeof(buffer) - 1);
	while (n > 0)
	{
		buffer[n] = '\0';
		map_str = ft_strfreecat(map_str, buffer);
		if (!map_str)
			return (0);
		n = read(fd, buffer, sizeof(buffer) - 1);
	}

Ojo: cada vuelta copia todo lo acumulado para añadir 255 bytes, así que el coste crece con el cuadrado del tamaño del fichero. En un mapa de 1000×1000 generado con el script del enunciado (1 MB, unas 4000 lecturas), el programa tarda unos 6 segundos, y prácticamente todo ese tiempo es la lectura: el mismo mapa con una línea de más, que se rechaza justo después de leerlo, tarda lo mismo.

Qué te obliga a aprender — Que la entrada no siempre cabe en un buffer fijo y hay que crecer bajo demanda. Y que crecer de 255 en 255 bytes copiando todo cada vez es cuadrático: con el diccionario del Rush 02 no se nota; con un mapa de un megabyte, sí. BSQ es el primer proyecto donde el rendimiento se ve sin medir.

cabeceraft_parse_header y ft_check_obj

Entrega: ft_parse_header.cAutorizado: ninguna

Los tres últimos caracteres de la primera línea son vacío, obstáculo y lleno; todo lo de delante tiene que ser dígitos. ft_check_obj exige que los tres sean imprimibles (32 a 126) y distintos entre sí, y ft_is_pos convierte una altura de 0 o negativa en 0, que es el «no válido».

	h = map->map[0];
	len = ft_strlen(h);
	if (len < 4 || !ft_only_digits(h, len - 3))
		return (0);
	map->obj[0] = h[len - 3];
	map->obj[1] = h[len - 2];
	map->obj[2] = h[len - 1];
	if (!ft_check_obj(map))
		return (0);
	map->height = ft_is_pos(ft_atoi(h));
	return (map->height != 0);

Ojo: ft_only_digits mira solo los len - 3 primeros caracteres, pero ft_atoi(h) lee la cabecera entera mientras haya dígitos. El enunciado recuerda que un dígito es un carácter válido para el mapa: con la cabecera 21ox (2 líneas, vacío '1'), ft_atoi lee 21 y el mapa sale como map error. Bastaría con no dejar que la conversión pase de len - 3.

Qué te obliga a aprender — A parsear de derecha a izquierda cuando el formato lo pide: los símbolos no se reconocen por ser «no dígitos», sino por su posición al final. Y a desconfiar de reutilizar una función (ft_atoi) cuyo contrato no coincide del todo con lo que necesitas: atoi decide sola dónde para.

validarft_parse_map y ft_validate_map

Entrega: ft_parse_map.c, ft_split.cAutorizado: malloc, free

El fichero se parte por '\n'; la cabecera tiene que ser válida y el número de líneas tiene que coincidir exactamente con lo prometido. Ese conteo, como explica el propio comentario del código, protege dos cosas: que ft_validate_map no se salga del array si faltan líneas y que no se acepten líneas de sobra.

	map->map = ft_split(map_str, "\n");
	if (!map->map || ft_arrlen(map->map) < 2)
		return (ft_parse_error(map));
	if (!ft_parse_header(map))
		return (ft_parse_error(map));
	if (ft_arrlen(map->map) != map->height + 1)
		return (ft_parse_error(map));
	return (ft_validate_map(map));

Después, todas las filas deben medir lo mismo que la primera y contener solo vacíos u obstáculos. El carácter «lleno» dentro del mapa también es error: lo pone el programa.

		if (ft_strlen(map->map[i]) != map->width)
			return (ft_parse_error(map));
		j = 0;
		while (j < map->width)
		{
			if (!ft_is_map(map->map[i][j], map))
				return (ft_parse_error(map));
			j++;
		}
Qué te obliga a aprender — Que la mitad de la nota de BSQ son mapas inválidos. La Moulinette prueba cabeceras raras, líneas desiguales, caracteres extraños y ficheros vacíos, y cada uno tiene que acabar en map error sin fugas: por eso todo camino de error pasa por ft_parse_error, que libera el split y la estructura.

claveft_bsq_isolver y ft_validate_sq

Entrega: ft_bsq_isolver.cAutorizado: ninguna

El algoritmo recorre el mapa de arriba abajo y de izquierda a derecha. En cada casilla vacía intenta hacer crecer un cuadrado con esa casilla como esquina superior izquierda, pero no desde 1: empieza en el mejor lado encontrado hasta ahora más uno. Un cuadrado igual o más pequeño no serviría de nada.

			if (map->map[i[0]][i[1]] == map->obj[0])
			{
				tmp = map->sq[2];
				while (tmp != -1
					&& tmp <= map->height - i[0]
					&& tmp < map->width - i[1])
				{
					tmp++;
					ft_validate_sq(map, i, &tmp);
				}
			}

ft_validate_sq recorre el cuadrado de lado tmp. Si encuentra un obstáculo, pone tmp a −1, lo que corta sus propios bucles y el while de fuera (si un cuadrado tiene un obstáculo, todos los mayores desde esa esquina también). Si no, y es mayor que el récord, se guarda.

			if (map->map[i[0] + j[0]][i[1] + j[1]] == map->obj[1])
				*tmp = -1;
	...
	if (map->sq[2] < *tmp)
	{
		map->sq[0] = i[0];
		map->sq[1] = i[1];
		map->sq[2] = *tmp;
	}

El desempate del enunciado sale solo: como se recorre en orden de lectura y el récord solo se sustituye con < estricto, un cuadrado del mismo tamaño encontrado más tarde (más abajo o más a la derecha) nunca reemplaza al primero. Los límites del while garantizan que el cuadrado no se salga por abajo ni por la derecha.

Qué te obliga a aprender — A razonar sobre el coste. Comprobar cada casilla con cada tamaño desde cero sería inviable; esta solución poda de dos formas (empezar por el récord + 1 y abandonar al primer obstáculo). Aun así, cada casilla vacía revisa un cuadrado de (récord + 1)² celdas, así que el coste depende de lo grande que sea la respuesta. En los mapas de prueba de 1000×1000 con obstáculos la búsqueda es rápida; lo lento es leer. Y el desempate demuestra que el orden de recorrido puede resolver una regla del enunciado sin una línea de código extra.

salidaft_fill_sq y ft_print_map

Entrega: ft_print_map.cAutorizado: write

Se pinta sobre el propio mapa (no hace falta copia) y se escribe cada fila de una vez, en vez de carácter a carácter. Si no hay ningún cuadrado posible (todo obstáculos), el lado es 0, los bucles no entran y el mapa sale tal cual.

	ft_fill_sq(map);
	i = 1;
	while (i <= map->height)
	{
		ft_putstr(map->map[i]);
		ft_putstr("\n");
		i++;
	}
Qué te obliga a aprender — Que write es una llamada al sistema y cada una cuesta. El comentario del código lo cuantifica: en un mapa de 300×300, 600 llamadas en vez de 90 000. Es la misma lección que ft_print_comb2 (C00) componiendo un buffer de 5 bytes, a otra escala.

ojoLo que se escapa

Probado: compilado y ejecutado tal cual
Qué te obliga a aprender — Que en un proyecto con Moulinette los casos límite no son un extra: son el examen. Un split que «limpia» las líneas vacías es cómodo para parsear, pero borra justo la información que hace falta para rechazar un mapa mal formado.

?Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado a fondo. Están agrupadas en: el algoritmo, entrada y errores, memoria y entrega, y puntos débiles. Antes de mirar la respuesta, intenta contestar tú.

El algoritmo

Explícame cómo encuentras el cuadrado.

Recorro el mapa en orden de lectura. Cada casilla vacía es una posible esquina superior izquierda: desde ella pruebo cuadrados empezando por el récord + 1 y voy creciendo mientras no me salga del mapa. Si un cuadrado tiene un obstáculo, abandono esa esquina; si no y es mayor que el récord, guardo fila, columna y lado en sq[3]. → ft_bsq_isolver

Si hay dos cuadrados igual de grandes, ¿cuál pintas y dónde está ese código?

El de más arriba y, entre esos, el de más a la izquierda, como pide el enunciado. No hay código específico: sale del orden de recorrido y de que el récord solo se cambia con < estricto, así que un empate encontrado después nunca reemplaza al primero. → ft_bsq_isolver

¿Es rápido? ¿Conoces otra forma de hacerlo?

La búsqueda poda bastante (récord + 1 y corte al primer obstáculo), y en mapas de 1000×1000 con obstáculos va rápida; lo lento es la lectura. La alternativa clásica es la programación dinámica: el lado del cuadrado que acaba en cada casilla es 1 + el mínimo de sus tres vecinos de arriba e izquierda, en una sola pasada. → ft_bsq_isolver, programación dinámica

Entrada y errores

¿Qué mapas dan map error?

Cabecera de menos de 4 caracteres, con algo que no sean dígitos delante de los símbolos, con símbolos no imprimibles o repetidos, o con altura 0; un número de líneas distinto del de la cabecera; filas de distinto ancho; caracteres que no sean vacío u obstáculo (también el de lleno); un fichero vacío o que no se puede abrir. → la cabecera, la validación

¿Qué hace sin argumentos? ¿Y con varios ficheros, si uno no existe?

Sin argumentos lee un único mapa del descriptor 0, así que vale ./bsq < mapa o cat mapa | ./bsq. Con varios, cada fichero va por separado con una línea en blanco entre salidas: el que no existe saca su map error y el programa sigue con el siguiente. → main, la lectura

¿Cómo sabes que el cuadrado no se sale del mapa?

Por las condiciones del while: antes de crecer, tmp <= height - i[0] y tmp < width - i[1], así que tras el tmp++ el cuadrado llega como mucho a la última fila y la última columna. Y el mapa ya está validado: todas las filas miden width y hay exactamente height. → ft_bsq_isolver

Memoria y entrega

¿Hay leaks, también cuando el mapa es inválido?

No. Todo error de parseo pasa por ft_parse_error, que libera el split y la estructura, y los mapas válidos se liberan en ft_run_map tras pintarlos. Valgrind no da fugas ni con un mapa válido seguido de un fichero que no existe ni con un mapa de filas desiguales. → la validación, fugas

¿Usas alguna función no autorizada? ¿Pasa la norminette?

No. El ejecutable solo importa open, close, read, write, malloc y free (lo comprueba nm -u bsq); ft_atoi, ft_split y ft_strlen son propias. Todos los ficheros pasan la norminette. → t_map, la Norma

Puntos débiles (mejor tener la respuesta preparada)

¿Funciona un mapa cuyo carácter vacío es un dígito?

No. Con la cabecera 21ox (2 filas, vacío '1'), ft_atoi lee 21 y el mapa sale como map error. La comprobación de dígitos mira solo los len - 3 primeros caracteres, pero la conversión no se para ahí. → la cabecera

¿Qué pasa con una línea vacía en medio del mapa?

Que se acepta: ft_split funde los '\n' seguidos y la línea desaparece. 1.ox, una línea vacía y ... se resuelve como mapa de una fila. Lo mismo con un mapa cuya última línea no acaba en '\n'. → lo que se escapa

¿Por qué tarda unos segundos con un mapa grande?

Por la lectura, no por la búsqueda: cada trozo de 255 bytes se pega copiando todo lo leído hasta entonces, y eso es cuadrático en el tamaño del fichero. Se arreglaría leyendo trozos mucho más grandes o duplicando la reserva cada vez que se llena. → la lectura

Sobre el trabajo

Es un proyecto en grupo: ¿qué hizo cada uno?

Esta te la tienes que preparar tú. El enunciado avisa de que cada persona del grupo debe entender todo el proyecto y de que se comprobará en la defensa, así que cualquiera puede tener que explicar la lectura, la validación o el algoritmo. Un cambio en directo probable: aceptar dígitos como símbolos o rechazar las líneas vacías.