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.
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/.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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 ':'.
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.
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.
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.
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;.
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).
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++;
}
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.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);
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).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ón | cociente | libres | elige | resto |
|---|---|---|---|---|
| 0 | 10 / 3! = 1 | 1 2 3 4 | la 2.ª → 2 | 10 % 6 = 4 |
| 1 | 4 / 2! = 2 | 1 3 4 | la 3.ª → 4 | 4 % 2 = 0 |
| 2 | 0 / 1! = 0 | 1 3 | la 1.ª → 1 | 0 |
| 3 | 0 / 0! = 0 | 3 | la 1.ª → 3 | 0 |
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.
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.
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.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.)
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);
main acepta size hasta 10, pero las
tablas son de 9 (inp[4][9], pos[9][9]). Con 40 pistas,
ft_parse_arg escribe fuera de inp (AddressSanitizer lo marca como
stack-buffer-overflow). La comprobación debería cortar en 9.ft_ordcom, while (ava[size] == 0) size++; busca el
primer 1 que puso ft_setcom; con tamaño 9 no hay ninguno dentro del array y la
lectura sigue en ava[9], fuera de rango.ft_parse_arg devuelve 0 si una pista pasa de
size, pero main no lo mira: el resto de inp queda sin
inicializar. En la práctica sale Error porque no hay solución, pero es por
casualidad.ft_factorial se recalcula en cada vuelta del bucle.ft_factorial.c queda comentada una versión con los valores a
mano, donde 8! y 9! están mal (40200 y 361800; son 40320 y 362880).
No se usa, pero se entrega.main, y que el algoritmo
aguante el crecimiento. Las factoriales crecen más deprisa que cualquier ordenador.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ú.
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
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
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
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
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
"… 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
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
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
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
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
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