Comment nous avons perdu 230 euros chez CJ Affiliate (Conversant)

[accueil]  [menu]  [marions-nous !]  [chercher]


1999-07-05 00:00

Concours : les Pentaminos



Rappel du problème paru dans le Virus 13 :

Les Pentaminos

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 :

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
symétries

Avec
symétries

3x20

2

8

4x15

368

1472

5x12

1010

4040

6x10

2339

9356


Auteur

Langage

Linux

Commentaire

Terje Mathisen

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

Patrice Torchet

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

Sylvain Lhullier

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

Bruno Gilleta

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

Alain De Cesare

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.





Vous aimez cette page ? Partagez-en le lien !

Facebook
Twitter
Google+
LinkedIn
Reddit


[homepage] [RSS] [archives]
[contact & legal & cookies] [since 1997]