1. Recherche de solution de l’Âne Rouge▲
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 défi de ce mois consiste à créer un programme qui recherche et affiche une solution de l’Âne Rouge.
Ce document présente :
- le rappel des règles de l’Âne Rouge ;
- la description de ce que doit faire le programme pour répondre au besoin de ce défi ;
- l’organisation mise en place autour de ce défi.
Un post est ouvert sur le forum à cet endroit permettant de discuter autour de ce défi. Les éventuelles questions et remarques doivent être posées à la suite dans ce post, les réponses seront apportées de manière publique toujours dans ce post.
2. Rappel des règles de l’Âne Rouge▲
Ce paragraphe s’inspire largement de la description faite par Wikipédia.
2-1. But du jeu▲
L’Âne Rouge, aussi appelé « klotski » (du polonais « klocki » signifiant « pièces en bois ») semble être un jeu d’origine thaïlandaise. C’est un casse-tête de déplacements proche du taquin. Le joueur n’est pas autorisé à enlever un bloc, il peut uniquement faire glisser les blocs horizontalement ou verticalement.
Le jeu est composé de 4 carrés de 1 case, 5 rectangles de 2 cases et 1 carré de 4 cases (c’est l’Ane Rouge). Ces 10 pièces sont disposées sur une surface de 5 X 4 et il reste donc 2 emplacements vides qui servent à déplacer les autres pièces.
La position initiale du jeu est la suivante :
Le but du jeu est d’amener le grand carré rouge, en bas de la boîte par glissements successifs des différents éléments.
La position finale des autres pièces jaunes et des trous n’a pas d’importance, par contre, la position finale du carré rouge doit obligatoirement être comme indiqué sur le dessin.
La solution optimale pour cette configuration initiale est de 81 déplacements. Le premier à publier cette solution a été Martin Gardner, en février 1964 dans le magazine Scientific American.
2-2. Les variantes du jeu▲
Les variantes de ce jeu concernent essentiellement la position initiale des différentes pièces.
3. Spécification du programme▲
3-1. Fonctionnement du programme▲
Le programme doit utiliser les règles spécifiées dans le paragraphe précédent.
Le programme doit rechercher et afficher la liste des coups à jouer pour obtenir la solution (ou une des solutions s’il y en a plusieurs) ainsi qu’éventuellement un système de coordonnées permettant de reproduire les coups à jouer.
S’il n’y a pas de solution, le programme doit le détecter et l’afficher.
Le programme doit afficher, lorsqu’il a terminé, le temps mis pour trouver la solution ainsi que le nombre de déplacements effectués.
Le nombre de déplacements à afficher est le nombre de déplacements pour aller le plus directement possible de la position initiale à la position finale. Il ne comprend pas les éventuels errements dus à la recherche de la solution. De plus, même si une pièce se déplace de 2 cases en un seul mouvement, il faudra tout de même compter 2 déplacements.
3-2. Paramètres du programme▲
Le programme doit accepter les paramètres suivants :
- « -h ». Cette option affiche l’aide en ligne du programme. À l’issue, le programme doit s’arrêter ;
- « -v ». Cette option affiche le copyright du programme. À l’issue, le programme doit s’arrêter ;
- « -f <fichier> ». Cette option permet d’indiquer au programme le nom du fichier décrivant la position initiale des pièces.
3-3. Format du fichier de description de la position initiale des pièces▲
La position initiale des pièces n’est pas connue par le programme, elle figure dans un fichier annexe. Le format du fichier décrivant cette position initiale est le suivant :
- c’est un fichier texte contenant 5 lignes de 4 caractères ;
-
chacune des 12 pièces est identifiée par une lettre :
- A : 1 carré libre de 1 case,
- B : 1 carré libre de 1 case,
- C : 1 carré de 1 case,
- D : 1 carré de 1 case,
- E : 1 carré de 1 case,
- F : 1 carré de 1 case,
- G : 1 rectangle de 2 cases,
- H : 1 rectangle de 2 cases,
- I : 1 rectangle de 2 cases,
- J : 1 rectangle de 2 cases,
- K : 1 rectangle de 2 cases,
- L : 1 carré de 4 cases (l’Âne Rouge) ;
-
si le contenu du fichier est invalide, il doit être ignoré et un message d’erreur doit être affiché :
- Mauvais nombre de lignes,
- Mauvais nombre de caractères sur une ligne,
- Mauvaise lettre d’identification,
- Configuration initiale impossible,
- …
L’exemple suivant montre le contenu d’un fichier permettant de spécifier la position initiale des pièces :
GLLH
GLLH
IJJK
ICDK
EABF3-4. D’autres positions initiales▲
À titre d’exemple et afin que vous puissiez valider vos projets, voici d’autres positions initiales possibles :
|
GLLH |
GLLH |
GLLH |
|
GLLH |
CLLD |
GLLH |
|
GLLH |
GGHH |
3-5. Contraintes supplémentaires▲
Les contraintes suivantes doivent être respectées :
- le programme doit être écrit en C ou en C++ ;
- le programme doit être écrit pour les environnements Microsoft ou Linux ;
- l’environnement de développement utilisé pour écrire le programme est libre ;
- le programme doit fonctionner en mode « console » uniquement ;
- l’usage des librairies externes s’il n’est pas interdit doit être très limité. Le challenger ne doit pas perdre de vue que le programme doit pouvoir s’exécuter dans un environnement qui n’est pas forcément un environnement de développement. Les seules librairies qui ne posent pas de problèmes du fait de leur universalité sont boost et la STL pour le langage C++ et glib pour le langage C ;
- le programme doit être livré avec une documentation décrivant le fonctionnement interne du programme, les algorithmes utilisés, les techniques de développement utilisées et toutes les autres choses qui pourraient être intéressantes ;
- le programme doit être livré avec une description sur la manière de recompiler entièrement le programme.
4. Déroulement du défi▲
4-1. Durée du défi▲
La durée de ce défi est de 5 semaines à compter de son ouverture publique. Cette durée pourra éventuellement être modifiée si des conditions particulières l’exigent.
La date de début du défi est fixée au dimanche 22 mars 2009 et la date de fin de soumissions des projets est fixée au dimanche 26 avril 2009 à minuit (c’est la date et heure de dépôt du fichier qui fera foi).
4-2. Critères d’évaluation des programmes▲
Chacun des projets proposés est noté sur 20 et les critères de notation retenus pour ce défi sont les suivants :
-
Fonctionnement du programme (sur 8 points)
- Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces (sur 1 point).
- Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés (sur 3 points).
- Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté (sur 3 points).
- Comportement face à une solution impossible (sur 1 point).
-
Documentation (sur 3 points)
- Complétude par rapport à ce qui est demandé (sur 1 point).
- Innovation dans les idées implémentées dans le code (sur 2 points).
-
Analyse du code (sur 7 points)
- Organisation des fichiers (sur 1 point).
- Découpage en modules/classes (sur 1 point).
- Lisibilité du code (sur 3 points).
- Simplicité du code (sur 2 points).
- Bonus C vs C++ (sur 2 points). Cet extra bonus est fait pour redonner un petit avantage aux programmes écrits en C compte tenu du travail et de l’effort supplémentaire nécessaire pour écrire en C.
-
Recompilation (sur 2 points)
- Complétude de la procédure et recompilation du programme (sur 1 point).
- Non-utilisation de librairies externes (sur 1 point). L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera.
4-3. Composition du jury▲
Le jury est composé des personnes suivantes :
- ram-0000 (organisateur de ce défi),
- Sylvain Togni (vainqueur du défi précédent),
- gangsoleil
5. Complément d’analyse du défi▲
Une analyse plus approfondie de ce défi montre que l’Âne Rouge est un jeu très riche puisque le nombre total de grilles différentes est de 363 480 grilles.
- Sur ces 363 480 grilles, il y en a 24 780 qui sont gagnantes sans aucun mouvement.
- Sur ces 363 480 grilles, il y en a 96 365 qui n’ont pas de solution.
- Sur les 267 115 grilles restantes, le plus long chemin optimal est de 179 mouvements.
Avec ces 363 480 grilles, il y a un total de 1 112 092 mouvements différents possibles, ce qui donne une moyenne de 3,05 mouvements par grille. La répartition du nombre de mouvements possibles pour toutes les grilles est la suivante :
- 0 grille ont 0 mouvement possible
- 8 760 grilles ont 1 mouvement possible
- 94 238 grilles ont 2 mouvements possibles
- 145 098 grilles ont 3 mouvements possibles
- 89 796 grilles ont 4 mouvements possibles
- 23 194 grilles ont 5 mouvements possibles
- 2 350 grilles ont 6 mouvements possibles
- 44 grilles ont 7 mouvements possibles
Une des solutions optimales possibles à partir de la grille présentée dans le paragraphe 2.1 est la suivante :
2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442
2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442 2442
2332 2332 233. 2.33 2133 2133 .133 1.33 133. 1332 1332 1332 1332 .332 33.2
2112 2112 2112 2112 2.12 2.12 2.12 2.12 2.12 2.12 2.12 2.12 .212 1212 1212
1..1 1.1. 1.12 1.12 1.12 .112 2112 2112 2112 211. 21.1 2.11 .211 .211 .211
2442 2442 2442 2442 2442 2442 .442 .442 .442 44.2 442. 442. 442. 4421 4421
2442 2442 2442 2442 2442 2442 2442 2442 .442 44.2 442. 4421 4421 442. 4422
3312 3312 3312 331. 33.1 .331 2331 2331 2331 2331 2331 233. 2332 2332 2332
12.2 1212 1212 1212 1212 1212 1212 .212 2212 2212 2212 2212 2212 2212 221.
.211 .2.1 .21. .212 .212 .212 .212 1212 1212 1212 1212 1212 121. 121. 121.
4421 4421 4421 4421 4421 4421 4421 4421 4421 4421 4421 44.1 441. 4412 4412
4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422
2332 2332 2332 2332 .332 33.2 3322 3322 3322 3322 33.2 3322 3322 332. 3321
22.1 22.1 2.21 2.21 2.21 2.21 2.21 2.21 2121 2121 2121 2121 2121 2121 212.
121. 12.1 1.21 .121 2121 2121 21.1 211. 2.1. 21.. 212. 212. 212. 212. 212.
4412 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412
4422 44.2 44.2 44.2 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412 4412
3321 3321 33.1 331. 33.. .33. 233. 233. 2.33 2.33 .233 .233 .233 ..33 .33.
21.2 2122 2122 2122 2122 2122 2122 2122 2122 2.22 .222 1222 1222 1222 1222
21.2 21.2 2122 2122 2122 2122 .122 1.22 1.22 1122 1122 .122 1.22 1222 1222
4412 4412 441. 44.1 4411 4411 4411 4411 4411 4411 ..11 .1.1 .11. .112 .112
4412 4412 4412 4412 44.2 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422
33.. 332. 3322 3322 3322 3322 3322 3322 3322 ..22 4422 4422 4422 442. 4422
1222 1222 1222 1222 1222 12.2 1.22 .122 ..22 3322 3322 3322 3322 3322 3322
1222 12.2 12.2 12.2 12.2 12.2 1.22 1.22 1122 1122 1122 1122 1122 1122 112.
1.12 11.2 1122 1122 1122 1122 1122 1122 1122 1122 .122 1.22 12.2 12.2 1222
4422 4422 4422 4422 4422 4422 4422 4422 4422 ..22 1.22 1.22 12.2 1222 1222
4422 4422 44.2 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 4422 44.2
3322 3322 3322 3322 3322 3322 3322 3322 ..22 4422 4422 4422 4422 44.2 44.2
112. 112. 112. 11.. 1.1. .11. .1.1 ..11 3311 3311 3311 3311 3311 3311 3311
1222 1222 .222 .222 .222 2.22 22.2 222. 222. 2222 2222 2222 2222 2222 2222
1222 .222 1222 1222 .222 2.22 22.2 222. 2222 2222 2222 2222 2222 2222 2222
.442 1442 1442 .442 1442 1442 1442 1442 1442 144. 1.44 .144 1144 1144 1144
.442 .442 .442 1442 1442 1442 1442 1442 144. 144. 1.44 1.44 ..44 3344 3344
3311 3311 3311 3311 3311 3311 3311 3311 3311 3311 3311 3311 3311 ..11 .1.1
2222 2222 2222 2222 2222 2222 2222 2222 2222 2222 2222 2222
2222 2222 2222 2222 2222 2222 2222 2222 2222 2222 2222 2222
1144 1144 1144 11.. 1.1. .11. .1.1 ..11 3311 3311 3311 3311
3344 3344 3344 3344 3344 3344 3344 3344 ..44 .144 1.44 144.
.11. 1.1. 11.. 1144 1144 1144 1144 1144 1144 1.44 1.44 144.6. Analyse des résultats▲
6-1. Fichiers de référence▲
Les 5 fichiers de références utilisés pour valider les résultats des différents projets sont les suivants :
|
Invalide 1 |
Invalide 2 |
Invalide 3 |
Impossible |
Réalisable |
|---|---|---|---|---|
|
GJLH |
GJLH |
gllh |
GGJC |
GLLH |
|
Ce fichier peut être téléchargé ici. Cette grille est invalide, car la deuxième ligne ne contient pas le bon nombre de caractères |
Ce fichier peut être téléchargé ici. Cette grille est invalide, car le gros carré est morcelé ainsi qu’un des rectangles horizontaux |
Ce fichier peut être téléchargé ici. Cette grille est invalide, car elle possède des caractères interdits |
Ce fichier peut être téléchargé ici. Cette grille est valide, mais n’a pas de solution |
Ce fichier peut être téléchargé ici. La solution optimale est de 85 coups |
6-2. Participants▲
Les personnes ayant participé jusqu’au bout à ce défi sont par ordre alphabétique :
Nous les remercions pour de leur participation à ce défi ainsi que tous les autres participants qui ne sont pas allées jusqu’au bout de la démarche, mais qui ont tenté de participer.
6-3. Commentaires sur les solutions proposées▲
Pour chacune des solutions proposées sont présentées la vision et l’analyse faite par le challenger ainsi que la notation du projet faite par le jury C & C++ de ce défi. Un récapitulatif de la notation des différents projets est présenté dans le paragraphe 6.4
6-3-1. acetyle (corrigé par ram-0000)▲
La solution proposée par acetyle peut être téléchargée ici (format zip).
Il s’agit d’un projet écrit en C, développé à l’aide de Visual Studio 2005 pour un environnement Windows XP.
6-3-1-1. Analyse par le challenger▲
C’est un problème à information complète ressemblant au taquin. Aucune difficulté mathématique n’est apparente. L’ensemble des combinaisons est fini. Le problème combinatoire est à complexité raisonnable (même avec une majoration grossière) qui pourrait être entièrement décrypté (i.e. stockage de toutes les solutions pour n’importe quelle configuration initiale).
Le principal problème à contourner est d’éviter les boucles et de détecter un état bloquant.
Le but de ce projet sera de réaliser un algorithme efficace, compréhensible et si possible léger en mémoire.
Une recherche en largeur d’abord paraît plus adaptée à ce genre de problème, car l’on peut s’arrêter à la première solution trouvée qui sera optimale par construction. Une recherche en profondeur pourrait être justement trop profonde.
Ce type de problème est typiquement adapté à une représentation bit à bit. Le casse-tête étant un espace réduit.
Beaucoup d’optimisations et /ou astuces peuvent être mises en place pour accélérer la recherche. L’utilisation d’un historique évite de boucler et de recalculer un chemin déjà étudié.
Il y a douze pièces à différencier, 2 vides, 1 carré, 5 doubles et 4 simples. Pour identifier ces pièces, 4 bits suffisent (12 < 15). Une ligne contient quatre pièces ou éléments d’une pièce (4 * 4 bits), donc un short de 16 bits peut représenter une ligne.
Le plateau de jeu est représenté ligne par ligne, 5 short (5*16 bits) sont nécessaires, les identifiants des pièces sont faits par leur lettre soustrait par 'A' donc de 0 à 11 d’après les spécifications.
identification('L’) = 'L’ - 'A' donne une valeur de 11, cette transformation est bien sûr bijective.La clé d’identification d’un plateau en découle: 4 des 5 short int représentant une ligne sont regroupés en un long long de (4*16 =>64 bits) et le dernier short est laissé en tant que clé secondaire. La clé n’utilise pas les identifiants des pièces, mais leurs types (SIMPLE, QUAD, DOUBLE …), en effet deux configurations sont équivalentes en comparant seulement la place de chaque type de pièces et non leur identifiant lettré.
GLLH 2442
GLLH 2442
IJJK devient 2332 la clé primaire est 2442244223342552
ICDK 2552 et la clé secondaire est 5005
EABF 5005
GLLH HLLG
GLLH HLLG
IJJK est équivalent en termes de position à IJJK
ICDK ICDK
EABF EABFLa Fifo contient l’adresse de début et la fin de la liste chainée, ce qui permet de faire des push à la fin et enlever la tête assez facilement.
J’ai utilisé une liste chainée triée par ordre croissant des clés génériques décrites au-dessus (la clé primaire en premier puis la secondaire). La même structure basique de liste chainée est utilisée pour la Fifo, les deux listes partagent l’adresse de l’élément stocké (facilité de mise à jour et optimisation mémoire).
INITIALISATION : push du plateau initial dans FIFO
Debut loop tant que Fifo non vide et pas de solution trouvée
La première configuration de la Fifo est enlevée et étudiée
DEBUT on crée une configuration pour chaque nouvelle configuration possible à partir de cette configuration initiale
Si la configuration est gagnante, on arrête
Sinon on pushe la configuration dans l’historique,
si elle est effectivement ajoutée, on l’ajoute aussi à la fin de la Fifo
sinon on ne fait rien
END
END loopChoix discutables : Le choix d’une liste triée pour l’historique n’est pas optimal, mais offre des performances acceptables. Une hashtable pourrait améliorer drastiquement les performances. L’utilisation de variables globales (ex. : informations sur les pièces et la Fifo), n’est pas des plus élégantes, mais elles évitent de trimbaler l’information dans toutes les fonctions.
Optimisations locales : On évite d’effectuer l’action inverse qui a permis de construire l’état actuel. On cherche les déplacements de pièces seulement autour des vides. Durant la recherche sur le deuxième emplacement vide, il est superflu d’étudier le déplacement de la pièce carré, des doubles verticaux vers la gauche et la droite ainsi que les doubles horizontaux vers le haut et le bas. En effet, tous ces différents déplacements ont été obligatoirement étudiés lors de l’étude autour du premier vide.
Optimisations globales : Le principal goulot d’étranglement de ce programme est la recherche coûteuse dans l’historique, j’ai rendu le temps de recherche acceptable (< 1 sec sur ma machine) en découpant l’historique en plusieurs sous-listes identifiées par la localisation du carré.
On pourrait continuer la découpe par rapport aux clés de primaire et secondaire aidée par une hashcode, mais j’ai considéré que le but du concours n’était pas l’extrême rapidité de recherche. L’utilisation d’une heuristique efficace (distance du carré à la sortie ? regroupement des blancs ?) aurait également pu être de la partie, mais la complexité du problème ne la justifie à mon avis pas.
6-3-1-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
6/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Le programme se crashe s’il est lancé sans paramètre. Il manque un petit test dans la fonction scanArgs() pour tester ce cas de figure |
0,5/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
La solution optimale (85 coups) est trouvée en 1 seconde |
3/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
Des problèmes dans l’affichage des accents (trouvEe par exemple). Suivi de la solution un peu difficile à suivre (1 étape par 9 lignes), il aurait peut-être été préférable de mettre plusieurs étapes en largeur. |
1,5/3 |
|
|
Comportement face à une solution impossible |
L’absence de solution est notifiée immédiatement |
1/1 |
|
|
Documentation |
2/3 |
||
|
Complétude par rapport à ce qui est demandé |
Tout y est, procédure de compilation, documentation, programme qui fonctionne du premier coup |
1/1 |
|
|
Innovation dans les idées implémentées dans le code |
Un petit travail supplémentaire peut être fait pour simplifier le hash de chaque grille. Actuellement, ce hash est sur 64 bits + 16 bits. Cette taille tient compte du fait qu’il y 12 pièces à différencier (donc 4 bits nécessaires * 20 cases = 80 bits ce qui fait bien 64 bits + 16 bits). Maintenant, si on tient compte du fait qu’en fait il n’y a que 5 pièces à différencier (espace, 1 case, 2 cases verticales, 2 cases horizontales, 4 cases), cela fait 3 bits * 20 cases = 60 bits donc cela rentre dans un nombre de 64 bits |
1/2 |
|
|
Analyse du code |
4/7 |
||
|
Organisation des fichiers |
Pas compris l’intérêt d’avoir un fichier structure.fwd.h et language.fwd.h. Pourquoi pas structure.h et language.h |
0,5/1 |
|
|
Découpage en modules/classes |
Les différentes fonctionnalités sont regroupées par fichiers |
1/1 |
|
|
Lisibilité du code |
Code aéré et facile à lire. Manque parfois de commentaires pour expliquer certains détails importants dans les algorithmes (les fonctions dans le module list.c par exemple) |
1,5/3 |
|
|
Simplicité du code |
Code simple à lire, on note toutefois la non-utilisation du mot clé const pour protéger certains paramètres par exemple |
1/2 |
|
|
Recompilation |
2/2 |
||
|
Complétude de la procédure et recompilation du programme |
Aucun problème de recompilation |
1/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Aucune librairie externe n’est utilisée |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
+2 |
||
|
Total |
16/20 |
6-3-2. Chatanga (corrigé par Sylvain Togni)▲
La solution proposée par Chatanga peut être téléchargée ici (format zip) ou ici (format tgz).
Il s’agit d’un projet écrit en C++, développé à l’aide de Xcode 3.0 pour un environnement Mac OS X.
6-3-2-1. Analyse par le challenger▲
L’environnement sous lequel le programme a été développé et testé est :
Mac OS X 1.5.6
2.4 GHz Intel Core 2 Duo
2 Go 667 MHz DDR2 SDRAM
Le développement s’est fait sous Xcode 3.0 (ça compile aussi sous Visual C++
2005 sans configuration particulière), mais un classique Makefile est fourni
pour pouvoir compiler le projet sans EDI. Les options de génération utilisées
par ce Makefile sont :
CPPFLAGS = -O2 -fno-strength-reduce -W -Wall -pedantic -ansi
Avec ces options de génération et sous l’environnement indiqué, la recherche
d’une solution prend moins d’une seconde.
Enfin le temps de développement doit s’élever à quelque chose comme une
quarantaine d’heures dont plus de la moitié dépensée dans la vaine* recherche
d’une heuristique valable, la version actuelle étant essentiellement une
réécriture de recherche basique qui explore mécaniquement l’espace des
coups à jouer.
* Enfin pas totalement vaines, juste pas vraiment utiles. ;)
Le dossier data contient une dizaine de plateaux donnant les résultats
suivants. Ces plateaux reprennent ceux fournis dans l’énoncé du problème
exception faite du numéro 0 mentionné sur le forum comme n’ayant pas de
solution.
Numéro Longueur Temps de
de meilleur recherche
plateau solution (+/- 5 ms)
----------------------------------------------
0 aucune 0 ms
1 116 110 ms
2 99 110 ms
3 90 110 ms
4 116 110 ms
5 100 110 ms
6 45 110 ms
7 85 115 ms
8 110 110 ms
9 49 370 ms6-3-2-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
7/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Parfait, gestion correcte et affichage détaillé des erreurs de lectures |
1/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
Excellent, solution optimale trouvée en un temps très court (environ 100 ms) |
3/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
Bon, mais un affichage des positions plutôt que des coups aurait peut-être été plus lisible |
2/3 |
|
|
Comportement face à une solution impossible |
Parfait, le programme affiche immédiatement « Aucune solution trouvée » |
1/1 |
|
|
Documentation |
2/3 |
||
|
Complétude par rapport à ce qui est demandé |
Complet, mais assez minimaliste : un README et des commentaires dans le code |
0,5/1 |
|
|
Innovation dans les idées implémentées dans le code |
Excellent choix algorithmique : parcours en largeur et gestion correcte des transpositions |
1,5/2 |
|
|
Analyse du code |
5/7 |
||
|
Organisation des fichiers |
Le découpage en 9 fichiers semble représenter un bon compromis vis-à-vis de l’architecture choisie |
1/1 |
|
|
Découpage en modules/classes |
Le nom des classes semble bien choisi et on comprend assez aisément leur rôle |
1/1 |
|
|
Lisibilité du code |
Lisibilité correcte, commentaires utiles là ou il faut |
2/3 |
|
|
Simplicité du code |
Moyen, pas mal de classes et beaucoup de lignes de code |
1/2 |
|
|
Recompilation |
2/2 |
||
|
Complétude de la procédure et recompilation du programme |
Compilation sous cygwin sans erreurs ni warnings |
1/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Parfait, aucune librairie non standard utilisée |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
0 |
||
|
Total |
16/20 |
6-3-3. Climoo (corrigé par gangsoleil)▲
La solution proposée par Climoo peut être téléchargée ici (format zip).
Il s’agit d’un projet écrit en C, développé à l’aide de Emacs et make pour un environnement Linux (Ubuntu 8.10).
6-3-3-1. Analyse par le challenger▲
Il s’agit d’un problème de recherche d’une solution, à travers plusieurs états. Ici un état est appelé 'Situation Klotski' ou plus simplement 'Situation'. Cela correspond a un état du plateau de jeu a un moment donne. On progresse d’un état vers d’autres états en cherchant les déplacements possibles à partir d’un état de départ. Si on atteint un état gagnant (dans le cas présent, la figure de l’Âne rouge est en bas du plateau), alors on a trouvé une solution, et celle-ci doit pouvoir être affichée. Si on visite tous les états accessibles, sans pouvoir en trouver un gagnant, alors il n’y a pas de solutions.
On utilise ici un arbre pour décrire l’avancement de la recherche d’une solution. La racine de l’arbre correspond à la situation initiale du jeu. Les situations filles de la racine correspondent aux premiers déplacements accessibles. On va créer l’arbre au fur et à mesure selon un parcours en largeur d’abord.
Justification du parcours en largeur d’abord : Parcourir en largeur d’abord permet de trouver la solution la plus courte possible dans un temps minimal. En effet, on va d’abord chercher la solution parmi les états les plus proches du nœud racine, donc ceux qui sont atteints avec un nombre minimum de déplacements.
Détection des situations similaires : À partir d’un état, il est possible, par un déplacement oppose, de revenir a l’état précédent (l’état parent). Il faut empêcher cela, car sinon l’arbre possède alors des branches infinies, et donc la résolution pourrait ne pas terminer dans le cas ou il n’y a pas de solutions. Empêcher cela est l’objet du module 'kl_tabSituations'. Au cours du parcours de l’arbre, on doit pouvoir déterminer rapidement si une situation a déjà été trouvée ou non.
Un moyen de remédier à ce problème est d’utiliser une table de hachage. Chaque situation est identifiée par une clé. Deux situations identiques (ou identiques si on peut les unifier par le biais d’un renommage des pièces) ont la même clé. Ainsi, à partir d’une situation donnée, on calcul sa clé, puis on la compare aux autres situations Klotski ayant la même valeur de cette clé. Dans la pratique, le nombre de clés possibles doit être suffisamment élèvé pour éviter qu’un trop grand nombre de situations n’aient la même clé.
Deux situations Klotski identiques ou symétriques doivent avoir la même clé. En effet, il n’est pas utile d’étudier une situation symétrique. Car s’il existe une solution à partir d’une de ces situations, alors il en existe aussi une dans sa situation symétrique, et vice-versa.
Comparaison de deux situations Klotski : Pour vérifier rapidement que deux situations Klotski sont équivalentes (identiques ou symétriques), on choisit de faire correspondre à chaque point du plateau, un nouveau symbole. Ce symbole est différent selon le type de pièce de la case. Par exemple, a tous les rectangles horizontaux de taille 2, on fait correspondre le caractère 'h'. Ainsi si deux situations sont identiques, alors les symboles équivalents de chacune de leurs cases sont égaux. De même, si deux situations sont symétriques, les symboles équivalents de chacune de leurs cases sont égaux a celui place symétriquement.
Exemple : Soient les situations suivantes :
KKDJ et KKCJ et JCKK
HHCJ HHDJ JDHH
K et H sont deux pièces horizontales de taille 2 => symbole équivalent: 'h'
C et D sont deux petits carrés de taille 1 => symbole équivalent: 'p'
J est une pièce verticale de taille 2 => symbole équivalent: 'v'
En appliquant à chaque case de ces situations la fonction permettant de faire correspondre le symbole équivalent, on obtient :
hhpv et hhpv et vphh
hhpv hhpv vphhOn peut constater que les deux premiers résultats obtenus sont identiques et que le 3e est symétrique aux deux autres. Donc au cours de la recherche dans l’arbre, si on rencontre ces trois situations, on en mémorisera qu’une seule ; il est inutile de garder en mémoire les deux autres. De plus, la table de conversion est toujours la même, quel que soit le moment de la résolution. Il suffit de la calculer une fois pour toutes au début de la résolution.
Clé de hachage : Sur le plateau de choisir un nombre N de points (aucun point ne doit être le symétrique d’un autre). On obtient des points X0, X2…, X(N-1). À chaque point, on va faire correspondre son symbole équivalent, qui sera compris entre 0 et le nombre total de symboles équivalents possibles NB, -1. Dans le cas, présent, NB vaut 5. On obtient un vecteur de taille N, V=[eq(X0), eq(X1)…, eq(X(N-1))]. Ce vecteur est en fait la clé de hachage. Cependant, comme la table de hachage est un tableau à une dimension, on va linéariser ce vecteur. On obtiendra alors un entier qui correspondra à l’indice dans la table de hachage.
La fonction de hachage est la suivante : clé = somme(pour i de 0 a (N-1)) (équivalent(Xi)) * (NB^i)
Cependant, comme on veut assurer que deux situations Klotski symétriques aient bien la même clé, on prend par exemple le minimum entre le symbole équivalent d’un point et celui de son symétrique. La fonction de hachage devient donc : clé = somme(pour i de 0 a (N-1)) min(équivalent(Xi),équivalent(symétrique(Xi))) * (NB^i)
Par suite, si on se fixe une taille M de la table de hachage, pour avoir une valeur entre 0 et M-1, il ne reste plus qu’a prendre le modulo de la clé. Finalement, on obtient : clé = (somme(pour i de 0 a (N-1)) min(équivalent(Xi),équivalent(symétrique(Xi))) * (NB^i)) % M
On a bien ici que :
- deux situations similaires ou identiques ont la même clé ;
- deux situations symétriques ont la même clé.
Il est très important que ces deux propriétés soient vérifiées, car sinon, on ne peut pas vérifier rapidement dans la table de hachage qu’une situation symétrique ou similaire à celle que l’on souhaite insérer, se trouve déjà parmi les situations connues.
Critique du projet : L’implémentation a été faite pour un format très spécifique et très contraint d’instance Klotski. Pour faire fonctionner le programme avec des pièces de tailles plus grandes, de formes pas nécessairement rectangulaires, une position gagnante différente, il faudrait modifier bon nombre de choses, en particulier dans le module gérant les déplacements. En effet, les déplacements sont calculés en partant du principe que les formes que l’on déplace sont rectangulaires et ont au plus une largeur de 2.
Le programme a été testé avec l’exemple type d’une instance Klotski :
GLLH
GLLH
IJJK
ICDK
EABFIl a été montre que la solution la plus courte de ce problème comportait 116 coups. Or mon programme trouve 120 coups, pour la plus courte des solutions (la première trouvée lors d’un parcours en largeur). La solution proposée semble correcte, néanmoins, j’ignore pourquoi mon programme ne trouve pas la solution composée de 116 coups.
6-3-3-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
5/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Rien à dire avec en prime l’affichage de tout ce qui ne va pas ce qui est fort utile si on est en train de construire un fichier de grille et que l’on veut la corriger |
1/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
Trouve une solution rapidement, mais ce n’est pas la solution optimale |
1/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
Affichage sommaire et efficace. Cette partie du programme aurait mérité d’être travaillée plus en détail. |
2/3 |
|
|
Comportement face à une solution impossible |
Rien à dire |
1/1 |
|
|
Documentation |
2/3 |
||
|
Complétude par rapport à ce qui est demandé |
Documentation très complète, notamment sur l’algorithme qui est bien détaillé |
1/1 |
|
|
Innovation dans les idées implémentées dans le code |
Les idées implémentées restent globalement simples (arbre, parcours en largeur, table de hash), mais sont très bien exploitées. Une grande partie de l’algorithme a été étudiée autour des positions symétriques et/ou équivalentes, avec a priori un bon choix qui permet d’obtenir des résultats rapides et efficaces |
1/2 |
|
|
Analyse du code |
5/7 |
||
|
Organisation des fichiers |
Organisation modulaire des fichiers, qui sont succinctement décrits dans la documentation |
1/1 |
|
|
Découpage en modules/classes |
Rien à dire |
1/1 |
|
|
Lisibilité du code |
Le code est clair et commenté. Le développeur est sûrement un peu fâché avec les retours à la ligne, mais rien de dramatique : le code fait partie de ceux que l’on lit avec plaisir. Toutefois, on notera la présence de exit() au milieu du code qui n’est pas du meilleur effet |
2/3 |
|
|
Simplicité du code |
Le code est simple, clair et efficace. Les améliorations suivantes sont possibles : Les fichiers d’en-tête ne sont pas protégés contre l’inclusion multiple, en cas de problème sur l’allocation mémoire, le programme quitte violemment, profiter du fait que la touche « entrée » soit plus grosse que les autres pour appuyer plus souvent dessus |
1/2 |
|
|
Recompilation |
2/2 |
||
|
Complétude de la procédure et recompilation du programme |
3 warnings (2 X kl_lecturefichier.c(118) : warning C4244: '=' : conversion de 'int' en 'KL_Piece', perte possible de données et 1 X « kl_resolution.c(86) : warning C4244: 'return' : conversion de 'int' en 'char', perte possible de données ») qui n’empêchent pas le programme de bien fonctionner |
1/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Aucune librairie externe n’est utilisée |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
+2 |
||
|
Total |
16/20 |
6-3-4. coyotte507 (corrigé par ram-0000)▲
La solution proposée par coyotte507 peut être téléchargée ici (format zip).
Il s’agit d’un projet écrit en C++, développé à l’aide de CodeBlock pour un environnement non spécifié.
6-3-4-1. Analyse par le challenger▲
L’algorithme stocke toutes les positions parcourues dans une table de hachage.
Si la position est moins bien que la même position déjà stockée, on arrête d’explorer à partir de cette position.
Pour toujours travailler avec des positions à peu près optimales, on augmente un peu la profondeur maximale (de 6 à chaque fois) que l’algorithme parcoure, quand il a fini d’explorer la profondeur précédente (on reprend à chaque fois les calculs à partir des dernières positions étudiées).
En gros, c’est un brute force qui s’arrête jusqu’à un certain niveau chaque fois et n’explore pas les positions où il est déjà passé et a fait mieux.
Le fait de niveler profondeur permet de trouver rapidement le meilleur chemin vers une position (si on ne le faisait pas, l’algorithme mettrait plusieurs minutes au moins pour trouver la solution optimale et le chemin vers certaines positions vaudrait 6000+coups et s’améliorerait petit à petit, en prenant un temps très long)
Remarque : en changeant les paramètres du hashage (alv_size et nb_hash), l’algorithme peut parcourir dans un autre sens et trouver une autre solution, c’est dû au fait que HashTable.dupl() renvoie les mêmes positions, mais dans un ordre différent selon les paramètres de hashage !!
6-3-4-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
5,5/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Un fichier avec des lettres interdites (abc) n’est pas rejeté comme demandé dans le défi. De même un fichier avec un mauvais nombre de lignes n’est pas rejeté non plus comme demandé dans le défi |
0/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
La solution optimale (85 coups) est trouvée en moins de 1 seconde |
3/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
Affichage de la solution au coup par coup. Cela peut être agréable (animation), mais c’est bloquant (attente sur le clavier) |
1,5/3 |
|
|
Comportement face à une solution impossible |
Détection immédiate de l’absence de solution |
1/1 |
|
|
Documentation |
1,5/3 |
||
|
Complétude par rapport à ce qui est demandé |
Le programme fait le principal (la recherche de solution), mais certains détails indiqués dans le défi ne sont pas implémentés |
0,5/1 |
|
|
Innovation dans les idées implémentées dans le code |
Il y a vraiment peu de choses qui sont décrites dans la documentation, c’est « service minimum » |
1/2 |
|
|
Analyse du code |
3/7 |
||
|
Organisation des fichiers |
Certaines classes sont définies et déclarées uniquement dans le .h, leur complexité aurait probablement justifié que la définition soit mise dans le .cpp associé |
0/1 |
|
|
Découpage en modules/classes |
Le découpage en classe semble logique |
1/1 |
|
|
Lisibilité du code |
Un code peu aéré et dont la mise en présentation est parfois déroutante, non-utilisation systématique du mot clé const servant à protéger les paramètres, beaucoup de pointeurs sur char en paramètres |
1/3 |
|
|
Simplicité du code |
Très peu de commentaires dans le code, quelques valeurs magiques dont on ne sait d’où elles sortent « Manager man(100003) » |
1/2 |
|
|
Recompilation |
1/2 |
||
|
Complétude de la procédure et recompilation du programme |
19 warnings (16 X « manager.cpp(106) : warning C4267: 'argument' : conversion de 'size_t' en 'Uint8', perte possible de données » et 3 X « manager.hpp(177) : warning C4706: assignation au sein d’une expression conditionnelle ») lors de la recompilation sous Visual Studio. Toutefois, ces warnings ne semblent pas empêcher le programme de fonctionner |
0/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Pas d’utilisation de librairie externe |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
0 |
||
|
Total |
11/20 |
6-3-5. jfouche (corrigé par Sylvain Togni)▲
La solution proposée par jfouche peut être téléchargée ici (format zip) ou ici (format rar).
Il s’agit d’un projet écrit en C++, développé à l’aide de CodeLite pour un environnement Linux.
6-3-5-1. Analyse par le challenger▲
L’algorithme utilisé est la force brute. On effectue l’ensemble des mouvements possible, en stockant chaque mouvement dans une map. La recherche des mouvements possibles s’effectue en recherchant les pièces qui peuvent bouger autour d’un trou (pièce A ou B). Les positions après mouvement sont stockées dans une file qui permet d’être dépilée au fur et à mesure de l’avancement du programme. Ceci évite une récursivité pouvant devenir gourmande en ressources.
Pour ne pas se trouver dans des positions presque identiques (c’est-à-dire que seule la valeur de la pièce change, non sa forme), il est généré une clé unique par position physique. Pour des raisons de performance, la clef est une chaine de caractères de 10 octets, générée à partir d’un code unique pour une forme donnée (et non par le caractère représentant une pièce). Ayant 5 formes différentes (trou, petit carré, rectangle horizontal, rectangle vertical et âne rouge), 4 bits sont nécessaires pour coder une case, donc 1 octet permet de coder 2 cases. Ayant 20 cases dans le jeu, on obtient une clé de 10 octets. Pour exemple, les 2 positions suivantes possèdent la même clé, car il y a inversion de la pièce G et de la pièce H, qui ont la même forme :
GLLH HLLG
GLLH HLLG
IJJK IJJK
ICDK ICDK
EABF EABFAfin de connaitre le chemin le plus rapide, à chaque fois que l’on retombe sur une position déjà atteinte, on regarde le nombre de coups utilisé pour arriver à cette position. Si le nombre de coups est inférieur à celui précédemment utilisé, on écrase la valeur précédente, et on signal que la position précédente est plus optimale pour parvenir à la position courante.
Pour terminer, il suffit donc de récupérer la solution dont le chemin et le plus court, et de parcourir à l’envers, depuis la position de la solution, jusqu’à la position initiale, en utilisant la position précédente stockée dans le mouvement.
6-3-5-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
4,5/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Gestion correcte, mais minimaliste, le programme n’est pas très bavard sur les causes d’erreur de lecture |
0,5/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
Très bon, solution optimale trouvée en un temps très correct (< 1s) |
3/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
L’affichage est correct et complet, mais une présentation plus compacte aurait augmenté la lisibilité. De plus, l’affichage du temps n’est pas très précis, seulement à la seconde près |
1/3 |
|
|
Comportement face à une solution impossible |
Non géré par le programme (crash) |
0/1 |
|
|
Documentation |
3/3 |
||
|
Complétude par rapport à ce qui est demandé |
Documentation de très bonne qualité réalisée avec doxygen |
1/1 |
|
|
Innovation dans les idées implémentées dans le code |
Algorithme de force brute simple et efficace grâce à une gestion correcte des transpositions, bien qu’un parcours en largeur aurait permis de trouver plus rapidement la solution optimale |
2/2 |
|
|
Analyse du code |
7/7 |
||
|
Organisation des fichiers |
Bon, le découpage en 5 fichiers représente un bon compromis |
1/1 |
|
|
Découpage en modules/classes |
Parfait, découpage pertinent en 5 classes (Mouvement Jeu Coordonnees Piece Position) |
1/1 |
|
|
Lisibilité du code |
Très bon, code facile à lire et à comprendre, commentaires utiles là où il faut |
3/3 |
|
|
Simplicité du code |
Code simple et réduit grâce à une bonne utilisation des possibilités du C++ et de sa bibliothèque standard |
2/2 |
|
|
Recompilation |
1,5/2 |
||
|
Complétude de la procédure et recompilation du programme |
Pas de problème avec mingw, un petit soucis avec cygwin (gcc4) : il manque un #include <cstdlib> dans main.cpp et un #include <cassert> dans jeu.cpp |
0,5/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Parfait, aucune bibliothèque non standard utilisée |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
0 |
||
|
Total |
16/20 |
6-3-6. JulienDuSud (corrigé par ram-0000)▲
La solution proposée par JulienDuSud peut être téléchargée ici (format zip).
Il s’agit d’un projet écrit en C++, développé à l’aide de CodeBlock pour un environnement non spécifié (mais probablement Linux).
6-3-6-1. Analyse par le challenger▲
3 algorithmes différents ont été implémentés, mais uniquement l’algorithme de « largeur-en-premier » sera utilisé pour obtenir un résultat.
En effet, c’est l’algorithme qui convient le mieux à la recherche de solution d’un jeu combinatoire tel que le Klotski.
Les autres algorithmes implémentés sont : profondeur-en-premier et gestion de sélection par coût réel+heuristique, mais ne seront pas utilisés pour résoudre le Klotski.
pseudo-code de l’algorithme implémenté :
----------------------------------------
OUVERT : queue vide
FERME : liste vide
S : état initial
mettre S dans OUVERT
tant que (vrai) alors
extraire un état N de OUVERT et l’introduire dans FERME
si N est équivalent à l’état recherché
terminer et retourner le cout jusque N
fsi
pour chaque successeur, M, de N
si M n’est pas dans OUVERT ou FERME alors
introduire M dans OUVERT
fsi
si M est dans OUVERT ou FERME alors
si le cout de M est inférieur à l’état trouvé alors
mettre à jour le cout de l’état trouvé par celui de M
fsi
si le cout a changé et que M était déjà dans FERME alors
transporter M de FERME à OUVERT
fsi
fsi
fpour
ftantOn s’occupera de l’expansion des états, c’est à dire trouver des successeurs à notre état courant dans la classe Klotski::KlotskiState. Étant donné que cette expansion est différente selon les règles du jeu, nous ne travaillerons sur l’expansion dans nos classes génériques Solver / State.
Le code a été écrit afin de pouvoir être réutilisable pour d’autres recherches. Que ce soit pour un simple pathfinding, pour la solution du sudoku, ou encore d’autres jeux, il suffit de dériver Solver::State et implémenter un gestionnaire d’états (tel que Klotski::KlotskiState) et d’implémenter, si nécessaire, les algorithmes de sélection et d’expansion.
6-3-6-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
5/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Rien à redire |
1/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
Les solutions optimales sont trouvées, mais temps de recherche est assez long comparé aux autres solutions (15 secondes) |
1/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
J’ai beaucoup aimé la barre de progression, l’affichage aurait mérité d’afficher plusieurs solutions en largeur simultanément pour afficher moins de lignes, l’affichage des différentes grilles est original, mais demande un petit peu de temps de compréhension, la gestion des caractères accentués n’est pas réussie |
2/3 |
|
|
Comportement face à une solution impossible |
Réponse immédiate |
1/1 |
|
|
Documentation |
3/3 |
||
|
Complétude par rapport à ce qui est demandé |
L’algorithme est bien décrit |
1/1 |
|
|
Innovation dans les idées implémentées dans le code |
Plusieurs algorithmes sont définis, ils héritent d’une classe de base virtuelle pure. Finalement, seul l’algorithme « largeur en premier » est utilisé. Cette architecture permettrait de définir un nouvel algorithme de manière simple. Le contrat qu’il doit remplir est défini, il ne resterait plus qu’à écrire les différentes fonctions de cet algorithme. |
2/2 |
|
|
Analyse du code |
6/7 |
||
|
Organisation des fichiers |
Les différentes classes (principalement les 3 algorithmes) auraient mérité chacune d’être dans un fichier séparé afin de faciliter la prise en main du projet |
0,5/1 |
|
|
Découpage en modules/classes |
Le programme est clairement découpé en classes |
1/1 |
|
|
Lisibilité du code |
Code très simple à lire, bien aéré et abondement commenté |
3/3 |
|
|
Simplicité du code |
Ce code demande tout de même au lecteur de bien connaitre le C++ afin d’en comprendre toutes les subtilités (utilisation de templates, de namespace). Il y a un paramètre std::string qui aurait mérité d’être passé par référence constante plutôt que par valeur dans la fonction LaunchKlotski() |
1,5/2 |
|
|
Recompilation |
2/2 |
||
|
Complétude de la procédure et recompilation du programme |
Rien à dire, le projet a été recompilé sous Visual Studio 2005 sous XP sans aucun problème et le binaire généré fonctionne. Seuls les caractères accentués n’ont pas supporté le portage, mais cela n’a pas été compté dans la notation |
1/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Une petite particularité du projet, il utilise boost. La version 1.38 sous Microsoft a pu être utilisée sans aucun problème |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
0 |
||
|
Programme soumis en 2 fois (durant la période du défi) |
-1 |
||
|
Total |
15/20 |
6-3-7. nfouille (corrigé par gangsoleil)▲
La solution proposée par nfouille peut être téléchargée ici (format zip).
Il s’agit d’un projet écrit en C, développé sans environnement particulier pour un environnement Solaris (à confirmer).
6-3-7-1. Analyse par le challenger▲
Lecture de la solution :
- les symboles ., -, | et # représentent les pièces : un carré, un rectangle horizontal, un rectangle vertical et l’âne rouge ;
- les symboles ^, v, < et > représentent les directions de déplacement des pièces : haut, bas, gauche et droite.
Dans le cas ou deux pièces pourrait effectuer le mouvement (au plus deux, car il y a deux cases vides) c’est la première de gauche à droite puis de haut en bas qui doit être déplacée, sauf si le mouvement est précédé d’un '2'
Le principe de résolution est de générer l’arbre complet des états possibles. En effet après une analyse du problème il s’avère que le nombre de combinaisons sans différencier les pièces est relativement petit.
La difficulté réside dans le codage / décodage d’un état sur un entier. Un tableau « f » sert à stocker la fonction d’évaluation qui à un état associe le nombre de mouvements minimal pour arriver à la solution.
La résolution consiste ensuite à prendre à chaque étape un mouvement qui envoie à un état dont le nombre de mouvements minimal est le nombre courant -1.
On peut également trouver toutes les solutions optimales par récursivité. On peut aussi changer la métrique pour arriver aux solutions.
Il existe 6 cas suivant le nombre de rectangles horizontaux ou verticaux, parmi les 5 :
- 5 rectangles verticaux, 0 horizontal ;
- 4 rectangles verticaux, 1 horizontal ;
- 3 rectangles verticaux, 2 horizontaux ;
- 2 rectangles verticaux, 3 horizontaux ;
- 1 rectangle vertical, 4 horizontaux ;
- 0 rectangle vertical, 5 horizontaux.
Pour chacun de ces cas, on peut majorer grossièrement le nombre d’états. Du au fait qu’on majore il faudra donner une validité à un état.
6-3-7-2. Notation du projet▲
|
Critère |
Commentaire |
Note |
|
|---|---|---|---|
|
Fonctionnement du programme |
5/8 |
||
|
Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces |
Rien à dire |
1/1 |
|
|
Obtention d’une solution valide. C’est le temps d’exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés |
Le temps de calcul est très long, même si le nombre de coups de la solution trouvée est bien optimal |
2/3 |
|
|
Affichage de la solution. C’est uniquement l’aspect « esthétique » de la présentation de la solution qui est noté |
L’affichage classique affiche le nombre de possibilités pour chaque état calculé, ce qui nuit à l’affichage et ne sert a rien. Pour ce qui est de l’affichage des positions, l’utilisation de symboles rend l’affichage complexe a lire, voir difficile à interpréter |
1/3 |
|
|
Comportement face à une solution impossible |
Trouve bien que la grille n’a pas de solution (mais au bout de 24 secondes tout de même) |
1/1 |
|
|
Documentation |
2/3 |
||
|
Complétude par rapport à ce qui est demandé |
Documentation un peu trop sommaire qui n’explique pas l’algorithme utilisé et les choix réalisés |
0,5/1 |
|
|
Innovation dans les idées implémentées dans le code |
Algorithme qui semble toujours trouver la solution optimale |
1,5/2 |
|
|
Analyse du code |
3/7 |
||
|
Organisation des fichiers |
Le projet se compose de 3 fichiers sans découpage évident |
0/1 |
|
|
Découpage en modules/classes |
Du fait du mauvais découpage en fichiers du projet, la notion de modularité du programme n’existe pas |
0/1 |
|
|
Lisibilité du code |
Le code est difficile à lire et manque cruellement de commentaires et d’aération |
1,5/3 |
|
|
Simplicité du code |
Le code est complexe à lire. Il y a de nombreux « magic numbers » un peu partout (par exemple int getSize() { return 12 * MAX_CONF_CAS[cas][0] * MAX_CONF_CAS[cas][1] * 15; }. Le code mélange les déclarations et le code, ce qui est interdit en C, peu ou pas de test des codes de retour des fonctions |
1,5/2 |
|
|
Recompilation |
1/2 |
||
|
Complétude de la procédure et recompilation du programme |
Le projet semble utiliser par défaut le compilateur Solaris. L’équipe ne disposant d’une plateforme Solaris, le projet a été recompilé avec le compilateur gcc sans aucune option de base, le projet se compile sans problème. Dès lors que les options de contrôle du code sont rajoutées, la compilation du projet génère 450 lignes de warnings. Si les options réellement contraignantes sont ajoutées (pedantic), il y a 470 lignes de warning |
0/1 |
|
|
Non-utilisation de librairies externes. L’usage de librairie externe sera détecté lors de la phase de link et c’est le bon sens collégial du jury qui statuera |
Rien à dire |
1/1 |
|
|
Bonus/Malus |
|||
|
Bonus projet C |
+2 |
||
|
Non-respect de la règle 2.7 des règles du défi concernant la libération des droits pour developpez.com. Une relivraison du fichier readme a dû être faite |
-2 |
||
|
Total |
11/20 |
6-3-8. ram-0000▲
En plus des solutions des participants au défi, je me permets de présenter la solution que j’ai développée. La solution proposée par ram-0000 peut être téléchargée ici (format zip). Il s’agit d’une solution développée avec Visual Studio 2005 sous environnement Windows. Le temps de réalisation est d’environ 30 heures.
L’algorithme implémenté est un algorithme qui construit la liste de toutes les grilles possibles et pour chaque grille identifie le meilleur chemin pour aller vers la solution. La grille testée est alors recherchée dans la liste des grilles et l’affichage de la solution est immédiat. Pour améliorer les performances, un fichier de cache des solutions est construit lors du premier usage et utilisé ensuite lors des relances ultérieures.
Il y a d’abord la génération de la liste des toutes les grilles initiales possibles avec la fonction GenerateGrille(). Cette fonction calcule tout d’abord toutes les grilles avec uniquement le gros carré. Puis pour chacune des 12 grilles obtenues, la fonction ajoute un rectangle horizontal ou vertical. Puis pour chacune des nouvelles grilles obtenues, il ajoute un 2e rectangle et ainsi de suite jusqu’à ce que toutes les pièces soient posées. Cette phase permet de générer les 363 480 grilles initiales possibles.
Une fois que toutes les grilles sont générées, la liste des mouvements possibles pour chacune des grilles est générée par la fonction GenerateMove(). Cette fonction génère un total de 1 112 092 mouvements différents possibles. Tous ces mouvements sont stockés dans une map pour permettre de les retrouver plus rapidement.
Chaque grille est identifiée par un hash unique qui est fonction de la disposition de la grille. Ce hash permet de rechercher de manière très rapide une grille particulière parmi la liste des grilles.
Une fois que tous les mouvements potentiels sont générés, le programme recherche le meilleur chemin pour la grille initiale. Pour cela, il part des positions gagnantes repérées lors de la création de toutes les grilles initiales par la fonction GenerateGrille(), c’est grille possèdent un éloignement du but qui vaut 0. À partir de ces grilles destination, il calcule la liste des grilles sources dont un des mouvements permet d’aller vers les grilles destinations. Il affecte alors à ces grilles source un éloignement de 1 par rapport au but final et sauve dans la grille le mouvement à effectuer pour se rapprocher du but. Et ensuite de manière récursive, il calcule l’éloignement de toutes les grilles par rapport au but final jusqu’à ce qu’il n’y ait plus de grilles sources. Cette phase permet d’identifier les 96 365 grilles qui n’ont pas de solution.
Une fois que ces phases initiales sont faites, la liste des grilles est sauvegardée dans un fichier de cache (le fichier DataGrille.bin de 17 Mo) qui sera réutilisé lors du prochain démarrage ce qui permet un recalcul beaucoup plus rapide lors du lancement suivant du programme.
Le fichier décrivant la position initiale est ensuite lu. Une fois que la grille est lue et valide, cette grille est recherchée dans la liste des grilles initiales et le chemin pour aller vers une des solutions finales et optimales est obtenu en effectuant, de proche en proche, le déplacement indiqué par la grille en un temps très rapide.
Remarque : compte tenu de la qualité des projets présentés lors de ce défi, ce projet n’aurait pas pu gagner.
6-4. Récapitulatif des notations▲
|
acetyle |
Chatanga |
Climoo |
coyotte507 |
jfouche |
JulienDuSud |
nfouille |
||
|---|---|---|---|---|---|---|---|---|
|
Fonctionnement du programme |
8 |
6 |
7 |
4,5 |
5,5 |
4,5 |
5 |
5 |
|
Résistance à un mauvais paramètre ou à un mauvais format de fichier |
1 |
0,5 |
1 |
1 |
0 |
0,5 |
1 |
1 |
|
Obtention d’une solution valide |
3 |
3 |
3 |
1 |
3 |
3 |
1 |
2 |
|
Affichage de la solution |
3 |
1,5 |
2 |
2 |
1,5 |
1 |
2 |
1 |
|
Comportement face à une solution impossible |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
Documentation |
3 |
2 |
2 |
2 |
1,5 |
3 |
3 |
2 |
|
Complétude par rapport à ce qui est demandé |
1 |
1 |
0,5 |
1 |
0,5 |
1 |
1 |
0,5 |
|
Innovation dans les idées implémentées dans le code |
2 |
1 |
1,5 |
1 |
1 |
2 |
2 |
1,5 |
|
Analyse du code |
7 |
4 |
5 |
5 |
3 |
7 |
6 |
3 |
|
Organisation des fichiers |
1 |
0,5 |
1 |
1 |
0 |
1 |
0,5 |
0 |
|
Découpage en modules/classes |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
Lisibilité du code |
3 |
1,5 |
2 |
2 |
1 |
3 |
3 |
1,5 |
|
Simplicité du code |
2 |
1 |
1 |
1 |
1 |
2 |
1,5 |
1,5 |
|
Recompilation |
2 |
2 |
2 |
2 |
1 |
1,5 |
2 |
1 |
|
Complétude de la procédure et recompilation du programme |
1 |
1 |
1 |
1 |
0 |
0,5 |
1 |
0 |
|
Non-utilisation de librairies externes |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
Autre |
||||||||
|
Bonus C vs C++ |
+2 |
0 |
+2 |
0 |
0 |
0 |
+2 |
|
|
Pénalité |
-1 |
-2 |
||||||
|
Total |
16/20 |
16/20 |
16/20 |
11/20 |
16/20 |
15/20 |
11/20 |
6-5. Synthèse des notes▲
- acetyle a obtenu une note de 16/20.
- Chatanga a obtenu une note de 16/20.
- Climoo a obtenu une note de 16/20.
- coyotte507 a obtenu une note de 11/20.
- jfouche a obtenu une note de 16/20.
- JulienDuSud a obtenu une note de 15/20.
- nfouille a obtenu une note de 11/20.
Quatre personnes ont donc une note de 16/20 et il ne faut qu’un gagnant. Il fallait donc réévaluer ces 4 projets et 3 axes étaient possibles :
- la meilleure documentation, le meilleur algorithme (l’algorithme a été inclus dans la documentation), la documentation la plus complète ;
- le meilleur programme, le plus rapide, la meilleure solution, le programme qui répond le mieux au besoin exprimé ;
- le meilleur code, le plus lisible, le plus portable, le mieux commenté.
Le jury a donc décidé que c’est l’aspect « meilleur programme » qui serait prépondérant, le programme qui répondrait le mieux et sans erreur au besoin exprimé.
- le projet de Climoo n’a pas été retenu, car il ne trouve pas la solution optimale ;
- le projet d’acetyle n’a pas été retenu, car il se crashe lorsque le programme est exécuté sans paramètre ;
- le projet de jfouche n’a pas été retenu, car il se crashe lorsque la grille analysée n’a pas de solution.
Le gagnant de ce défi est donc Chatanga et nous le félicitons tous.
7. Conclusion▲
De manière globale, on retiendra dans ce défi :
- l’excellente qualité des projets qui ont été présentés (4 projets à égalité avec une note de 16/20 et il y aurait pu y en avoir un cinquième avec celui de JulienDuSud s’il n’avait pas eu de pénalité pour double soumission) ;
- l’engouement pour ce défi (7 projets remis) plus un nombre conséquent de visites sur la page WWW du défi. Le nombre de visites sur cette page s’élève à 3142 visites et 2906 visiteurs depuis son lancement le 22 mars.
Dans les conseils aux futurs participants, il faudra bien retenir :
- ne pas oublier de bien relire et de bien comprendre ce qui est attendu pour le défi. À ce niveau d’excellence, la moindre erreur se paye cher ;
- ne pas soumettre trop tôt son projet. Si on a du temps et que l’on est en avance, ne pas hésiter à peaufiner les détails. On l’a vu dans ce défi, avec un tel niveau, tous les détails comptent.
Encore une fois, nous tenons à remercier tous les participants à ce défi et à féliciter notre grand gagnant Chatanga qui se verra remettre rapidement son prix sous la forme d’un bon d’achat Amazon de 40 € offerts par la rédaction de developpez.com.
Nous espérons vous retrouver nombreux pour le prochain défi qui ne devrait plus tarder maintenant.