1. Le cube de SOMA

Le défi de ce mois consiste à rechercher des solutions au cube de SOMA.

La grande nouveauté de ce défi est qu'il est ouvert à tous les langages et toutes les technologies.

Ce document présente :

  • La description et le fonctionnement du cube de SOMA,

  • L'organisation et les règles mises en place autour de ce défi,

  • La description de ce que doit faire le programme pour répondre au besoin 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. Description et fonctionnement du cube de SOMA

Ce paragraphe est largement inspiré de la page Wiki qui traite du cube de SOMA à cet endroit.

2-1. Histoire

Le cube SOMA est un casse-tête inventé dans les années 1930 par le poète et scientifique danois Piet Hein.

Selon la légende rapportée en 1958 par Martin Gardner, ce casse-tête aurait été inventé par Hein en 1936, pendant un cours de mécanique quantique donné par Werner Heisenberg ; néanmoins, Ole Poul Pedersen a trouvé en 2003 un brevet danois, déposé par Hein dès le 2 décembre 1933.

Le nom, SOMA, est tiré de la nouvelle d'Aldous Huxley, Le Meilleur des mondes. Cette nouvelle décrit une société du futur dans laquelle le SOMA est une drogue addictive, grâce à laquelle chaque élément de la société est heureux et ne revendique rien.

2-2. Principe

Le casse-tête consiste en sept pièces formées de cubes unitaires qui doivent être assemblées pour former un cube 3×3×3. Les pièces peuvent aussi être combinées en une grande variété d'autres motifs.

Ce puzzle est souvent considéré comme l'équivalent en trois dimensions des polyminos.

2-3. Détail des sept pièces du cube

Les éléments du cube SOMA sont formés de toutes les combinaisons possibles de quatre cubes unitaires ou moins, à l'exception des formes convexes (i.e., les cuboïdes 1×1×1, 1×1×2, 1×1×3, 1×1×4 et 1×2×2). Il reste donc seulement un tricube (pièce composée de 3 cubes unitaires) et six tétracubes (pièces composées de 4 cubes unitaires), deux d'entre eux formant une paire d'énantiomères.

Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
tricube « V » tétracube « L » tétracube « T » tétracube « Z » tétracube « A » tétracube « B » tétracube « P »

2-4. But du cube de SOMA

Le but du jeu est de reconstituer une forme donnée (un puzzle) en utilisant les 7 éléments. Le premier puzzle est bien sûr de reconstituer le cube (il y a 240 solutions distinctes pour reconstituer le cube).

Cube de SOMA
Cube de SOMA

Il existe une grande collection de formes réalisables. Toutes les formes présentées ici sont issues de ce site

Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Image non disponible Image non disponible        

Il existe aussi des formes qui n'ont pas de solution.

3. Organisation et règles de ce défi

Ce paragraphe décrit les règles applicables à ce défi. Les règles générales applicables en temps normal aux défis C & C++ ne sont pas applicables dans le cadre de ce défi.

3-1. Les participants

Aucune inscription aux défis n'est nécessaire mis à part bien sûr d'être enregistré comme membre des forums. La simple soumission du travail effectué est suffisante pour s'ajouter à la liste des participants.

Les participants peuvent, s'ils le souhaitent, se constituer en équipe pour un défi. Ils doivent alors nommer un responsable d'équipe. C'est cette personne et elle seule qui doit soumettre le résultat du travail de l'équipe. Une personne membre d'une équipe ne peut être membre d'une autre équipe ni participer à titre individuel au défi.

Les modérateurs, rédacteurs, administrateurs, responsables (en somme, toute personne ayant des plumes ou des étoiles quoi) peuvent aussi participer au défi de manière individuelle ou en équipes constituées avec un responsable identifié lors de la soumission. Leur travail sera alors classé dans la catégorie Responsables DVP". Il suffit d'un seul modérateur, rédacteur, administrateur ou responsable dans l'équipe pour que toute l'équipe passe dans la catégorie "Responsables DVP".

Une seule soumission par participant ou par équipe est autorisée, celle-ci une fois faite ne peut plus être modifiée.

3-2. Durée et suivi du défi

La durée de ce défi est de 8 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 13 septembre 2009 et la date de fin de soumission des projets est fixée au dimanche 8 novembre 2009 à minuit (c'est la date et heure de dépôt du fichier qui fera foi).

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.

Tous les participants ont le droit de poser des questions sur l'énoncé du problème en cas de points obscurs ou mal compris. Les réponses seront aussi portées de manière publique sur ce fil. Les organisateurs, les participants ayant moins de difficultés mais aussi les autres forumeurs peuvent également répondre sur ce fil.

3-3. Langages et technologies

Pour la première fois, tous les langages (C, C++, Pascal, Perl, Python, ...) et toutes les technologies Office, PHP, ...) peuvent participer à ce défi.

Comme l'organisateur de ce défi n'est pas supposé maitriser tous les langages possibles et toutes les technologies existantes, il est demandé au différents participants de vérifier si le langage ou la technologie qu'ils utilisent est maitrisée par un des membres du jury (cf paragraphe 3.7) et en cas de non support, d'envoyer un petit MP à l'organisateur du défi (ram-0000) qui fera le nécessaire pour recruter un membre du jury connaissant ce langage ou cette technologie.

3-4. Licence des codes sources

Les codes sources des projets doivent obligatoirement être libres de droits pour une éventuelle intégration dans les pages Sources sur Developpez.com. Cette mention doit être apportée explicitement dans tous les sources du projet.

L'accord du participant devra être précisé dans le fichier README qui se trouvera dans l'archive du travail effectué.

A titre d'information, le texte d'accompagnement de votre projet pourrait être :

Copyright ©2009 <votre pseudo ou votre nom>.
Les sources qui constituent ce projet <Nom du projet> de même que la documentation associée sont la propriété de leur auteur.
Je donne mon accord au site developpez.com pour l'utilisation de tout ou partie des sources et de la documentation de ce projet dans les pages developpez.com

3-5. Soumission des projets

Les codes sources doivent suivre les règles suivantes :

  • Le code peut être écrit dans n'importe quel langage.
  • Le code doit être présentable ce qui implique donc de fournir un code relativement bien aéré (mais pas trop non plus) et avec des tabulations homogènes.
  • Des commentaires sur les zones critiques des codes sont vivement recommandés, cela permet de mieux comprendre l'implémentation de chacun.
  • Les codes sources doivent être testés. Leur compilation ne doit pas laisser paraître d'erreurs ni d'avertissements. Toutefois, les avertissements peuvent pour certains être éventuellement tolérés si vous savez ce que vous faites et que vous pouvez le justifier.
  • Chaque projet doit être accompagnée d'une documentation minimum. Cette documentation peut décrire la procédure de recompilation, le fonctionnement du programme, les algorithmes utilisés, les choix d'architecture et toute autre information qui pourrait être utile lors de l'évaluation du projet.
  • Lors de la soumission du défi, c'est le projet complet qui doit être remis (à l'exception des fichiers objets intermédiaires). Si le projet comprend un fichier de génération (makefile par exemple) ou des fichiers spécifiques à l'environnement de développement (Visual Studio par exemple), ceux-ci doivent faire partie de la livraison du projet.

Pour chaque soumission de projet il faut fournir obligatoirement les informations suivantes :

  • Un texte de licence autorisant developpez.com à diffuser votre travail.
  • Le langage et/ou technologie utilisée.
  • Le système d'exploitation sur lequel la compilation et les tests ont été faits.
  • Une description de la machine sur laquelle les tests ont été réalisés (type de CPU, quantité de RAM, ...).
  • Le compilateur/EDI utilisé avec les options de compilation.
  • Le numéro de version de la technologie, par exemple .NET 3.0 ou PHP 5.1
  • La liste précise des bibliothèques utilisées (ainsi que leur numéro de version si nécessaire)
  • Le temps passé (approximativement) pour concevoir et réaliser votre projet.

Tout projet ne fournissant pas ces information sera rejeté.

Les travaux des participants doivent obligatoirement être fournis sous la forme d'une archive (zip, tar.gz, ...). Il est obligatoire que l'archive contienne un fichier README ainsi que les fichiers nécessaires à la regénération complète du projet.

Le nom des archives doit obligatoirement avoir le format suivant: <pseudo>.<ext>. Où : <pseudo> est le pseudo ou nom du participant et <ext> est l'extension de l'archive (.zip, .rar, .tar, .tgz, ...).

Les soumissions ne peuvent se faire que par le biais du formulaire de soumission suivant : http://c.developpez.com/defis/upload/. Cette soumission peut être confirmée par un petit MP à tous les membres du jury afin de les informer de la présence de votre travail.

3-6. Composition du jury

Le jury est composé des personnes suivantes :

Nom Langage
ram-0000 C & C++
r0d C & C++
Jean-Marc.Bourguet C & C++
gorgonite Python
Baptiste Wicht Java
Franck SORIANO Delphi, VB.Net

4. Spécification du programme

4-1. Démonstration

En plus de la création du programme décrit dans le paragraphe suivant, le challenger doit démontrer de manière textuelle (et pas simplement montrer) que la forme suivante n'a pas de solution :

Image non disponible

Cette démonstration doit figurer dans un fichier texte accompagnant le projet.

4-2. Fonctionnement attendu du programme

La spécification du fonctionnement du programme est volontairement laissée floue afin que les différents challengers puissent exprimer leur créativité. Toutefois, le fonctionnement minimal attendu du programme est le suivant :

  • Le programme peut fonctionner au choix en mode graphique ou bien en mode console.

  • La forme du puzzle recherché doit être spécifiée par un fichier donné en paramètre au programme lors du lancement (programme en mode console) ou alors par l'IHM du programme (programme graphique). Le format du fichier décrivant le puzzle à rechercher est décrit dans le paragraphe 4.4.

  • Le programme doit vérifier que le fichier décrivant le puzzle respecte bien le format imposé (voir le paragraphe 4.4 pour la spécification du format de ce fichier).

  • Le programme doit rechercher la (ou une des) solution(s) au puzzle proposé et il doit afficher le résultat de cette recherche (présence ou absence de solution).

  • Optionnellement, le programme peut afficher la solution trouvée.

4-3. Contraintes de développement

Il n'y a aucune contrainte de développement sur ce défi. Toutes les librairies, tous les frameworks, toutes les IHM peuvent être utilisés. Toutefois, les challengers doivent prendre en compte la difficulté qu'il pourrait y avoir à recompiler leur projet. Ils doivent faire en sorte que l'environnement de développement à reproduire par les correcteurs soit le plus simple possible. Lâchez vous mais pensez tout de même aux correcteurs.

Il n'y aura pas de pénalités ou de différences de notation entre un projet en mode console (donc pourvu d'une interface simplifiée) et une interface graphique complète. Seule l'originalité de la solution et aussi l'absence de bug) sera notée.

4-4. Format du fichier décrivant le puzzle

Le fichier décrivant le puzzle dont on recherche la solution respecte le format suivant :

  • C'est un fichier au format CSV (valeurs séparées par des virgules).

  • Chaque ligne du fichier CSV représente les coordonnées 3D de la position d'un des cubes du puzzle (un fichier normalement constitué doit donc posséder 27 lignes).

  • La 1ère valeur d'une ligne représente l'abscisse, la 2ème valeur représente l'ordonnée et la 3ème valeur représente la profondeur de la coordonnée 3D.

  • La valeur 0 représente la gauche sur l'axe des abscisses, le bas sur l'axe des ordonnées ou le devant sur l'axe des profondeurs.

  • Les valeurs de l'abscisse, de l'ordonnée et de la profondeur peuvent varier entre 0 et 9 uniquement.

  • L'ordre de spécification des différentes coordonnées dans le fichier ne doit pas avoir d'importance, la seule chose importante est qu'il y ait 27 points.

  • Si une des lignes du fichier ne respecte pas l'une de ces règles, le fichier doit être considéré comme invalide.

2 fichiers respectant ce formalisme sont fournis à titre d'exemple :

Ces fichiers sont fournis à titre d'exemple, ils ne seront probablement pas utilisés par le jury lors de la notation des différents projets. Les challengers sont libres de créer et d'utiliser d'autres fichiers lors du développement de leur solution.

monnomamoi a créé les fichiers représentant les 24 premières formes réalisables du chapitre 2.4. L'archive .zip contenant ces fichiers est téléchargeable ici. Les fichiers dont le nom contient un underscore n'ont pas le bon nombre de points (figures pas assez lisibles). Les fins de ligne sont au standard Unix.
Merci à lui pour sa contribution.

4-5. Critères généraux d'évaluation des projets

Les grandes orientations de la notation des projets porteront sur les points suivants :

  • Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1.

  • Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur.

  • Capacité du programme à détecter l'absence de solution au puzzle proposé.

  • Capacité du programme à trouver une solution au puzzle proposé.

  • Fonctionnalité optionnelle, capacité du programme à afficher la solution trouvée. La notation fera qu'il n'y aura pas d'avantage pour les programmes purement graphiques par rapport aux programmes purement console. Toutefois, il est clair qu'il est beaucoup plus difficile d'afficher une solution 3D en mode console. Les challengers qui choisiront cette voie devront donc être imaginatifs et originaux lors de l'affichage de la solution.

  • Qualité de la documentation accompagnant le projet. La qualité de la documentation est jugée uniquement sur le fond. Un fichier texte suffit parfaitement, nul besoin d'un logiciel de PAO pour rédiger la documentation de ce défi.

Les critères d'évaluation des différents projets sont :

Critère Détails Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1 4/20
     
Documentation Qualité de la documentation accompagnant le projet 4/20
     
Analyse du code   6/20
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet 2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires 2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible 1
  Facilité à recréer l'environnement de développement nécessaire au projet 1
     
Fonctionnement du programme   6/20
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur 2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé 4
     
Total   20/20

5. Analyse des projets

5-1. Liste des participants

Les personnes ayant participé jusqu'au bout à ce défi sont par ordre alphabétique :

Nous les remercions pour leur participation à ce défi ainsi que tous les autres participants qui ne sont pas allés jusqu'au bout de la démarche mais qui ont tenté de participer.

Les archives des différents projets qui n'étaient pas au format .zip ont été repackagées dans un fichier au format .zip (il semble que ce format de compression soit le plus standard)

Initialement, il était prévu par les règles du défi qu'il y aurait un classement spécifique pour les rédacteurs, modérateurs et autres responsables de rubrique. pseudocode étant la seule personne à entrer dans cette catégorie, le jury a décidé qu'il n'y aurait au final qu'un seul classement, son statut de modérateur ne l'ayant pas favorisé (ni défavorisé d'ailleurs) dans ce défi.

5.2. Fichiers de test

Ce paragraphe présente les fichiers de tests qui ont été utilisés pour valider les différents projets soumis.

Nom du fichier Contenu Comportement attendu du programme
Fichier 1 Trop de lignes Le programme doit afficher que le format du fichier est invalide (si possible en donnant la raison explicite)
Fichier 2 Pas assez de lignes Le programme doit afficher que le format du fichier est invalide (si possible en donnant la raison explicite)
Fichier 3 Format d'une des lignes invalide Le programme doit afficher que le format du fichier est invalide (si possible en donnant la raison explicite)
Fichier 4 Coordonnées invalides Le programme doit afficher que le format du fichier est invalide (si possible en donnant la raison explicite)
Fichier 5 Puzzle sans solution Le programme doit afficher que ce puzzle n'a pas de solution
Fichier 6 Puzzle avec une solution Le programme doit afficher qu'il y a au moins une solution (en affichant si possible la solution)

5.3. Relecture de la démonstration

La relecture de la démonstration de tous les projets a été faite par ram-0000. Les critères de notation de cette démonstration sont :

  • Concision de la démonstration (une démonstration courte à plus de chance de ne pas avoir d'erreur)
  • Validité de la démonstration (il faut quand même que cette démonstration soit juste)
  • Facilité de lecture de la démonstration

A titre d'exemple, et parce qu'il ne peut y avoir une seule démonstration valide, la démonstration suivante est proposée. Elle est issue de la revue "Pour la Science" du mois d'août 2009 (page 83).

On a envie de réaliser, avec les sept pièces du SOMA, le mur en W. Pourtant c'est impossible. La preuve la plus simple est due à Richard Naylor de Denver dans le Colorado.
Image non disponible
Considérons les dix coins du mur (en vert sur la figure, 1 de ces coins est caché par la forme elle-même). Chacun des tétracubes « L » et « T » peut occuper au plus 2 coins. Chacune des autres pièces placées dans le mur ne peut occuper qu'un seul coin (quelques secondes d'attention pour chacune vous en persuaderont). Au total, sans même prendre en compte les contraintes que les pièces s'imposent les unes aux autres quand on veut les placer ensemble dans le mur, on voit donc qu'elles ne peuvent occuper au mieux que 9 des 10 coins. La figure est donc impossible.

6. Commentaires sur les projets

6-1. Projet de ClodoDuNet

La solution proposée par ClodoDuNet peut être téléchargée ici. Il s'agit d'un projet en mode console écrit en C++ avec Code::Blocks et gcc (MinGW version 5.1.4).

Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration très longue (38 pages) qui par une approche brute force montre que la forme en "W" n'a pas de solution. L'approche est intéressante (on place les pièces 1 par 1 dans la forme en "W" dans toutes les positions qu'elles peuvent occuper) jusqu'à ce que l'on ne puisse plus placer de pièces ou bien que l'on trouve une solution. Malheureusement, par flemme je n'ai pas vérifié toutes les positions (il y a en près de 48000). La démarche semble rigoureuse mais la démonstration par "brute force" est vraiment trop longue à vérifier. 1,5/4
       
Documentation Qualité de la documentation accompagnant le projet. Bonne présentation, explications claires, mais documentation un peu trop longue (pas assez synthétique). 3,5/4
       
Analyse du code     3/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Arborescence particulière, mais efficace. 1,5/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Code très commenté, mais la présentation complique beaucoup la compréhension. 1/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Indentation et présentation incompréhensibles. 0/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Peu de fichiers, bonne arborescence. Il manquait juste un fichier de projet (.cbp pour code::clocks). 0,5/1
       
Fonctionnement du programme     3,5/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Mis à part un crash lorsqu'il manque des données (fichier 3), bonne résistance générale. 1,5/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. La ou les solutions ne sont pas toujours trouvée. 2/4
       
Total     11,5/20

6-2. Projet de jaffael

La solution proposée par jaffael peut être téléchargée ici. Il s'agit d'un projet en mode graphique écrit en Delphi avec Delphi 7 - Edition professionelle.

Un petit aperçu du programme de jaffael
Un petit aperçu du programme de jaffael
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration longue (8 page) mais très facile à lire. L'approche de la démonstration est une approche brute force mais orientée dès le début en essayant de placer les 3 pièces tridimensionnelle (pièces P, A et B). La démonstration énumère les positions que peuvent prendre ces 3 pièces et conclut que le puzzle est impossible à résoudre. La longueur de cette démonstration, qui semble rigoureuse, n'exclut toutefois pas la présence d'erreurs. 2/4
       
Documentation Qualité de la documentation accompagnant le projet. La documentation se compose du README demandé pour le défi. C'est assez succinct mais il n'y a pas grand-chose à dire non plus. 3/4
       
Analyse du code     5/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Il n'y a pas beaucoup de classes ou de composants différents dans l'application, donc on comprend assez bien l'organisation des différents éléments. 1/2 points sont enlevés à cause de l'architecture de l'application en elle-même : il y a bien des classes et des fichiers différents pour modéliser les structures de données. En revanche l'algorithme de résolution principal est implémenté directement dans la fiche et mélange "algorithme" et "IHM" ce qui est dommage. 1,5/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. C'est globalement très bien. A quelques remarques près : les commentaires décrivant le rôle de chaque méthode sont définit sur la partie implémentation uniquement. Il n'y a pas de commentaire dans la déclaration de la classe. Il est ainsi plus difficile d'avoir une vision globale de chaque classe et du rôle de chaque méthode puisqu'il faut aller dans l'implémentation pour les trouver. 1,75/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Pas grand-chose à dire. Le code est indenté, bien aéré, assez facile à lire. Peut-être quelques sauts de lignes en excès. 0,75/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Rien a redire, on ouvre le projet dans Delphi, il compile et démarre sans problème. On ne peut pas faire plus simple. 1/1
       
Fonctionnement du programme     4,75/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Lorsqu'on essaie d'ouvrir un cube erroné, les messages d'erreurs manquent un peu de précision. On sait globalement que le cube est invalide mais on ignore la cause (ligne manquante, en trop, ligne incorrecte, ...). De plus, le fichier 4 n'est pas détecté comme invalide. Le cube est chargé, le programme essaie de le résoudre et trouve qu'il n'a pas de solution. L'application en elle même résiste bien aux mauvais traitements. Le seul "bug" que j'ai pu trouver : on peut maximiser la fenêtre, et l'affichage ne tient pas compte de la nouvelle taille. 1/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Le programme a bien résolu (ou invalidé) tous les puzzle qui ont été testés. Les fichiers de test ont tous été résolus en moins de 500ms, et ce malgré la mise à jour de l'affichage entre chaque test. La seule imperfection réside peut-être dans le fait que le programme n'élimine pas automatiquement les solutions équivalentes par symétrie. 3,75/4
       
Total     14,75/20

6-3. Projet de monnomamoi

La solution proposée par monnomamoi peut être téléchargée ici. Il s'agit d'un projet en mode console avec un module de visualisation graphique de la solution trouvée écrit en python python-2.6.2 et vpython-5.13.

Un petit aperçu du programme de monnomamoi
Un petit aperçu du programme de monnomamoi
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Pas de démonstration. 0/4
       
Documentation Qualité de la documentation accompagnant le projet. README complet... Code bien commenté, ce qui donne une documentation Doxygen intéressante pour les développeurs. 4/4
       
Analyse du code     5/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Rien à redire, si ce n'est un main un peu trop long, qui aurait pu être scindé pour des raisons de lisibilité. 1,75/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Indentation assurée par le langage. Les commentaires, bien que compréhensibles se limitent au minimum nécessaire pour séparer les parties ou générer la documentation Doxygen. 1,5/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Rien à redire. 1/1
  Facilité à recréer l'environnement de développement nécessaire au projet. vpython n'est pas compatible avec les versions >= 2.6.3, dur pour ceux qui ont fait l'effort de migrer en python 3. Tout le reste est compris en standard. 0,75/1
       
Fonctionnement du programme     5,75/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Le jeu de tests passe parfaitement mais aucune information détaillée sur les erreurs de format ne sont renvoyées. 1,75/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Les résultats obtenus collent au jeu de test. 4/4
       
Total     14,75/20

6-4. Projet de nlegriel

La solution proposée par nlegriel peut être téléchargée ici. Il s'agit d'une application en mode graphique écrite en Java (1.6.0_16) avec Eclipse (3.5).

Un petit aperçu du programme de nlegriel
Un petit aperçu du programme de nlegriel
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration longue (11 pages) dont la démarche est facile à suivre et agrémenté de nombreux dessins clairs. Une approche intéressante qui consiste à regarder les différentes positions possibles pour la pièce Z afin de tenter de placer ensuite les 3 pièces tridimensionnelles A, B et P en concluant assez rapidement que le puzzle est impossible à résoudre. 2,5/4
       
Documentation Qualité de la documentation accompagnant le projet. Documentation très complète (même UML) et très bien écrite. Comprend même des tests unitaires. 4/4
       
Analyse du code     4,5/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Découpage en classes très bien fait. 2/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Un peu trop de commentaires parfois. Méthodes un peu longue. 1,5/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Code très bien présenté, mais certaines parties de code un peu lourdes. 0,75/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Utilisation facilitée avec Maven 2 mais main-class non configurée et installation de Java3D dans library path. 0,25/1
       
Fonctionnement du programme     5/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. A résisté à tous les cas de mauvais fichiers de puzzle. 2/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Trouve une solution à tous les puzzles relativement rapidement (5 à 30s). Impossible de naviguer dans la solution. 3/4
       
Total     16/20

6-5. Projet de phymbert

La solution proposée par phymbert peut être téléchargée ici. Il s'agit d'une application en mode console et graphique écrite en Java (1.5) avec Eclipse.

Il n'a pas été possible de faire fonctionner l'interface en mode graphique (de toute façon, elle n'est pas notée), seule le programme en mode console est noté.

Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Pas de démonstration. 0/4
       
Documentation Qualité de la documentation accompagnant le projet. Documentation quasi inexistante, javadoc dans le code, algo commenté dans le code. 2/4
       
Analyse du code     4,75/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Classes bien découpées, utilisation de 2 modules Maven. 2/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Le code est bien lisible, les commentaires sont pour la plupart pertinent et bien placés. Quelques méthodes sont un peu trop longues. 1,5/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Le code est bien présenté. 1/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Script d'installation de Java3D ne fonctionne pas, mvn install ne passe pas car échec des tests unitaires après 30 minutes. 0,25/1
       
Fonctionnement du programme     3,75/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Exception en cas de puzzle invalide, ce n'est pas très clair. 1,5/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Trouve très rapidement (< 1s) une solution aux puzzles. Trouve des solutions à des puzzles insolubles. Indique que certains puzzles sans solution sont invalides et non pas insolubles. 2,25/4
       
Total     10,5/20

6-6. Projet de pip1000

La solution proposée par pip1000 peut être téléchargée ici. Il s'agit d'une application en mode graphique écrite en Java (1.5 avec compatibilité 1.6).

Un petit aperçu du programme de pip1000
Un petit aperçu du programme de pip1000
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Simple, concis (3 lignes) et efficace. C'est la même démonstration que celle proposée en exemple dans le §5.3. 4/4
       
Documentation Qualité de la documentation accompagnant le projet. Documentaire claire, installation et algorithme bien expliqué. 4/4
       
Analyse du code     4,5/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Classes et interfaces très bien séparées, packages différents. 2/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Code très clair, mais commentaires parfois un peu redondants, méthodes claires. Par contre, quelques bouts de code pourraient être revus. 1,25/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Code très bien présenté, mais parfois rendu assez lourd par la présence de beaucoup de commentaires. 0,75/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Installation de Java3D nécessaire. 0,5/1
       
Fonctionnement du programme     6/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. A résisté à tous les mauvais fichiers. 2/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. A trouvé très rapidement (< 200ms) une solution à tous les puzzles essayés. 4/4
       
Total     18,5/20

6-7. Projet de plegat

La solution proposée par plegat peut être téléchargée ici. Il s'agit d'une application en mode console écrite en Java avec Netbeans 6.7.1 et le JDK officiel Sun (version 1.6.0, build 1.6.0-b105).

Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration de 2 pages dont le raisonnement est facile à suivre. La démarche consiste dans cette démonstration à rechercher toutes les solutions possèdant les 3 pièces tridimensionnelles A, B et P pour ensuite placer les pièces T et Z. La particularité de la démarche est que les placements A, B et P qui occupent 3 centres de face sont éliminés car ils empêchent d'office le placement des pièces T et Z. Fort logiquement, la démonstration conclut sur une impossibilité de résoudre ce puzzle. 2,5/4
       
Documentation Qualité de la documentation accompagnant le projet. Documentation complète (PDF + Javadoc complète). Manque néanmoins quelques explications au niveau de l'explication des algos utilisés. 3,5/4
       
Analyse du code     5,25/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Les classes sont bien découpées, quoi qu'un peu longues pour certaines. L'organisation est très claire. 1,75/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Code très bien commenté, mais les méthodes sont parfois très longues et plutôt difficiles à digérer. 1,5/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Code très bien présenté, rien à redire. 1/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Aucuns soucis de ce côté-là. 1/1
       
Fonctionnement du programme     6/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. A résisté à tous les cas de mauvais paramètres. 2/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. A très rapidement (< 1s) trouvé les solutions aux puzzles proposées et a trouvé qu'il n'y avait pas de solution pour les puzzles insolubles. 4/4
       
Total     17,25/20

6-8. Projet de pseudocode

La solution proposée par pseudocode peut être téléchargée ici. Il s'agit d'une application en mode graphique écrite en Java (1.6) avec Eclipse (3.5).

Un petit aperçu du programme de pseudocode
Un petit aperçu du programme de pseudocode
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Simple, concis (32 lignes) et efficace. C'est la même démonstration que celle proposée en exemple dans le §5.3 avec en prime des dessins en ASCII art (pas toujours faciles à comprendre). 4/4
       
Documentation Qualité de la documentation accompagnant le projet. Documentation limitée à l'explication des outils utilisés et à l'utilisation simple du programme. 2/4
       
Analyse du code     5,25/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Les classes sont bien séparées, mais les méthodes sont parfois un peu longues. 1,5/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Code très bien commenté et facile à comprendre. 2/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Bonne présentation mais code parfois un peu lourd à lire avec plusieurs lignes collées les unes aux autres et quelques bouts de code qui auraient pu être revus. 0,75/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Environnement complet fourni avec le projet, découpage clair entre librairies, binaires et sources. 1/1
       
Fonctionnement du programme     6/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. A résisté à tous les cas de mauvais paramètres. 2/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. A très rapidement (< 1s) trouvé les solutions aux puzzles proposées et a trouvé qu'il n'y avait pas de solution pour les puzzles insolubles. 4/4
       
Total     17,25/20

6-9. Projet de requinham

La solution proposée par requinham peut être téléchargée ici. Il s'agit d'un projet en mode console écrit en C99 avec Visual Studio 2005.

Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Il ne s'agit pas vraiment d'une démonstration mais plutôt du résultat d'une démarche brute force avec retour arrière pour tenter de placer toutes les pièces du puzzle. La démonstration conclut fort justement mais en 4600 lignes tout de même qu'il est impossible de résoudre cette forme. La démarche exposée dans cette démonstration est impossible à suivre. 1/4
       
Documentation Qualité de la documentation accompagnant le projet. Il n'y a aucune documentation accompagnant le fichier source (ni description de l'algorithme, ni description de la structure du programme). Le code est commenté mais de manière insuffisante pour suppléer à cette absence. 0,5/4
       
Analyse du code     3,75/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Le projet est composé d'un seul fichier, écrit dans un style impératif pur des plus classiques. 2/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Si le déroulement du code est simple dans son principe, l'abus de variables globales le rend parfois difficile à suivre. 1/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Le mélange entre l'anglais et le français dans le choix des noms est génant. Les choix du format du code sont parfois étranges. Il y a beaucoup de code répété avec des changements mineurs. 0/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Le code a compilé sous Linux après quelques modifications simples pour supprimer des spécificités (presque totalement inutilisées) de Windows. 0,75/1
       
Fonctionnement du programme     5/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Un fichier mal formé est capable de faire crasher le programme. 1/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Rien à dire. 4/4
       
Total     10,25/20

6-10. Projet de Shadowbiwan

La solution proposée par Shadowbiwan peut être téléchargée ici. Il s'agit d'un projet en mode graphique écrit en VB.Net sous Visual Studio 2008 avec le Framework 3.5.

Un petit aperçu du programme de Shadowbiwan
Un petit aperçu du programme de Shadowbiwan
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration facile à lire sur 3 pages avec des graphiques clairs qui permettent d'appuyer la démarche. Cette démonstration commence d'abord par énumérer toutes les positions possibles pour la pièce P qui possède le moins de libertés de placement. Ensuite, pour chacunes des positions identifiées (4 après simplifications dûes aux 2 symétries existantes dans la pièce), on tente de placer les tétracubes A et B. Cette démarche conclut fort logiquement que la forme est impossible à résoudre. 2,5/4
       
Documentation Qualité de la documentation accompagnant le projet. Toutes les classes et méthodes ont été commentés en utilisant les commentaires XML de Visual Studio, du coup l'explication de chaque méthode est directement fournie par l'intellisense dans VS, sans avoir à chercher les informations. De plus le programme possède une aide en ligne qui décrit chaque fonctionnalités, ainsi que les raccourcis clavier. Il manque peut-être juste un petit diagramme de classes pour mieux présenter l'architecture générale de l'appli. 3,5/4
       
Analyse du code     4/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. On fait bien la distinction entre l'IHM et les traitements fonctionnels. En revanche la modélisation "Objet" n'est pas très naturelle. On a des classes dont les noms désignent des fonctionnalités (ClsManualSearch, ClsSortFromView, ClsSortFromNum, voir même ClsThreads), d'autres désignent des objets (ClsSOMA, ClsCube). De plus, en dehors de l'IHM, les noms des fichiers ne sont pas très explicites ("Module et Classes.vb"). 1,5/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Il y a pas mal de code assez long, avec des noms de variables pas toujours très significatif. Du coup il est plus difficile de comprendre le déroulement du code. Ce sont surtout les commentaires abondants qui permettent de s'y retrouver. 1/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. La présentation du code en soit est irréprochable. Par contre, il y pas mal de méthodes assez longues, avec parfois des noms peu explicites (Méthodes qui s'appellent "Tester", variables "Atester"…). 0,5/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Rien à redire. On ouvre le projet dans Visual Studio, ça compile, ça tourne ! 1/1
       
Fonctionnement du programme     6/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. C'est nickel ! Tous les mauvais fichiers sont détectés correctement, avec un retour précis en cas d'erreur. L'IHM réagit bien. 2/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Très bon temps de résolution (50ms), le programme indique les cubes sans solutions, résoud les autres cubes. Il est capable de compter le nombre de solution existantes. Il existe même un mode "recherche manuel" permettant de placer manuellement une pièce dans le cube pour essayer de reconstruire la figure. 4/4
       
Total     16/20

6-11. Projet de Tesing

La solution proposée par Tesing peut être téléchargée ici. Il s'agit d'un projet en mode console ou graphique écrit en python (Python 2.6.2 et Visual Python 5.13).

Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration très longue (20000 lignes) très fastidueuse à lire et impossible à vérifier dont la plus grande partie est générée par un script. La démarche est une approche brute force avec retour arrière pour tenter de placer toutes les pièces pour en arriver à la conclusion que la forme est impossible à résoudre. 1/4
       
Documentation Qualité de la documentation accompagnant le projet. README complet. Il manque quelques commentaires pour générer une documentation automatique "complète". 3,75/4
       
Analyse du code     4/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Quelques fonctions trop longues. Il était pourtant facile de scinder/factoriser du code. 1,5/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Trop de boucles for imbriquées, ça nuit à la compréhension. Il manque quelques commentaires pour générer une doc automatique "complète" mais les commentaires en # sont présents. 1,75/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. L'indentation est assurée par la syntaxe python, mais parfois le code n'est pas assez divisé pour laisser apparaître clairement sa structure. 0,75/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Impossible de recréer l'environnement de développement nécessaire à ce projet (voir plus bas pour plus d'explication). 0/1
       
Fonctionnement du programme     5/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Voir plus bas pour plus d'explication. 1/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Voir plus bas pour plus d'explication. 4/4
       
Total     13,75/20

Explication sur la notation du projet de Tesing. Malgré le temps passé dessus, le relecteur (gorgonite) n'a pas réussi a reproduire l'environnement de développement. Le projet utilise les exceptions (avec le mot clé "as"), il faut au minimum une version python >= 2.6, mais en raison de l'utilisation de bibliothèque numpy et vpython il faut rester sur une version de python < 3. ubuntu aurait du pouvoir cet environnement de travail, mais le paquet python-visual crée un segfault au chargement... Après un essai sur une debian sid, il a été possible de monter un python-2.5 + python-visual (c'est cette version qui a été utilisée pour le projet de monnomamoi), mais impossible d'avoir une python-2.6 malgré un essai en mode experimental. Un autre essai sur une debian minimaliste, une recompilation de python 2.6, et python-numpy pour cette version de python... mais les sources de vpython trouvés n'ont pas voulu se compiler car il me manquait des entêtes gtltextmm qui ne sont pas installables. De plus, fedora refuse de s'installer dans ma virtualbox, car il ne semble pas gérer le driver du disque virtuel

Le projet étant impossible à tester, la décision suivante a été prise concernant la notation de ce projet.

  • La note concernant le critère Facilité à recréer l'environnement de développement nécessaire au projet est 0
  • Le bénéfice du doute est laissé et la note concernant le fonctionnement du programme est maximale. Nous pensons que Tesing n'aurait pas remis un projet qui ne fonctionne pas. Toutefois, 1 point a été supprimé car il semble en lisant le code que les messages d'erreur en cas de mauvais fichiers ne soit pas suffisamment informatifs.

Cette expérience servira pour le prochain défi et le poid du critère de Facilité à recréer l'environnement de développement nécessaire au projet sera plus élévé.

6-12. Projet de tpoinsot

La solution proposée par tpoinsot peut être téléchargée ici. Il s'agit d'un programme en mode graphique écrit en Java (IDE : netbeans 6.7 et Java sdk 1.6).

Un petit aperçu du programme de tpoinsot
Un petit aperçu du programme de tpoinsot
Critère Détails Commentaires Note
Démonstration Validité de la démonstration textuelle de l'absence de solution du puzzle proposé au paragraphe 4.1. Une démonstration très courte (36 lignes) mais qui demande tout de même un effort de compréhension de la part du lecteur. La démarche tente de placer la pièce Z en prenant en compte la forme des 3 pièces tridimensionnelles A, B et P et en définissant 3 cas différents. La démonstration conclut par l'impossibilitré de résoudre le puzzle. 3/4
       
Documentation Qualité de la documentation accompagnant le projet. Documentation assez limitée (fichier readme), mais algorithme documenté. 2,5/4
       
Analyse du code     3,75/6
  Facilité à comprendre l'organisation des fichiers, classes et objets composant le projet. Les classes ne sont pas des plus clairement séparées, les méthodes parfois un peu longues. 1/2
  Facilité à lire et à comprendre le déroulement du code, pertinence des commentaires. Le code est bien lisible et suffisamment commenté. 1,5/2
  Aération et présentation du code (saut de ligne, indentation, nom des variables et des fonctions), présence ou non de code "barbare" et incompréhensible. Le code est parfois assez lourd à lire, surtout la partie de l'interface graphique. 0,5/1
  Facilité à recréer l'environnement de développement nécessaire au projet. Nécessité de tout recompiler et générer JAR. 0,75/1
       
Fonctionnement du programme     5,5/6
  Capacité du programme à résister à de mauvais paramètres, à de mauvais fichiers de description du puzzle ou à de mauvaises manipulations de l'utilisateur. Ne détecte pas tous les cas de fichiers invalides. 1,5/2
  Capacité du programme à trouver une solution ou à détecter l'absence de solution au puzzle proposé. Trouve extrêmement rapidement une solution (< 100 ms) à tous les puzzles solvables. 4/4
       
Total     14,75/20

7. Récapitulatif des notations

7.1. Synthèse des notes

Le gagnant de ce défi est donc pip1000 et nous le félicitons tous.

8. Conclusion

Sur les 12 projets et bien que cela soit une option, sept possèdent une interface graphique et certaines de ces interfaces sont extérieurement d'excellente qualité.

La page WWW du défi a été consultée 9 052 fois (7 824 consultations uniques) entre le 13 septembre et le 8 novembre 2009. Le post du défi dans le forum a été consulté 16 711 fois sur la même période avec 121 messages postés dans ce post.

Encore une fois, nous tenons à remercier tous les participants à ce défi, les membres du jury et à féliciter notre grand gagnant pip1000.

Nous espérons vous retrouver nombreux pour un prochain défi.