C Piscine — Rush 01

El puzle de los rascacielos (skyscrapers): rellenar una cuadrícula N×N con alturas de 1 a N sabiendo cuántos edificios se ven desde cada borde. El primer problema de la piscine que no se resuelve con una fórmula, sino probando — y que obliga a pensar en cuánto cuesta probar.

El puzle — Cada casilla es un edificio de altura 1…N; en cada fila y en cada columna no se repite ninguna altura (es un cuadrado latino). Alrededor de la cuadrícula hay 4N pistas: cuántos edificios ve alguien que mira desde ese borde, teniendo en cuenta que uno alto tapa a los bajos que tiene detrás. El programa recibe las pistas en un solo argumento, en este orden: columnas vistas desde arriba, columnas desde abajo, filas desde la izquierda y filas desde la derecha. Si hay solución la imprime; si no, Error.
$> ./rush-01 "4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2"
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
El enunciado clásico es de 4×4; este grupo lo generalizó para que el tamaño salga del número de pistas (de 3×3 en adelante). No hay PDF del enunciado en el pack. Es trabajo de grupo: la cabecera de rush01.c la firma otra persona del grupo; el repo vive en packs/piscine/017_rush01/repo/ex00/.

GGlosario de teoría

El Rush 01 es el primer encuentro con la combinatoria y con la búsqueda de soluciones por prueba y error. La página usa palabras de las matemáticas, de la teoría de algoritmos y de cómo C guarda los datos; aquí está cada una explicada desde cero y con un ejemplo sacado del propio rush. 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.

El puzle y la combinatoria

Cuadrado latino

Una cuadrícula N×N rellena con N símbolos de forma que ninguno se repite en una fila ni en una columna. Un sudoku resuelto es un cuadrado latino 9×9 con una regla más (las cajas de 3×3).

Toda solución del puzle de los rascacielos es un cuadrado latino con las alturas 1…N. La solución del ejemplo, 1 2 3 4 / 2 3 4 1 / 3 4 1 2 / 4 1 2 3, lo es: cada fila es la anterior desplazada una posición. El rush garantiza las filas porque las construye como permutaciones, y las columnas las comprueba ft_diff_col.

Permutación

Una forma de ordenar un conjunto de elementos, usando cada uno exactamente una vez. 3 1 2 es una permutación de {1, 2, 3}; 3 1 1 no, porque repite el 1 y le falta el 2.

Cada fila válida del puzle es una permutación de 1…N. Por eso el rush no rellena casillas sueltas: elige una permutación entera para cada fila, y así una fila nunca puede repetir altura.

Factorial (N!)

El producto de todos los enteros de 1 a N: 4! = 4·3·2·1 = 24. Por convenio 0! = 1. Es el número de permutaciones de N elementos: hay N candidatos para la primera posición, N−1 para la segunda, y así hasta 1.

ft_factorial lo calcula de forma recursiva (n * ft_factorial(n - 1), con 1 para 0 y 1). El rush lo usa dos veces: ft_factorial(size) es cuántas permutaciones prueba por fila (24 en un 4×4, 120 en un 5×5) y ft_ordcom lo necesita para numerarlas.

Orden lexicográfico

El orden del diccionario: se compara el primer elemento, y solo si empatan se mira el segundo, y así sucesivamente. Aplicado a permutaciones de 1 2 3: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.

ft_ordcom recorre las permutaciones en este orden: la número 0 es 1 2 3 4, la 23 (la última de un 4×4) es 4 3 2 1, y la 10 es 2 4 1 3, como se ve en la tabla de la sección de ft_ordcom.

Sistema factorial de numeración

Una forma de escribir enteros en la que cada cifra tiene su propia base: la de la derecha vale 0!, la siguiente 1!, luego 2!, 3!… Igual que 345 en base 10 es 3·100 + 4·10 + 5, en sistema factorial el 10 se escribe 1 2 0 0: 1·3! + 2·2! + 0·1! + 0·0!. Cada cifra de la posición k puede valer de 0 a k.

La gracia es que esas cifras dicen directamente qué permutación es: «toma la 2.ª altura libre, luego la 3.ª de las que quedan, luego la 1.ª, luego la 1.ª». Es exactamente lo que hacen las divisiones y restos de ft_ordcom con i = 10. A esta numeración también se la llama código de Lehmer.

Explosión combinatoria

Cuando el número de casos posibles crece tan deprisa con el tamaño que probarlos todos deja de ser viable. Los factoriales y las potencias crecen más rápido que cualquier mejora de hardware: 4! es 24, pero 6! es 720 y 9! ya es 362 880.

En el rush, si se probaran todas las combinaciones de filas serían (N!)N cuadrículas: 244 ≈ 330 000 para 4×4 y 7206 ≈ 1,4·1017 para 6×6. Por eso el programa resuelve 5×5 al instante y con 6×6 no termina en un minuto.

Buscar una solución

Fuerza bruta

Resolver un problema probando todas las candidatas posibles hasta dar con una que cumpla. Es siempre correcto si se prueba todo, y muchas veces es demasiado lento.

La idea de partida del rush es fuerza bruta: probar permutaciones fila a fila. Lo que la hace manejable hasta 5×5 es la poda por filas.

Backtracking (vuelta atrás)

Una forma ordenada de fuerza bruta: se construye la solución paso a paso; en cada paso se elige una opción, se comprueba que no rompe nada y se pasa al siguiente. Si más adelante todo falla, se vuelve atrás al último paso con opciones sin probar y se elige la siguiente.

ft_skyline_isolver es eso: el paso es la fila p, las opciones son las N! permutaciones, y volver atrás es simplemente que la llamada de la fila p + 1 devuelve 0 y el bucle de la fila p sigue con i_com + 1.

Recursión y caso base

Una función es recursiva si se llama a sí misma con un problema más pequeño, hasta llegar a un caso base que se resuelve sin volver a llamarse. Cada llamada pendiente guarda sus variables locales en la pila de llamadas.

ft_skyline_isolver(…, p) se llama con p + 1; el caso base es p == size, cuando ya no quedan filas y solo hay que mirar las columnas. Como mucho hay size + 1 llamadas anidadas, así que la pila de llamadas no es problema. ft_factorial también es recursiva, con caso base en n <= 1.

Poda

Descartar una rama entera de la búsqueda en cuanto se sabe que no puede llevar a una solución, sin explorar lo que cuelga de ella. Cuanto antes se poda, menos se prueba.

El rush poda por filas: si una permutación no cumple las pistas de izquierda y derecha, no se baja a la fila siguiente. Las columnas, en cambio, no podan nada porque solo se miran con la cuadrícula completa; comprobarlas fila a fila (que no se repita altura en ninguna columna) cortaría muchas más ramas.

Invariante de bucle

Una afirmación que es cierta antes de cada vuelta de un bucle y que la vuelta mantiene. Sirve para convencerse de que el bucle hace lo que debe: si es cierta al principio y cada vuelta la conserva, al terminar sigue siéndolo.

En ft_check_row_left: «max es la altura más alta entre las casillas ya vistas y count cuántas de ellas se ven». Al acabar, count es justamente la pista que hay que comparar.

C y memoria

Máquina de estados

Un programa que en cada momento está en uno de unos pocos estados y, según lo que lee, pasa a otro. Es la forma más sencilla de reconocer un formato carácter a carácter.

ft_is_valid_arg tiene dos estados: check = 0 («espero un dígito») y check = 1 («espero un espacio»). Un dígito en el estado 0 cuenta una pista y pasa al 1; un espacio en el estado 1 vuelve al 0; cualquier otra cosa detiene el bucle.

De carácter a dígito y vuelta

En ASCII los dígitos '0'…'9' son los códigos 48…57, seguidos. Por eso restar '0' (48, o 0x30 en hexadecimal) a un carácter dígito da su valor, y sumárselo a un número de 0 a 9 da su carácter.

ft_parse_arg hace *str - 0x30 para pasar de '3' a 3, y ft_putmatrix hace matrix[i][j] + '0' para el camino contrario. Solo funciona con una cifra: una altura 10 saldría como ':'.

División entera y resto

Entre enteros, / da el cociente sin decimales (10 / 6 es 1) y % el resto (10 % 6 es 4). Juntos descomponen un número: 10 = 1·6 + 4.

Es la herramienta de ft_ordcom: el cociente i / (N−1−j)! elige la altura de la posición j y el resto i % (N−1−j)! pasa a la siguiente.

Arrays de dos dimensiones

int pos[9][9] son 81 enteros seguidos en memoria, fila tras fila; pos[i][j] está en la posición i·9 + j. El tamaño es fijo y se decide al compilar. Al pasarlo a una función, en realidad se pasa la dirección de la primera fila, así que la función escribe en el array original y no en una copia.

Por eso ft_setcom puede rellenar la fila p de sol, que vive en main. Las tablas son de 4×9 (pistas) y 9×9 (cuadrícula), declaradas como variables locales: el rush no usa malloc.

Desbordamiento de buffer

Escribir o leer fuera de los límites de un array. C no lo comprueba: a[9] en un array de 9 elementos accede a lo que haya justo detrás en memoria, que puede ser otra variable. Es comportamiento indefinido: puede funcionar, dar resultados raros o romper el programa.

En el rush, main acepta size 10 pero inp tiene filas de 9: con 40 pistas, ft_parse_arg escribe fuera de la tabla.

AddressSanitizer

Una herramienta del compilador que se activa con -fsanitize=address: añade comprobaciones a cada acceso a memoria y, cuando uno se sale de su sitio, para el programa y dice dónde. Sirve para ver desbordamientos que sin ella pasarían desapercibidos.

Compilando el rush con ella y pasando 40 pistas 1, el informe empieza por AddressSanitizer: stack-buffer-overflow en ft_parse_arg.c:28, la línea inp[i][j] = *str - 0x30;.

Código de salida

El número que devuelve main llega al sistema como resultado del programa: 0 quiere decir «todo bien» y cualquier otro valor, «algo falló». En la terminal se ve con echo $? justo después de ejecutar.

El rush devuelve 0 cuando imprime una solución y 1 en todos los casos de Error (argumentos de más o de menos, pistas mal contadas, sin solución).

entradaft_is_valid_arg y ft_parse_arg

Entrega: ex00/ft_is_valid_arg.c, ex00/ft_parse_arg.cUsa: write

La validación es una pequeña máquina de dos estados: check vale 0 cuando se espera un dígito y 1 cuando se espera un espacio. Así se aceptan solo dígitos sueltos separados por un espacio. El número de pistas tiene que ser múltiplo de 4, y el tamaño es ese número dividido entre 4.

	while (*str)
	{
		if (('1' <= *str && *str <= '9') && !check)
		{
			length++;
			check = 1;
			str++;
		}
		else if (*str == ' ' && check)
		{
			check = 0;
			str++;
		}
		else
			break ;
	}
	if (length % 4 == 0)
		return (length / 4);
	return (0);

Después, ft_parse_arg vuelca los dígitos en int inp[4][9]: una fila por borde (arriba, abajo, izquierda, derecha) y size pistas en cada una. Aquí sí se comprueba que ninguna pista pase de size.

		if (j >= size)
		{
			j = 0;
			i++;
		}
		if ('1' <= *str && *str <= ('0' + size))
		{
			inp[i][j] = *str - 0x30;
			j++;
		}
Qué te obliga a aprender — Que validar la entrada es la mitad del programa. Un parser con estado (check) es la forma más simple de reconocer un formato, y es el germen de los autómatas que aparecerán más adelante (minishell, por ejemplo). Y que las tablas de tamaño fijo ([4][9]) imponen un tope que hay que defender en main.

vistasft_check_row_left / right, ft_check_col_top / bottom

Entrega: ex00/ft_check_row.c, ex00/ft_check_col.cUsa: write

Contar cuántos edificios se ven es llevar el máximo visto hasta ahora: cada vez que aparece uno más alto que todos los anteriores, se ve, y pasa a ser el nuevo máximo. Las cuatro funciones son la misma idea recorriendo en cuatro sentidos; para mirar desde la derecha o desde abajo se lee el índice al revés (size - i - 1).

	while (i < size)
	{
		if (max < pos[p][i])
		{
			max = pos[p][i];
			count++;
		}
		i++;
	}
	if (count == inp[2][p])
		return (1);
Qué te obliga a aprender — A traducir una regla del mundo real («uno alto tapa a los de detrás») a un invariante de bucle: «max es el edificio más alto visto hasta i». Escribir la misma función cuatro veces cambiando solo el recorrido también deja ver el coste de no tener todavía punteros a función (C11).

claveft_ordcom — la permutación número k

Entrega: ex00/rush01.c, ex00/ft_factorial.cUsa: write

La pieza más original del rush. Una fila válida es una permutación de 1…N, y hay N! de ellas. En vez de generarlas con recursión, el grupo las numera: dada una i entre 0 y N!−1, ft_ordcom construye directamente la permutación que ocupa ese puesto en orden lexicográfico. ava marca qué alturas están ya usadas (0 = libre).

	j = 0;
	while (j < size)
	{
		t = i / ft_factorial(size - 1 - j);
		i_ava = 0;
		while (i_ava < size && t >= 0)
		{
			if (ava[i_ava] == 0)
				t--;
			i_ava++;
		}
		ava[i_ava - 1] = 1;
		pos[p][j] = i_ava;
		i = i % ft_factorial(size - 1 - j);
		j++;
	}

Es el sistema factorial de numeración: en la posición j, el cociente i / (N−1−j)! dice cuál de las alturas que quedan libres va ahí, y el resto pasa a la posición siguiente. Por ejemplo, con N = 4 e i = 10:

posicióncocientelibreseligeresto
010 / 3! = 11 2 3 4la 2.ª → 210 % 6 = 4
14 / 2! = 21 3 4la 3.ª → 44 % 2 = 0
20 / 1! = 01 3la 1.ª → 10
30 / 0! = 03la 1.ª → 30

La permutación número 10 es 2 4 1 3. ft_setcom solo prepara ava (libres las size primeras, ocupadas el resto) antes de llamar a ft_ordcom.

Qué te obliga a aprender — Que se puede numerar un espacio de búsqueda: si sabes contar las soluciones posibles (N!), puedes recorrerlas con un simple entero en lugar de con estructuras. Es la misma idea que hay detrás de convertir un número de base 10 a otra base (C04), solo que aquí cada cifra tiene su propia base. De paso, el ejercicio de factorial de C05 deja de ser un ejercicio y se convierte en herramienta.

solverft_skyline_isolver — backtracking por filas

Entrega: ex00/rush01.cUsa: write

La recursión va fila a fila (p). Para la fila actual prueba las N! permutaciones; si una cumple las pistas de izquierda y derecha, baja a la fila siguiente. Si desde ahí se llega a una solución, devuelve 1 hacia arriba sin probar más; si no, sigue con la siguiente permutación de esta fila.

	while (i_com < ft_factorial(size) && p < size)
	{
		ft_setcom(pos, size, i_com, p);
		if (ft_check_row_left(inp, size, pos, p)
			&& ft_check_row_right(inp, size, pos, p))
		{
			r = ft_skyline_isolver(inp, size, pos, p + 1);
			if (r == 1)
				return (r);
		}
		i_com++;
	}
	if (p == size)
		r = ft_check_col(inp, size, pos) && ft_diff_col(pos, size);
	else
		r = 0;
	return (r);

Cuando p == size el bucle ni entra: todas las filas están puestas y lo que queda es comprobar las columnas. Ese es el caso base.

Qué te obliga a aprender — El esqueleto del backtracking: elegir, comprobar, bajar un nivel y, si falla, deshacer y probar la siguiente opción. Aquí «deshacer» es gratis porque la fila p se sobrescribe con la siguiente permutación. Es el mismo patrón que ft_print_combn (C00) o las diez reinas (C05), ahora con poda: las filas que no cumplen sus pistas cortan una rama entera.

finalColumnas: ft_check_col y ft_diff_col

Entrega: ex00/ft_check_col.c, ex00/ft_diff_col.cUsa: write

Las filas no repiten alturas por construcción (son permutaciones), pero las columnas sí podrían. ft_diff_col compara cada casilla con todas las de debajo en su columna, y ft_check_col comprueba las pistas de arriba y de abajo. Las dos se ejecutan solo cuando la cuadrícula está completa.

			z = i + 1;
			while (z < size)
			{
				if (pos[i][j] == pos[z][j] && i != z)
					return (0);
				z++;
			}

(El i != z sobra: z empieza en i + 1.)

Qué te obliga a aprender — Dónde poner cada comprobación es una decisión de diseño con consecuencias de rendimiento. Comprobar las columnas al final es lo más sencillo de escribir, pero significa que una columna con dos alturas iguales en las dos primeras filas no se detecta hasta haber rellenado todas las demás.

salidaft_putmatrix y main

Entrega: ex00/ft_putmatrix.c, ex00/rush01.cUsa: write

ft_putmatrix escribe cada altura como dígito, con espacio entre columnas y salto de línea al final de la fila. main encadena todo y responde Error (con código de salida 1) si falta el argumento, si el número de pistas no cuadra o si no hay solución.

	size = ft_is_valid_arg(argv[1]);
	if (size < 3 || size > 10)
	{
		write(1, "Error\n", 6);
		return (1);
	}
	ft_parse_arg(inp, argv[1], size);
	if (ft_skyline_isolver(inp, size, sol, 0))
		ft_putmatrix(sol, size);
Qué te obliga a aprender — A separar el programa en piezas que se pueden probar solas (parsear, resolver, imprimir) y repartirlas en el grupo. Ocho ficheros para un rush de fin de semana es justo eso: cada persona se lleva una pieza, pero en la defensa hay que saber explicar las de los demás.

ojoLímites y coste

Probado: 3×3, 4×4 y 5×5 resuelven al instante; 6×6 no termina en 60 s
Qué te obliga a aprender — Que «funciona con el ejemplo» no es lo mismo que «funciona». Generalizar de 4×4 a N×N es buena idea, pero trae dos obligaciones: que los límites de las tablas coincidan con los que acepta main, y que el algoritmo aguante el crecimiento. Las factoriales crecen más deprisa que cualquier ordenador.

?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. En un rush la pregunta puede ir a cualquiera del grupo, sobre cualquier fichero. Antes de mirar la respuesta, intenta contestar tú.

El algoritmo

Explícame cómo resuelve el puzle.

Con backtracking por filas, una fuerza bruta ordenada: para la fila p prueba las N! permutaciones; si una cumple las pistas de izquierda y derecha, se llama a sí mismo con la fila p + 1. Cuando están todas puestas (p == size) comprueba las columnas: pistas de arriba y abajo, y que no se repita ninguna altura. Si falla, vuelve a la fila anterior y prueba la permutación siguiente. → ft_skyline_isolver

¿Cómo generas las permutaciones?

No se generan con recursión: se numeran. ft_ordcom recibe un número i de 0 a N!−1 y construye la permutación que ocupa ese puesto en orden lexicográfico, dividiendo entre factoriales: el cociente elige cuál de las alturas libres va en cada posición y el resto pasa a la siguiente. La 10 de un 4×4 es 2 4 1 3. → ft_ordcom

¿Cómo cuentas los edificios que se ven?

Recorriendo desde el borde con el máximo visto hasta ahora: si la casilla es más alta que max, se ve, se suma 1 y pasa a ser el nuevo máximo. Desde la derecha o desde abajo se lee el índice al revés, size - i - 1. → contar edificios visibles

¿Dónde compruebas que no se repitan alturas?

En las filas no hace falta: cada fila es una permutación, así que no puede repetir. En las columnas sí, y lo hace ft_diff_col, pero solo con la cuadrícula completa. → columnas

Entrada y casos límite

¿Qué entradas dan Error?

Sin argumento o con más de uno; un número de pistas que no es múltiplo de 4 o que da un tamaño fuera de 3…10 (con 15 pistas, o con dos espacios seguidos, que cortan la validación antes de tiempo); y un puzle sin solución ("1 1 1 1 …"). En todos los casos sale Error y el código de salida es 1. → entrada, main

¿Y si después de las pistas hay basura, como "… 2 2 2x"?

Se acepta y lo resuelve como si no estuviera. ft_is_valid_arg para en la x pero ya ha contado 16 pistas, así que devuelve 4; ft_parse_arg llega a la x con todo inp relleno y devuelve 0, pero main no mira el retorno. Mejor tenerlo reconocido antes de que lo encuentren: bastaría con exigir que la validación llegue al final de la cadena. → entrada, ojo

¿Hasta qué tamaño funciona?

3×3, 4×4 y 5×5 se resuelven al instante; 6×6 no termina en un minuto por la explosión combinatoria: (N!)N cuadrículas en el peor caso. Y aunque main deja pasar hasta 10, las tablas son de 9: con 40 pistas se escribe fuera de inp, y con 9×9 ft_ordcom lee ava[9]. El tope correcto sería 9. → límites y coste

Memoria y reglas

¿Hay leaks? ¿Dónde se reserva memoria?

En ninguna parte: no hay malloc. Todas las tablas (inp[4][9], sol[9][9], ava[9]) son variables locales de tamaño fijo, así que no hay nada que liberar. El precio es el tope de 9 que impone ese tamaño fijo. → arrays de dos dimensiones

¿Cómo lo harías más rápido?

Podando antes: comprobar al poner cada fila que no repite ninguna altura en las columnas ya rellenas, y descartar pronto las columnas que ya no pueden cumplir su pista. Y guardar ft_factorial(size) en una variable en lugar de recalcularlo en cada vuelta. → poda, columnas

¿Pasa la Norma? ¿Por qué cuatro funciones casi iguales?

norminette da OK! en los ocho ficheros. Las cuatro funciones de vistas son la misma idea con cuatro recorridos; unirlas en una exigiría pasar el sentido como parámetro, y con el límite de 25 líneas y 4 parámetros por función de la Norma es más sencillo tenerlas separadas. → contar edificios visibles

Sobre el trabajo en grupo

¿Quién hizo qué? ¿Cómo os repartisteis los ocho ficheros?

Esta te la tienes que preparar tú. Las piezas se separan bien (validar y parsear, contar vistas, permutaciones, resolver, imprimir), pero en la defensa cualquiera del grupo tiene que poder explicar todas, y la que más se pregunta es ft_ordcom. → ft_ordcom