C Piscine — C 00

Primer módulo de C. Una sola función autorizada en todo el módulo: write. Nueve ejercicios que van de imprimir un carácter a generar combinatorias con recursión — todo construido desde un único byte.

Por qué solo write — Es la decisión pedagógica que define el módulo. printf es una función gigante de la librería estándar que formatea, bufferea y esconde todo lo interesante. write(fd, buf, n) es la llamada al sistema desnuda: "kernel, escribe estos n bytes de esta dirección en este descriptor". Quitándote printf, 42 te obliga a descubrir que todo lo demás se construye: imprimir un número, un alfabeto o una tabla es siempre, al final, empujar bytes uno a uno por el descriptor 1 (stdout). Cuando en C04 reimplementes putnbr y en el cursus escribas tu propio printf, este será el único ladrillo de base. (El prólogo del enunciado — la "mermelada de fideos" de Pierre Dac, humorista francés — es puro absurdo intencional: dos páginas de receta imposible que terminan en "C sí que vale la pena".)

GGlosario de teoría

C 00 es el primer contacto con C, así que casi todo es nuevo: qué es compilar, qué es una función, por qué un carácter es un número, qué hace write con un &, por qué -2147483648 da problemas. Aquí está cada idea explicada desde cero, con un ejemplo sacado del propio módulo (las salidas están ejecutadas). 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.

Compilar y entregar

Compilar, cc y las flags -Wall -Wextra -Werror

El ordenador no ejecuta C: ejecuta código máquina. Compilar es traducir tus .c a un ejecutable, y lo hace el compilador, que en 42 se llama con cc. cc main.c ft_putchar.c genera un a.out que ya se puede lanzar con ./a.out.

Las flags que pide el enunciado activan los avisos (warnings): -Wall y -Wextra encienden la mayoría (variable sin usar, comparación sospechosa, función sin declarar…), y -Werror convierte cada aviso en error, así que el código con avisos ni siquiera compila. La Moulinette compila así: un aviso es un cero.

main: función frente a programa

Un programa en C empieza siempre por la función main. En C 00 no se piden programas sino funciones: se entrega solo ft_putchar.c, sin main, y la Moulinette lo compila junto a su propio main de pruebas. Si el tuyo también lo tiene, hay dos main y el enlazado falla (multiple definition of `main'). Para probar, escribe el main en otro archivo que no entregues, o déjalo comentado, como permite el enunciado.

La Norma y norminette

La Norma es el reglamento de estilo de 42 y es obligatoria: si no se cumple, la nota es 0 aunque el código funcione. Algunas reglas que ya se notan en C 00: nada de for (solo while), como mucho 25 líneas por función y 5 funciones por archivo, como mucho 5 variables por función, declaradas al principio y separadas del resto por una línea en blanco, sangría con tabuladores, y el header de 42 (el recuadro de comentarios con tu login) al principio de cada archivo.

norminette es el programa que comprueba buena parte de esas reglas. En este módulo se ejecuta con -R CheckForbiddenSourceHeader, como hará la Moulinette. No lo comprueba todo: quien te evalúa puede encontrar faltas que norminette no ve.

Moulinette

El corrector automático de 42 (en francés, el pasapurés). Después de la evaluación entre pares, compila tus funciones con su propio main, las llama con sus casos y compara la salida byte a byte. No admite discusión. Corrige en orden: si un ejercicio falla, los siguientes no cuentan aunque estén bien.

#include y <unistd.h>

Para usar una función, el compilador tiene que conocer antes su prototipo. Las de la librería del sistema están declaradas en cabeceras (archivos .h), y #include <unistd.h> pega esas declaraciones al principio de tu archivo. En unistd.h está write. Sin el include, -Wall -Werror da error por usar una función sin declarar.

Lo básico de C

Función, prototipo y void

Una función es un trozo de código con nombre que recibe parámetros y puede devolver un valor. Su prototipo es la primera línea: tipo de retorno, nombre y parámetros. El enunciado lo fija, y la Moulinette solo podrá llamar a tu función si coincide exactamente:

void	ft_is_negative(int n);

void como tipo de retorno significa «no devuelve nada» (todas las de C 00 solo imprimen), y entre los paréntesis, como en ft_print_alphabet(void), «no recibe nada».

Tipos: char, int y long

Cada variable tiene un tipo que dice cuántos bytes ocupa y qué valores caben. En una máquina Linux de 64 bits como las de 42, sizeof da 1 para char, 4 para int y 8 para long. Un char es un número de 8 bits (de −128 a 127); un int, de 32 bits, va de −2147483648 a 2147483647; un long llega a unos 9,2 trillones.

Al mezclar tipos, C convierte el pequeño al grande sin avisar: en n = nb; de ft_putnbr, el int se copia a un long sin perder nada. El tamaño de long depende del sistema (en Windows es de 4 bytes), pero en 42 se trabaja en Linux o macOS, donde es de 8.

ASCII: los caracteres son números

El ordenador no guarda letras: guarda números, y una tabla dice qué carácter corresponde a cada uno. La tabla básica es ASCII (1963): 128 códigos en los que '0'–'9' van del 48 al 57, 'A'–'Z' del 65 al 90 y 'a'–'z' del 97 al 122, siempre seguidos y en orden. Por eso se puede contar con letras:

printf("%d %d %d %c\n", 'a', 'z', '0', 'a' + 1);
97 122 48 b

De ahí salen ex01–ex03 (un contador que va de 'a' a 'z') y el truco de ex06 y ex07: un dígito d se convierte en su carácter con d + '0' (3 + 48 = 51, que es '3').

Literal de carácter 'N' frente a cadena "N"

Con comillas simples, 'N' es un solo número, el 78. Con dobles, "N" es una cadena: un trozo de memoria con los bytes N y \0 (el terminador), y lo que vale la expresión es la dirección de ese trozo. Por eso en ex04 write(1, "N", 1) funciona sin &: la cadena ya es una dirección. Con write(1, 'N', 1) se le pasaría el número 78 como si fuera una dirección (el compilador avisa y, con -Werror, no compila).

Bucle while: inicio, condición y avance

while (condición) { … } repite el bloque mientras la condición sea verdadera, y la comprueba antes de cada vuelta. Todo bucle de contador tiene tres piezas: el valor inicial (antes del while), la condición de parada y el avance (al final del bloque). En ex01:

c = 'a';             // inicio
while (c <= 'z')     // condición
{
	write(1, &c, 1);
	c++;                 // avance
}

Si falta el avance, el bucle no acaba nunca. Si la condición es < en vez de <=, falta la última letra. La Norma prohíbe for, que junta las tres piezas en una línea.

Función static (función auxiliar)

Una función marcada static solo existe dentro de su archivo: nadie de fuera puede llamarla y su nombre no choca con otra igual en otro archivo. Es lo indicado para las funciones auxiliares, las que solo sirven a la función pedida. En el repo lo son ft_print_trio (ex05), ft_print_pair (ex06), ft_print_tab y ft_rec (ex08). Partir así el código además ayuda a cumplir el límite de 25 líneas por función de la Norma.

Array

Una fila de variables del mismo tipo, seguidas en memoria, a las que se accede por posición empezando en 0. char s[5]; son cinco char, de s[0] a s[4]; s[5] ya está fuera y escribir ahí es un error grave. En ex06, s guarda los 5 caracteres de "00 01" para imprimirlos con un solo write; en ex08, int tab[10] guarda los dígitos de la combinación que se está construyendo.

Memoria y salida

write y llamada al sistema

Una llamada al sistema es pedirle algo directamente al núcleo del sistema operativo (el kernel), que es el único que puede tocar la pantalla, los discos o la red. write es la de escribir:

ssize_t	write(int fd, const void *buf, size_t count);

«Escribe count bytes, empezando en la dirección buf, en el descriptor fd». Devuelve cuántos bytes ha escrito, o −1 si falla; en C 00 nadie mira ese valor. No sabe nada de números ni de formatos: printf, que sí formatea, está construida encima, y por eso aquí no se puede usar.

Descriptor de fichero (fd)

Un número pequeño con el que un programa se refiere a algo abierto: un archivo, la terminal, una tubería. Todo programa arranca con tres: 0 es la entrada estándar (stdin), 1 la salida estándar (stdout) y 2 la salida de error (stderr). El 1 de write(1, &c, 1) es stdout, que es lo que la Moulinette captura y compara.

Dirección de memoria, & y puntero

Toda variable vive en algún sitio de la memoria, y ese sitio tiene un número, su dirección. &c es la dirección de c. Un puntero es una variable que guarda una dirección. write no recibe el carácter sino dónde está, para poder escribir uno o mil bytes seguidos con la misma llamada: write(1, &c, 1) es «el byte que hay donde vive c». En ex06 no hace falta & porque el nombre de un array, s, ya vale la dirección de su primer elemento.

Números

División entera y módulo (/ y %)

Entre enteros, / da el cociente sin decimales (se trunca hacia cero: 7 / 2 = 3 y −7 / 2 = −3) y % el resto (7 % 2 = 1). Con 10 sirven para separar las cifras de un número: 42 / 10 es 4 (lo que queda al quitar la última cifra) y 42 % 10 es 2 (la última cifra). ex06 lo usa para escribir números de dos cifras y ft_putnbr, para cualquier longitud. Ojo con los negativos: -7 % 10 es −7, no 3.

Complemento a dos y rango de int

Es como la máquina guarda los enteros con signo. Con 32 bits hay 2³² combinaciones; la mitad con el bit más alto a 1 son los negativos. Como el 0 ocupa una de las «positivas», el rango queda asimétrico: de −2147483648 (INT_MIN) a 2147483647 (INT_MAX). Hay un negativo más que positivos, así que INT_MIN no tiene opuesto dentro de un int: 2147483648 no cabe. Es el caso que el enunciado de ex07 pide explícitamente («cualquier valor posible de un int»).

Desbordamiento y comportamiento indefinido

Un desbordamiento es una operación cuyo resultado no cabe en el tipo. Con enteros con signo, C no dice qué pasa: es comportamiento indefinido, y el programa puede dar cualquier cosa. Un putnbr que niega dentro del int, con nb = -nb, lo provoca con INT_MIN. Compilado aquí, imprime -(: la negación deja el número negativo, nb % 10 vale −8 y '0' - 8 es el carácter (. Con -fsanitize=undefined el propio programa lo denuncia:

runtime error: negation of -2147483648 cannot be represented in type 'int'

El ft_putnbr del repo lo evita copiando primero a un long, donde 2147483648 sí cabe.

Algoritmos

Recursión y pila de llamadas

Una función es recursiva cuando se llama a sí misma con un problema más pequeño, y tiene un caso base en el que ya no lo hace. Cada llamada pendiente se queda esperando en la pila de llamadas con sus propias variables, y se retoma cuando la de dentro termina.

En ft_putnbr, para 123: ft_putnbr(123) llama a ft_putnbr(12), que llama a ft_putnbr(1). Esta es el caso base (1 < 10), escribe 1 y vuelve; entonces la de 12 escribe 2 y la de 123 escribe 3. Las cifras se calculan de la última a la primera, pero se imprimen al volver, en el orden correcto. Sin caso base la pila crece hasta que el programa revienta (segfault).

Combinación

Una forma de elegir k elementos de un conjunto sin que importe el orden: 012 y 210 son la misma combinación. Para no repetirlas se escribe cada una en un solo orden, el creciente, que es lo que piden ex05, ex06 y ex08. Cuántas hay es el número combinatorio C(n, k) = n! / (k!·(n−k)!): C(10, 3) = 120 tríos en ex05, C(100, 2) = 4950 parejas en ex06, y C(10, 2) = 45 para ft_print_combn(2). Si el orden importase serían variaciones y habría muchas más (720 para tres dígitos distintos).

Problema de la valla (fencepost)

Una valla de 10 metros con un poste cada metro tiene 11 postes, no 10. En programación es el error de contar uno de más o de menos (en inglés, off-by-one), y su versión más común en la piscine es el separador: 120 combinaciones llevan 119 ", ", porque va entre elementos. La salida de ex05 mide 120·3 + 119·2 = 598 bytes, y el repo los da. Las soluciones del repo lo resuelven detectando el último elemento: 789, 98 99, o en ex08 que el primer dígito sea 10 - n.

Backtracking (vuelta atrás)

Una manera de recorrer todas las soluciones construyéndolas paso a paso: se elige un valor para la primera posición, se resuelve recursivamente el resto, y al volver se prueba el siguiente valor para esa posición. Cada nivel de la recursión hace de uno de los bucles anidados de ex05, así que sirve para cualquier número de posiciones. En ft_rec de ex08, el nivel pos prueba los dígitos desde start hasta 9 y le pasa al siguiente d + 1, de modo que solo se construyen combinaciones crecientes. Es el mismo esquema que resuelve sudokus o el problema de las n reinas, donde además se abandona una rama en cuanto deja de ser válida.

ex00ft_putchar

Entrega: ft_putchar.cAutorizado: write
void	ft_putchar(char c)
{
	write(1, &c, 1);
}

El enunciado incluso da la línea. Lo que se evalúa es entender sus tres argumentos: descriptor 1 (stdout), la dirección del carácter (&c — write no recibe valores, recibe punteros a memoria) y la longitud en bytes.

Qué te obliga a aprender — Tu primer contacto con dos ideas que lo atraviesan todo: (1) las funciones del sistema trabajan con direcciones de memoria, no con valores — de ahí el &; y (2) un char no es "una letra", es un byte, un número de 8 bits. Esta función de 1 línea es el átomo del que saldrán todas las demás salidas por pantalla de la piscine.

ex01ft_print_alphabet

Entrega: ft_print_alphabet.cAutorizado: write
void	ft_print_alphabet(void)
{
	char	c;

	c = 'a';
	while (c <= 'z')
	{
		write(1, &c, 1);
		c++;
	}
}
Qué te obliga a aprender — Que los caracteres son números y se puede hacer aritmética con ellos: 'a' vale 97 en ASCII y 'a' + 1 es 'b'. Ese diseño — heredar del telégrafo una tabla donde las letras son consecutivas — es lo que permite recorrer el alfabeto con un contador. También es tu primer bucle while de la Norma: 42 prohíbe for precisamente para que veas las tres piezas del bucle (inicialización, condición, avance) por separado.

ex02ft_print_reverse_alphabet

Entrega: ft_print_reverse_alphabet.cAutorizado: write
	c = 'z';
	while (c >= 'a')
	{
		write(1, &c, 1);
		c--;
	}
Qué te obliga a aprender — Parece el mismo ejercicio y esa es la trampa: al invertir el sentido cambian tres cosas coordinadas (valor inicial, condición de parada, operador de avance). El error clásico del principiante es cambiar dos de las tres. Enseña a razonar el bucle como un invariante y no como una receta copiada.

ex03ft_print_numbers

Entrega: ft_print_numbers.cAutorizado: write
	c = '0';
	while (c <= '9')
	{
		write(1, &c, 1);
		c++;
	}
Qué te obliga a aprender — La diferencia entre el número 0 y el carácter '0' (que vale 48 en ASCII). Confundirlos es uno de los errores más comunes de todo C. La conversión digito + '0' ↔ caracter - '0' que aquí se insinúa será la pieza central de putnbr (ex07) y de atoi (C04).

ex04ft_is_negative

Entrega: ft_is_negative.cAutorizado: write
void	ft_is_negative(int n)
{
	if (n < 0)
		write(1, "N", 1);
	else
		write(1, "P", 1);
}
Qué te obliga a aprender — Dos cosas pequeñas pero deliberadas: (1) leer la especificación con lupa — el 0 es "P", y quien imprime "N" para el cero suspende: los contratos se cumplen al pie de la letra, como hará la Moulinette; y (2) que un literal de cadena "N" ya es una dirección de memoria válida para write — la primera pista de que las cadenas en C son punteros.

ex05ft_print_comb

Entrega: ft_print_comb.cAutorizado: write

Todas las combinaciones de tres dígitos distintos en orden creciente: 012, 013, …, 789.

	a = '0';
	while (a <= '7')
	{
		b = a + 1;
		while (b <= '8')
		{
			c = b + 1;
			while (c <= '9')
			{
				ft_print_trio(a, b, c);
				c++;
			}
			b++;
		}
		a++;
	}
Qué te obliga a aprender — Dos ideas de peso. Primera: generar por construcción, no filtrar. La solución ingenua enumera 000–999 y descarta; la buena hace que cada bucle empiece donde el anterior lo dejó (b = a + 1), de modo que solo se generan combinaciones válidas — así se piensa en combinatoria y en SQL, en backtracking, en todo. Segunda: el problema de la valla (fencepost): hay separador ", " entre elementos, no después de cada uno; detectar el último elemento (789) es la parte que de verdad se falla. Además obliga a decidir los límites de cada bucle (¿por qué a para en '7'?) razonando, no probando.

ex06ft_print_comb2

Entrega: ft_print_comb2.cAutorizado: write

Parejas de números de dos cifras: 00 01, 00 02, …, 98 99.

	s[0] = a / 10 + '0';
	s[1] = a % 10 + '0';
	s[2] = ' ';
	s[3] = b / 10 + '0';
	s[4] = b % 10 + '0';
	write(1, s, 5);
Qué te obliga a aprender — La descomposición posicional de un número: n / 10 da las decenas y n % 10 las unidades. La división entera y el módulo son las dos herramientas con las que un número "se convierte" en sus dígitos — putnbr (ex07) generaliza esto a cualquier longitud. De regalo: componer un buffer de 5 bytes y hacer un solo write enseña que la salida no tiene por qué ir carácter a carácter.

ex07ft_putnbr

Entrega: ft_putnbr.cAutorizado: write

Imprimir cualquier int, incluido -2147483648.

void	ft_putnbr(int nb)
{
	char	c;
	long	n;

	n = nb;
	if (n < 0)
	{
		write(1, "-", 1);
		n = -n;
	}
	if (n >= 10)
		ft_putnbr(n / 10);
	c = n % 10 + '0';
	write(1, &c, 1);
}
Qué te obliga a aprender — El ejercicio-emboscada del módulo, con dos lecciones. (1) Recursión por necesidad: los dígitos se obtienen del último al primero (n%10), pero se imprimen del primero al último — la pila de llamadas recursivas invierte el orden gratis. (2) Complemento a dos: en 32 bits el rango es [-2147483648, 2147483647] — asimétrico. -INT_MIN no cabe en un int: es comportamiento indefinido y el clásico segfault/valor basura de las malas soluciones. Pasar por long antes de negar es reconocer cómo representa los enteros la máquina. Es la primera vez que la piscine te castiga por no conocer los límites del hardware.

ex08ft_print_combn

Entrega: ft_print_combn.cAutorizado: write

Como ex05 pero con n dígitos (0 < n < 10).

static void	ft_rec(int *tab, int pos, int n, int start)
{
	int	d;

	if (pos == n)
	{
		ft_print_tab(tab, n);
		return ;
	}
	d = start;
	while (d <= 9)
	{
		tab[pos] = d;
		ft_rec(tab, pos + 1, n, d + 1);
		d++;
	}
}
Qué te obliga a aprender — La generalización que rompe el esquema anterior: en ex05 anidaste 3 bucles a mano, pero no puedes escribir "n bucles". La respuesta es que la recursión es un bucle de profundidad variable: cada nivel de la llamada es uno de los bucles anidados, y el array tab hace de estado compartido. Esto es backtracking en miniatura — el mismo esqueleto con el que se resuelven sudokus, n-reinas o cualquier "prueba todas las opciones válidas". Cierra el módulo conectando ex05 (enumeración por construcción) con ex07 (recursión).

?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 donde está explicado. En C 00 lo normal es que te pidan compilar con un main de prueba delante de ellos y que expliques cada línea, así que ten ese main preparado fuera del repo. Están agrupadas en: write y caracteres, los ejercicios, casos límite y reglas. Antes de mirar la respuesta, intenta contestar tú.

write y caracteres

¿Por qué &c y no c en write?

Porque write no recibe el valor que hay que escribir sino la dirección donde empieza, y cuántos bytes leer desde ahí. &c es la dirección de c. Con write(1, c, 1) el número del carácter se usaría como dirección: con -Wall -Wextra -Werror ni compila. → puntero, ex00

¿Qué diferencia hay entre 0 y '0'?

0 es el número cero; '0' es el carácter que se ve como un cero, cuyo código ASCII es 48. Escribir el byte 0 no enseña nada en pantalla. Por eso ex03 cuenta de '0' a '9', y para imprimir una cifra d se escribe d + '0'. → ASCII, ex03

Los ejercicios

¿Qué imprime ft_is_negative(0)?

P. El enunciado dice que el cero cuenta como positivo o nulo, y el código solo imprime N si n < 0. Probado: 0, -1 y 5 dan PNP. → ex04

En ft_print_comb, ¿por qué el primer bucle para en '7'?

Porque detrás tienen que caber dos dígitos mayores: si a fuese '8', b sería '9' y para c no quedaría nada. Por lo mismo b para en '8'. Cada bucle empieza en el anterior más uno, así que nunca se repite un dígito ni sale un trío desordenado: 120 combinaciones, sin filtrar ninguna. → combinación, ex05

¿Cómo evitas la coma después de la última combinación?

Detectando la última: ft_print_trio no escribe ", " si el trío es 789, ft_print_pair si la pareja es 98 99, y ft_print_tab si el primer dígito es 10 - n, porque la última combinación de n dígitos siempre empieza ahí (89, 789, 6789…). → problema de la valla, ex05, ex08

¿Por qué ft_putnbr es recursiva?

Porque % 10 saca las cifras de la última a la primera y hay que imprimirlas al revés. La recursión primero llama con n / 10 y escribe su cifra al volver, así que las cifras salen en orden sin necesidad de un array. La profundidad es como mucho de 10 llamadas, una por cifra. → recursión, ex07

Casos límite

¿Funciona ft_putnbr con -2147483648?

Sí: el test lo prueba y da -2147483648. El truco es copiar nb a un long antes de cambiarle el signo, porque 2147483648 no cabe en un int. Un putnbr que hace nb = -nb con int imprime aquí -(. → complemento a dos, desbordamiento, ex07

¿Qué hace ft_print_combn con n fuera de rango?

El enunciado garantiza 0 < n < 10, así que no está pedido. Con n = 10 imprime 0123456789. Con n = 0 imprime ", ": entra directo al caso base y ft_print_tab lee tab[0] sin que nadie le haya dado valor. No se cuelga ni revienta, pero si te lo preguntan, esa es la respuesta honesta. → ex08

Reglas: Norma, Moulinette y funciones autorizadas

¿Puedo usar printf?

No en lo que se entrega: la única función autorizada en todo C 00 es write, y usar otra es un cero. En el main de pruebas, que no se entrega, da igual. → write

¿Por qué no entregas un main?

Porque se piden funciones, no programas, y la Moulinette las compila con su propio main. Si el tuyo también tiene uno, el enlazado falla por multiple definition of `main'. → main

Norminette dice OK. ¿Ya cumple la Norma?

No necesariamente: norminette no comprueba todas las reglas, y la Norma la revisa también quien te evalúa. En el repo los nueve archivos pasan norminette -R CheckForbiddenSourceHeader, usan solo while, tienen el header de 42 y las funciones auxiliares son static. → Norma, static