Retour
Les Pentaminos
Rappel du problème paru dans le
Virus 13 :
|
Vous avez déjà entendu parler des pentaminos ? Ce sont les petites pièces que l'on peut former avec 5 petits carrés (un carré ayant toujours au moins une face en contact avec un autre). En tout il y en a 12 différents (aux symétries et rotations prêts) que l'on désigne par la lettre de l'alphabet doint il se rapproche le plus. Le but du jeux est d'agencer ces petits pentaminos pour former des rectangles de différentes tailles (3x20, 4x15, 5x12 ou 6x10). |
Une solution théorique a été proposée dans le Virus 14. A cette occasion, nous vous invitions à proposer vos programmes capables de trouver tous les solutions (aux symétries prêtes) pour différentes tailles de rectangle (3x20, 4x15, 5x12 et 6x10).
Maintenant les participations sont closes, et vous trouverez ci-dessous les solutions retenues classées par temps d'exécution décroissant (" signifie seconde et ' minute). Tous les programmes ont été recompilés de la même façon pour la mesure.
Bien que ce problème soit clos, vous pouvez toujours envoyer vos remarques et vos questions à David.
Le grand gagnant est donc Terje Mathisen dont le programme avait déjà gagné un concours (d'après Jean-Charles Meyrignac).
Voici la réponse à quelques questions souvent posées :
- Il faut faire un et un seul programme qui soit capable de trouver toutes (aux symétries prêtes) les solutions pour (au moins) les 4 rectangles de 60 cases.
- Eliminer les solutions symétriques n'est pas obligatoire mais recommandé (ne serait-ce que parce que ça peut accélérer le programme en réduisant le champ d'étude).
- Le programme doit être aussi portable que possible (éviter les fioritures d'affichage, ...).
Si vous avez écrit un programme et que vous vous demandez
s'il est correct, voici le nombre de solutions qu'il doit trouver :
Rectangle |
Sans |
Avec |
3x20 |
2 |
8 |
4x15 |
368 |
1472 |
5x12 |
1010 |
4040 |
6x10 |
2339 |
9356 |
Auteur |
Langage |
Linux |
Commentaire |
|
C |
3x20 |
0"03 |
Merci à Jean-Charles Meyrignac qui a retrouvé ce programme sur Simtel.net. Le code est un parfait compromis entre clarté et efficacité. Il s'est montré le plus rapide tout en étant parfaitement portable. Mais en sacrifiant la portabilité, on peut l'accélérer encore plus : des routines en assembleur peuvent-être utilisée à la place du C en initialisant USE_ASM à 1. |
|
4x15 |
0"25 |
|||
5x12 |
1"23 |
|||
6x10 |
2"93 |
|||
C |
3x20 |
0"05 |
Le source C n'est pas directement portable (prévu pour DOS), néanmoins l'adaptation n'est pas très compliquée. Le code est diablement efficace, même si la clarté est loin d'être au rendez-vous. |
|
4x15 |
0"75 |
|||
5x12 |
2"71 |
|||
6x10 |
6"71 |
|||
C |
3x20 |
0"05 |
Non seulement le code est impeccable et le programme très souple d'utilisation, mais en plus ça décoiffe pas mal au niveau vitesse ! Seul point négatif : l'option pour éliminer les symétries n'est pas au point. |
|
4x15 |
0"93 |
|||
5x12 |
4"42 |
|||
6x10 |
9"74 |
|||
CWEB |
3x20 |
0"15 |
Ce programme résoud aussi le problème pour les assemblages en 3D ! Vous trouverez ici le source C correspondant, et une version Java sur le site de l'auteur. |
|
4x15 |
2"18 |
|||
5x12 |
9"38 |
|||
6x10 |
27"44 |
|||
C |
3x20 |
0"09 |
Le code est clair, net et le résultat relativement rapide. |
|
4x15 |
3"88 |
|||
5x12 |
15"59 |
|||
6x10 |
30"24 |
|||
(temps mesurés sur un K6-233 avec 64 Mo de RAM)
CWEB : c'est un système qui permet d'intégrer du TeX au langage C pour faciliter la documentation des programmes. La version d'origine (WEB), qui fonctionnait avec le langage Pascal, est l'oeuvre de Donald E. Knuth, l'auteur de TeX. Le passage au langage C a été fait en 1987 par Silvio Levy. Un fichier CWEB (généralement avec l'extension ".w") est utilisable à travers deux moulinettes : ctangle qui permet de générer le source en C, et cweave qui donne un fichier TeX.