Défi C/C++ - Pavage de plan

Date de publication : 7 janvier 2009 , Date de mise à jour : 29 janvier 2009

Les "défis C/C++" sont des petits exercices à faire soi même sur un sujet précis, un peu comme lors des examens ou exercices de livres. Ces codes à écrire sont étudiés de sorte que les défis aient un côté algorithmique en plus de l'implémentation, ce qui implique pour vous une réflexion plus ou moins approfondie ainsi que l'écriture d'un algorithme textuel, son implémentation et pour terminer vous devez le tester.

Ce mois ci, les équipes C et C++ vous proposent de travailler sur un programme de pavage du plan.

1. Pavage de plan

Les règles générales des "Défis C/C++" sont décrites à cet endroit. Certaines de ces règles sont modifiées par le présent document.

Le but de ce défi est de remplir le mieux possible un plan (une surface) avec une liste de formes. Ces formes seront communiquées à l'exécution.

1.1. Données sur les formes à utiliser:

Elles peuvent comporter des trous ;

Elles ne seront pas plus larges ni plus hautes que 100 cases ;

Elles seront définies dans un fichier texte noté "formes.txt" dont voici un exemple :

***
**
*
 
****
 ***
 ***
 
*

Cet exemple comporte 3 formes, séparées chacune par une ligne vide. Chaque * représente une case de la forme, les espaces marquent les décalages.

Le fichier formes.txt devra se situer dans le même répertoire que l'exécutable.

1.2. Utilisation des formes

Chaque candidat pourra considérer les formes dans l'ordre qu'il voudra. Il pourra aussi les tourner de 90°, 180° ou 270°. Il ne pourra pas les retourner (symétries axiales). Il devra utiliser ces formes pour paver un plan d'une taille variable, fixée lors de l'exécution.

Pour une largeur donnée du plan, l'objectif est de fournir l'agencement de formes qui nécessitera le moins de lignes de remplissage. La largeur du jeu du plan n'excèdera pas 500 cases.

1.3. Paramètres d'exécution

Le programme nécessitera un paramètre pour s'exécuter : la largeur du jeu de tétris à remplir. L'exécution se fera de la manière suivante :

programme_du_defi.exe 17

=> le plan à remplir a une largeur de 17 cases.

1.4. Résultat

Le résultat de l'agencement sera également inscrit dans un fichier, noté resultat.txt, ce fichier contiendra l'agencement trouvé, où les formes seront représentées par des lettres. Pour une largeur de 6 cases, un fichier résultat pourra être de la forme suivante :

BBBAAA
BBB AA
BBBBCA

On y retrouve les 3 formes de départ où A représente la première forme, B la seconde et C la troisième. Le nommage des formes doit respecter l'ordre de départ. L'exemple contient volontairement un faible nombre de formes, les programmes proposés par les candidats devront pouvoir agencer jusqu'à 26 formes. Il n'y aura pas plus de 26 formes à agencer. Le fichier de résultat devra être créé par le programme et être situé dans la même répertoire que l'exécutable.

Le programme affichera également à l'écran le nombre de lignes nécessaires pour agencer les formes.

1.5. Cas particuliers

Si une forme ne rentre pas dans le plan, le programme l'indiquera lors de son exécution par un message à l'écran, de la forme "La forme A ne rentre pas" où A est le même nommage de la forme que pour l'affichage du résultat. Le programme continuera cependant l'agencement des autres formes.
Si plusieurs solutions existent pour un même jeu de formes, le programme n'en inscrira qu'une dans le fichier resultat.txt
Si le fichier formes.txt est introuvable ou inaccessible, le programme affichera un message puis fermera proprement.
Si le programme ne peut écrire le fichier resultat.txt, il affichera un message puis fermera proprement.
Si le paramètre d'exécution est supérieur à 500 ou est absent, le programme affichera un message et fermera proprement.

2. Déroulement du défi

2.1. Dates du défi

Date de début du défi : Mardi, le 1er juillet 2008
Date de fin du défi : Vendredi, le 1er août 2008

3. Analyse des résultats

3.1. Participants

Un seul participant : floflo_2006

3.2. Notes des participants

Voici le détail des notes retenues envers le gagnant :

Robustesse : 0,6 / 3
Commentaires / Propreté : 1 / 3
Elegance : 2,833333333 / 6
Vitesse / Consommation : 1,5 / 3
Organisation du code : 4 / 5
Note finale : 10,16666667 (arrondie à 10)

3.3. Gagnants

Le grand gagnant de ce premier défi C n'est autre que : floflo_2006. Toutes nos félicitations à ce grand gagnant des premiers défis C. Voyons maintenant sa note ainsi que les critiques envers son code.

4. Commentaires sur la solution proposée

4.1. Robustesse

4.1.1. Entrées / Sorties

Le parsage du fichier formes.txt, bien que répondant à l'énoncé est rude. En effet, le fichier de données doit forcément être terminé par deux lignes vide pour que la dernière forme soit prise en compte.

Dans le fichier de forme, les espaces en fin de ligne sont pris en compte dans la largeur de l'élément ce qui peut donner des résultats surprenant.

Il y a une fuite mémoire lors de la lecture des formes. En effet, dès qu'une ligne est lue, une allocation est faite si nécessaire par un élément de type t_forme. Par contre, si la forme n'a pas été lu "correctement" (par exemple si la dernière ligne n'est pas suivie de deux retours à la ligne) cet élément n'est pas libéré.

Au niveau de la sortie : En principe, pour quitter une application correctement et s'assurer quelque chose de portable, il faudrait utiliser EXIT_FAILURE. Quitter l'application avec exit(-1) n'est pas une bonne solution. La stratégie préconisée est de faire remonter l'erreur jusqu'à main(), sauver ce qui peut l'être, libérer ce qui doit l'être et quitter l'application proprement.

4.1.2. Code

2 variables pouvant être utilisé sans être initialisées (signalées par deux warning à la compilation) :

j dans positionnerForme() (lorsque la hauteur est nulle, ce qui ne devrait pas pouvoir se produire)
y dans utiliserForme() (avec un jolie plantage à l'exécution...)

Il aurait juste été plus plaisant d'avoir des arrêts propres du programme lors des erreurs. Un exit(-1), bien qu'amenant techniquement le même comportement suite à la destruction du processus, est plus barbare qu'une libération consciencieuse de tous les objets alloués et des fichiers ouverts.

Ne tester aucun ou quasiment aucun retour de malloc/calloc est une très mauvaise habitude. Bien que la réponse de retour est quasiment toujours positive, une vérification est nécessaire.

L'utilisation de sizeof(type) au lieu de sizeof(variable), complexifie la maintenance et l'évolutibilité et donc on prend des risques inutiles.

Aucun test sur les retours de fonctions, c'est aussi une mauvaise habitude.

4.2. Commentaires / propreté

On note un réel effort pour les commentaires. Ils sont nombreux et amènent un ratio code/commentaire remarquable. Cependant, des commentaires plus explicatifs, aidant à comprendre les grandes lignes plutôt que simplement parfois une réécriture en langage naturel des fonctions appelées aurait été plus appropriés. De la même manière, un bloc descriptif accompagnant chaque fichier aurait été du meilleur effet.

À déplorer aussi, l'allocation massive de la matrice principale s'appuyant sur la hauteur maximale possible. Cela simplifie le problème c'est vrai mais entraine une consommation excessive de mémoire. Une solution plus propre aurait été d'agrandir la matrice au fur et à mesure de son utilisation ou, pour éviter les multiples appels à l'allocateur mémoire, d'allouer la matrice par blocs de lignes de plus en plus grands.

L'utilisation du nom de l'exécutable Pavage_de_plan.exe "en dur" dans le message d'aide n'est pas une bonne idée, en effet, si on appelle son programme "pavage" ?

Utilisation de tests non explicite dans le code, par exemple :


if(forme->matrice[i][j])

Masquage de la qualité de pointeur de t_liste. Pourquoi ne pas assumer qu'il s'agisse d'un pointeur?

Des cast en double inutile à plusieurs endroits du code.

Les identificateurs commençant par _ suivi d'une majuscule sont réservés.

Utilisation systématique de int pour les tailles et les indices de tableaux. size_t aurait mieux convenu.

4.3. Élégance de la solution

L'avantage de cet algorithme est sa complexité qui est relativement avantageuse. L'algorithme semble fonctionner et répond donc à nos attentes. Dommage qu'il n'y ai pas eu d'autres concurrents pour comparer.

4.4. Vitesse / consommation mémoire

Comme dit précédemment, il y a une fuite mémoire, dommage.

Avec un fichier contenant une seule forme de 6 étoiles, le programme effectue 2604 allocations dont 2600 pour allouer largeur octets correspondant aux nombre de ligne maximale théorique de la solution. Point de vue des performances, on peut faire mieux.

4.5. Organisation du code

Organisé comme un code orienté objet, on voit tout de suite le rôle de chaque fichier. Bien joué! Nous souhaiterions voir des programmes architecturés de la sorte plus souvent.

4.6. Conclusion

En général, c'est du code très bien présenté et architecturé, et compte tenu du temps passé à coder la solution, est déjà très bien. Seul regret, ne pas avoir profité de tout le temps défini pour peaufiner et améliorer son code...

Etant donné qu'il n'y avait qu'un seul et unique participant, nous avons eu le temps de bien nous plonger dans le code et d'en ressortir toutes les qualités et défaut, en espérant que ça puisse lui servir.

Les sources du grand gagnant du défi C sont téléchargeable à partir de ce lien

Copyright © 2009 Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.