Adaptations de l'énoncé du défi le 4 mai à 17h50.

Bonjour à tous!

Après le défi sur la création d'un algorithme de génération de termes de la suite de Conway, nous allons maintenant nous attaquer aux labyrinthes! (sans nous perdre bien sur...)

Les labyrinthes?

Je suppose que vous connaissez tous le principe de ce jeu, mais je le rappelle quand même, pour les moins dégourdis


Avec cette définition très simple, voici un petit exemple imagé (le point de départ est en vert et l'arrivée en rouge).


Le but de ce défi est en soi assez simple: vous devez créer un script php qui va générer aléatoirement des grilles de labyrinthe, qui va être capable de trouver la solution de celles-ci, si elle existe (eh oui, il se peut qu'un labyrinthe soit insoluble!), et qui pourra afficher tout ca dans le navigateur.

Voici donc les consignes de ce défi

Ce défi comporte deux parties: la génération et la solution du labyrinthe. Votre script devra clairement séparer ces deux options (deux fonctions ou deux classes distinctes par exemple). Vous n'êtes bien sur pas obligés de réaliser la deuxième partie, qui est plus compliquée que la première, mais si vous le faites, vous serez bien évidemment mieux cotés!
Il faudra impérativement ajouter une troisième fonctionnalité: l'affichage des grilles (résolues ou non).
Vous devez pouvoir générer, résoudre et afficher des grilles de toutes tailles (pas nécessairement carrées).
Il serait évidemment mieux que vous génériez des labyrinthes parfaits (au moins une méthode), mais si pour tester votre algorithme de résolution vous faites des techniques de création de labyrinthes plus exotiques, ca peut aller aussi. L'algorithme de résolution doit quant à lui, dans l'idéal, prendre le chemin le plus court.

Voici les critères sur lesquels vous serez cotés:

• La clarté du script (bien commenté, bien indenté, pas de chichis inutiles, ...)
• L'opérationalité du script (si ca fonctionne pas, c'est moins bien! )
• L'algorithme utilisé et son efficacité (pour cela, on testera les deux parties sur des grilles de tailles différentes: une grille 10*10 et une grille 100*100 par exemple). Si vous générez des grilles tout le temps solubles, et que vous les résolvez en trouvant le chemin le plus court en un temps infime, c'est mieux que si votre grille ne ressemble à rien et que vous faites trois détours dans votre solution, le tout prenant un temps astronomique!
• L'aspect esthétique des grilles affichées et des solutions

Vous pouvez utiliser autant de fichiers que vous voulez, mais vous devez avoir un fichier index.php qui fait une démonstration de votre script (qui génère une grille de test, l'affiche, la résoud et affiche la grille résolue par exemple), et qui contient tous les commentaires que vous jugez utiles pour notre compréhension de votre bébé.


Voici donc la grille de correction qui sera utilisée (au niveau des points):

• 3 points pour l'originalité du script, le design, la facilité d'utilisation, les petits plus qui ne sont pas dans les autres scripts.
• 3 points pour le code, sa qualité, sa lisibilité et sa clarté, l'utilisation cohérente de php, l'utilisation des classes, fonctions à bon escient. Utilisez les commentaires pour qu'on puisse facilement comprendre votre code.
• 5 points pour la partie génération du labyrinthe.
• 5 points pour la partie résolution du labyrinthe.
• 4 points pour la partie représentation du labyrinthe.

Les trois dernières catégories auront les mêmes critères de notation, à savoir l'optimisation et l'efficacité de vos méthodes, la qualité de leurs implémentations et leur nombre (mais n'en faites pas nécessairement 15!). Une attention particulière sera aussi faite sur le choix cohérent et logique des structures de données les plus adaptées aux problèmes posés (tableau, arbre, graphe, pile, file... en fonction de ce qu'on fait).



Il faut remettre le tout dans une archive .zip ou .tar.gz nommée [DefiLaby]VotrePseudo sur l'adresse mjasienski[at]gmail[dot]com avant le 30 Juin 2007 à 23h59, en mettre comme objet [DefiLaby]VotrePseudo.
Vous avez pas mal de temps car ce n'est pas si facile que ca, et que certains vont bientot être en examens!

Quelques conseils

• Vous trouverez sur Wikipedia deux algorithmes de génération de labyrinthes. Ils vous suffiront pour la génération des grilles (choisissez-en un des deux, ou implémentez les deux, c'est au choix).
• Pour la solution d'un labyrinthe, pensez en termes de 'chemins possibles'. Vous pouvez les stocker dans des structures de données telles que des arbres (là, c'est le top du top!) ou des tableaux.
• L'affichage peut se faire en html ou par images générées par GD (là encore, ce serait le top!)
• Le choix de la structure de données pour enregistrer le labyrinthe est tout à fait libre. L'exemple donné dans ce premier message est là pour vous donner une idée si vous êtes à court, mais ce n'est peut-être pas le plus efficace.
• J'insiste encore une fois sur le fait que les 3 parties du défi doivent clairement être séparées. ON NE PEUT PAS générer et résoudre dans une même fonction. Ces deux tâches doivent être tout à fait indépendantes.
• Il est interdit de laisser vos sources dans ce sujet. C'est un défi, laissez tout le monde participer sur un même pied d'égalité.

Bon courage à tous!

Martin (en accord avec winzou)

(edit winzou : modif date)

Trop compliqué ton truc, en plus interdire php5, ça commence à devenir de plus en plus aberrant c't'histoire ....

Je comprend vraiment pas pourquoi vouloir toujours utiliser autre chose que la dernière version de php

En plus s'il faut s'attarder sur le design des grilles générées, ce n'est plus un défi php pur.

Il est vrai que restreindre à PHP4 était un peu ridicule... J'ai donc modifié l'énoncé.
Par contre, pour le 'design' des grilles, c'est simplement pour éviter d'avoir des trucs complètement farfelus et illisibles. Je ne demande pas non plus d'avoir un truc hyper beau, mais simplement sobre et bien lisible.

Il est vrai que c'est un défi un peu compliqué, mais pas tant que ca. Si c'était trop simple, ce ne serait plus un défi. C'est un problème d'algorithmique intéressant, et la partie 'Génération' de grilles est relativement facile car l'algo est donné sur wikipedia. Le seul truc 'dur', c'est la solution des grilles. Là, il faudra faire preuve d'un peu d'imagination ou de logique.
Mon script de test fait moins de 300 lignes et fait tout ce qui est demandé, c'est donc pas si long que ca non plus...

oula, mais c'est franchement trop farfelu ton truc, jamais personne ne se lancera là dedans...

Moi je trouve ça plutôt fun
Si je trouve le temps je le ferais, d'ici le 31 juillet ca doit être faisable.

C'est du classique, mais c'est très intéressant, d'habitude on fait plus ca en C, par exemple les graphes et cie.

Je participe : c'est les vacances et j'ai du temps libre.

Si j'ai du temps libre je vais peut etre faire la 1ère partit mais la seconde je ne vois pas comment la faire.

Qu'est-ce que PHP5 a de plus que PHP4?

yahou!!!
Mon idée à portée ces fruits!!
(bon ok on avait eu plus ou moins en même temps la même avec winzou)
Je participe!!!!!

Bon j'ai commencé le script fusion j'ai des petit labyrinthe mais j'ai quelques problèmes :S

Citation : The French

Qu'est-ce que PHP5 a de plus que PHP4?

PHP 5 est plus rapide, et il y a quelques fonctions intéressantes en plus et surtout des librairies (qui ne nous seront pas utiles dans ce défi).

Mwais... Bof, je participe pas (pas le temps en plus), ca m'interesse pas
(J'imagine qu'il faut utiliser GD et un coup de génération de nombre aléatoire dans le tas...)

Helo les zer. heu les fous.
hou la la il y a des fou qui releve se defi. Perso sa parait dure et sa rapporte rien a par de l' auto satisfaction c'est deja pas mal.
En php ???
Faudra aficher les solutions car moi pas l'ombre d'une ombre d' idée.
MERCI

Alors, afficher le spectre de fichiers .wav, joindre 2 fichiers .wav, résoudre un sudoku ca ne vous fait pas peur (défis précédents).
Et là résoudre un labyrinthe, ca vous effraie ? C'est plus simple pourtant...

Et ca t'appoorte aussi de l'expérience....
Après avoir vu le truc sur wikipedia, on a, en effet, pas forcemment besoin de GD.
Les olutions, ben, ca dépend qui gagne

hum j'aurais préféré en C, mais c'est pas grave
J'ai déja bien avancée mon script de génération par fusion. Sinon la résolution me semble plus facile.
Par contre j'ai bien un problème : je dessine un labyrinthe mais ou placé le départ / arrivée ?
forcément haut-gauche vers bas-droite ?

Bon, j'ai bien envie de concourir, mais plutôt hors-concours (on a pas le droit, tant pis !)

Parce que j'ai bien envie de faire un truc vraiment costaud , avec utilisation :

• Des classes en PHP5
• Du design pattern Strategy -> Pour utiliser plusieurs algorithmes
• -> Plusieurs algorithmes de génération
• -> Plusieurs algorithmes de résolution
• Du design pattern Factory -> pour avoir plusieurs formats de sortie
• -> Format (X)HTML
• -> Format XML ? (je sais pas, je suis pas motivé par celui-là en fait ^^)
• -> Format gif/png/jpg classique
• -> Format gif animé qui dessine la solution jusqu'à l'arrivé

Bref, j'ai envie de m'amuser un peu

[edit] Sinon pour Arnaud : oui, tu peux mettre le départ en haut à gauche et l'arrivée en bas à droite, mais c'est toi qui choisit la convention je pense... Tu peux toujours les mettre en haut à droite et en bas à gauche, voire du milieu-bas à en haut à droite (mais dans ce dernier cas, les risques de solutions "simplistes" sont plus grands !)

Au départ j'avais fait l'affichage en div ou en tableaux, mais c'était pas super joli car les border se gèrent pas comme on veut. J'ai donc fait une version GD qui rend bcp mieux, mais c'est pas indispensable de faire comme ca
L'étape la plus lourde en calculs est évidemment la solution du labyrinthe. Essayez d'optimiser un max à ce niveau là!
On peut prendre comme convention que le départ est au dessus à gauche et l'arrivée en bas à droite. Ca change pas grand chose au défi! Je l'ajoute dans le premier message.

Un lien vers ton script K-jasi ?

Et les sources aussi?

Pffffooouu J'ai essayé, c'est très chaud ! Moi les murs sortent du tableau !
Je laisse tomber car je n'ais pas le temps !

A+ et bonne chance pour les autres !

Je pense que je vais essayer ! Je vais commencer par coder les fonctions d'affichage, et le reste devrait se passer sans problème, une fois qu'il y a la visualisation

Citation : K-jasi

Et les sources aussi?

Mais non juste pour l'exemple

EDIT :

Mouahahaha : V1

Bon j'ai un peu merdé entre les abscisses ordonnées, j'ai perdu un temps fou ! et il gère pas les rectangle (juste une erreur de script que je vais corriger)

bench : environ 1 sec pour 20*20, 400 cases. (pas optimisé il est tout frais)

Version GD pour bientôt.

Pour l'instant mon algo (le deuxime sur wikipédia) met environ 0.3 secondes pour générer un labyrinthe de 100*100 cases avec php 5.2.1 sur un Athlon 64 X2 3800+ (on peut pas comparer sinon ^^).

Merci K-jasi !
Epinglé

Je pense que je vais participer si j'ai le temps, ça a l'air intéressant ;).

J'ai codé la génération par image, il me manque encore tout : génération du labyrinthe, et de la solution... Je penserai tout ça demain dans le train, ça va être du plaisir !


Je pense utiliser le deuxième algorithme présenté sur wikipédia, qui me semble plus adapté pour le PHP !

Je sens que je vais imprimer quelques un de mes labyrinthe pour m'occuper pendant les cours de philo

=> sort

Si vous voulez mon exemple:
http://mjasienski.celeonet.fr/misc/labyrinthe.php

J'ai utilisé la fusion des chemins, et GD pour la représentation. Pour la résolution (ce qui prend le plus de temps dans le temps d'exec), il y a surement moyen de faire mieux (utiliser des structures de données plus adaptées).

Moi j'utilise le premier algo, je vais essayer de l'optimiser car il est assez lent.
Sinon voici le lien avec GD : http://php.vosmaps.fr/php/gen.fusion.class.php

Les premières ébauches arrivent déjà, il va y avoir du challenge, c'est cool