Setting Up, c’est le projet de C qu’on croise en première année à Epitech. Sous le capot, c’est l’algorithme du BSQ (le plus grand carré) appliqué à une carte, avec des contraintes de C en plus. Je ne l’avais pas réussi.
Cette année, il m’est revenu en tête. Pas par défi : par ennui. J’étais entre deux tâches, avec un petit creux, et je me suis dit : et si je le refaisais ? Trois jours de travail plus tard, étalés du 18 au 27 octobre, c’est fait.
Je ne publie pas le code complet : c’est un projet noté, et le but est que tu comprennes l’idée, pas que tu la recopies.
Pourquoi je l’avais raté
Un problème de compréhension, tout simplement. L’algo me paraissait obscur. Il a fallu que plusieurs personnes me l’expliquent, et même pour la force brute naïve, qui est pourtant la version la plus bête : pour chaque case, essayer des carrés de plus en plus grands, en relisant tout à chaque fois.
Sur les petites cartes, ça passait. Sur les grosses, le programme tournait, tournait, et prenait beaucoup trop de temps. Ce n’est pas un bug mystérieux qui m’a coulé, c’est le chronomètre, et derrière lui, une carte que je ne savais pas parcourir intelligemment.
Le sujet en une phrase
On te donne une carte faite de cases vides (.) et d’obstacles (o). Il faut trouver le plus grand carré vide, puis réafficher la carte avec ce carré dessiné en x. S’il y a plusieurs carrés de la même taille, on garde le plus haut, puis le plus à gauche.
..... ..xxx
.o... .oxxx
..... → ..xxx
..... .....
..... .....Les contraintes pimentent l’exercice : seulement open, read, write, close, malloc, free et stat. Pas de printf, pas de strlen. Une erreur s’écrit sur la sortie d’erreur et le programme sort avec le code 84. Il y a aussi un second mode : ./setting_up N "motif" génère une carte de N × N en répétant un motif, puis la résout.
Le programme est un pipeline
Avant d’écrire la moindre ligne d’algorithme, j’ai découpé le programme en étapes qui ne se marchent jamais dessus :
arguments → lecture → validation → construction de la carte → calcul → marquage → affichage
Règle de base : seul main a le droit de crier. Toutes les autres fonctions retournent -1 ou NULL sans rien dire, et main libère la mémoire, écrit le message, retourne 84.
Petit détail qui a l’air de rien : le 84 ne doit jamais servir de valeur de retour interne. Sinon, une carte valide de 84 lignes serait traitée comme une erreur, et tu passerais une soirée à te demander pourquoi.
L’idée : on ne cherche pas des carrés, on les fait grandir
La force brute, c’est ce que j’avais fait : pour chaque case, essayer des carrés de plus en plus grands. En version naïve, c’est du O(n·m·k³). Sur 1000 × 1000, ton ordinateur prend un café et ne revient pas.
La programmation dynamique renverse le problème. On remplit un tableau où chaque case contient une seule information :
dp[i][j]= le côté du plus grand carré vide dont le coin bas-droit est la case(i, j).
La règle de remplissage tient en trois lignes, celles qui m’avaient échappé la première fois :
obstacle → 0
première ligne ou colonne → 1
sinon → 1 + min(haut, gauche, diagonale)Pourquoi min et pas max ?
Imagine que tu veux poser un carré de côté 4 dont le coin bas-droit est ta case. Il faut que les trois voisins (au-dessus, à gauche, en diagonale) portent chacun un carré de côté 3. Si l’un des trois est plus petit, c’est le maillon faible : il limite tout le monde. D’où le min. Avec un max, tu inventerais des carrés qui contiennent des obstacles, et ta carte ressemblerait à un fromage.
Le départage tient dans un seul caractère
On parcourt la carte ligne par ligne, de gauche à droite, et on retient un nouveau meilleur carré uniquement si sa taille est strictement plus grande : > et pas >=.
À taille égale, c’est donc le premier trouvé qui reste, le plus haut puis le plus à gauche. Avec >=, tu obtiens le plus bas et le plus à droite. La taille est juste, la réponse est fausse, et tu cherches pendant longtemps un bug qui tient en un caractère.
Dernier piège de cette partie : le calcul donne le coin bas-droit, mais pour dessiner il faut le coin haut-gauche. Il faut donc convertir, (i - taille + 1, j - taille + 1), et on l’oublie facilement.
Les pièges classiques (dans le C, pas dans l’algo)
Cette fois, je n’ai pas vraiment perdu de temps dessus. Mais ce sont ceux qui coûtent cher quand on tombe dedans :
- Lire l’en-tête trop gentiment : si tu ignores les caractères non numériques,
1a2passe pour12. Généreux, mais non. - Le dépassement d’entier : avec
99999999999en première ligne, le nombre devient n’importe quoi. Le test doit se faire avant la multiplication, parce qu’après, c’est déjà un comportement indéfini. - Un
i++oublié dans la boucle de lecture, et un fichier0\ntourne pour l’éternité. - Un
-cdans la règle de liaison du Makefile : le binaire n’est jamais produit, et tu accuses ton code C pendant un bon moment alors que le coupable est une option du Makefile. - Un
mallocutilisé avant le test deNULL.
Il existe huit façons de le résoudre
Une fois la solution qui marche, j’ai voulu comparer. J’ai écrit huit versions du même solveur : force brute naïve, force brute améliorée (on ne revérifie que la bordure), sommes de préfixes avec dichotomie, DP classique, DP à deux lignes, DP à une ligne, histogramme avec pile monotone, et distances gauche/haut.
Sur une carte vide de 1000 × 1000, qui est le pire cas parce que le carré peut faire 1000 de côté, les écarts sont énormes (médianes, compilé en -O2) :
| Algorithme | Temps |
|---|---|
| Force brute naïve | plus de 150 s |
| Force brute améliorée | 61 s |
| Distances gauche/haut | 362 ms |
| DP classique | 4,1 ms |
| DP à une ligne | 2,4 ms |
Oui, c’est exactement la famille d’algorithmes qui m’avait coulé. La DP reste linéaire en nombre de cases, les autres se dégradent dès que k grandit. La DP à une ligne est la plus rapide : même récurrence, mais avec un seul tableau de la largeur de la carte, parce que pour calculer une case on n’a besoin que de la valeur juste au-dessus, de celle de gauche et de la diagonale. Ces mesures viennent de mon PC (un i7-11850H) : des ordres de grandeur, pas une promesse.
Ce que ça donne
Mon programme produit exactement la même sortie que les solutions de référence sur les 36 cartes d’exemple. La plus grosse, 1000 × 1000, est traitée en environ 75 ms, lecture et affichage compris. Les cas d’erreur (fichier inexistant, aucun argument) sortent bien avec le code 84 et un message sur stderr. Un nm sur le binaire confirme que seules les fonctions autorisées sont utilisées.
Ce que j’en retiens
Trois jours. C’est tout ce qu’il m’a fallu, et pas trois jours de génie : des jours normaux, entre deux autres choses.
Si je l’ai raté en première année, ce n’est pas parce que l’algo était hors de portée. Je ne le comprenais pas, et surtout je n’avais pas travaillé dessus assidûment. Quand tu t’assois vraiment dessus, un projet « impossible » devient un projet de trois jours.
Le plus vexant, c’est qu’il m’a fallu de l’ennui pour m’y remettre. Je devrais peut-être m’ennuyer plus souvent.
Si tu es dessus en ce moment : dessine la carte sur papier, remplis le tableau à la main sur un exemple de 4 × 4, et regarde ce que fait le min. Tu n’auras pas besoin de plus.