bon ba voila un défi intéressant, je me lance

Espérons que ce défi n'aura pas le même sort que le dernier qui s'était achevé pendant un mois de juillet... C'est-à-dire une non correction (L'aide aux malvoyants)

Ce défi pour les labyrinthes, je l'avais fait en cours (en Caml) c'était sympa à faire. Je pense qu'après mes concours, je m'y mettrais.

Par contre, est-ce possible de définir un peu mieux la matrice de départ ? Ou alors on fait comme on veut ?

Citation : K-jasi

qui contiendra dans chacune de ses cases deux valeurs booléennes, pour déterminer si l'on peut ou non aller vers la droite ou vers le bas de cette case

Ca ne me paraît pas bien clair, comment avec ceci, tu codes le fait que tu ne puisses pas aller en haut ou en bas

Dans la mesure où tu génères toi même ton Labyrinthe, libre à toi de définir ta matrice comme tu veux.

On ne peut pas aller en haut si la case du dessus est fermé en bas

Je bloque sur ces trucs justement... Mais j'ai une petite idée
(Je participe hors concours hein)

Pour vous mieux vaut privilégier l'optimisation ou la sécurité et sa gestion d'erreur ?

Si tu veux mon avis, quand tu génères un laby de 40*40 et que tu trouves sa solution, le temps d'éxécution pour la gestion d'erreurs et la sécurité est négligeable (le tout étant que tes algorithmes soient cohérents)

Interdiction totale de participer en "hors-concours". C'est trop bête, rendez votre script vous pourrez vous comparer aux autres et avoir une correction adaptée !

Par contre j'avais pas vu la date de fin, c'est beaucoup trop long. D'autres défis / concours / whatever attendent, surtout en été. Je rapproche l'échéance au 30 Juin. Si c'est vraiment trop court on verra (soyons flexible), mais pour l'instant c'est le 30 Juin Ca laisse 2 mois et demi c'est quand même pas mal.

PAr hors concours, ca veut dire que je le rends pas
Car GD cay pas mon truc, et que là je galère rien que pour générer le labyrinthe. Je le rendrais si j'arrive à totu boucler à temps (ce qu m'etonnerait... Peut-être que vers mi juin, je m'y remettrais)

C'est pas très compliqué la génération mais moi ca prend un temps fou !

Arnaud > Au vu du nom de ton fichier (bah j'observe ^^), tu as pris la première méthode via une un objet, non ?

Citation : Talus

Arnaud > Au vu du nom de ton fichier (bah j'observe ^^), tu as pris la première méthode via une un objet, non ?

Non il n'y a pas d'objet une simple fonction et une autre pour l'affichage.

Allez je me lance dans ce défi.

Salut à tous amis des défis !

J'ai fini de coder la génération du labyrinthe...

Alors que je suis à environ 120ms pour un 10*10 sur intel P4 2,4gHz, je me retrouve à 10s sur un 30*30 et à 30s sur un 40*40...

Vous avez quoi sur les gros formats comme temps ?

Environ 0.8s pour la génération
L'affichage ca prend au moins 0.02s...
La résolution, pas tout à fait finie, mais il semblerait que ca prenne moins de 0.05s...
Conclusion : ce qui prend le plus de temps et ce sur quoi je vais travailler dur, c'est la génération


[edit] Pentium 4 C 2.4Ghz + Zend_optimiser

Citation : flobard

Vous avez quoi sur les gros formats comme temps ?

Labyrinthe généré en 0.177948951721 seconde(s)
Solution générée en 0.0341620445251 seconde(s)
Image générée en 0.196769952774 seconde(s)

Pour un 100*100
Seul l'algo de génération est optimisé.

EDIT : Athlon 64 X2 3800+ 2 Ghz

En fait, rien.

Ouf, j'ai analysé le problème en me douchant matin (oui, je pense à vous même tôt le matin)... J'ai fait une première vague d'optimisation qui me donne du 3s en 40*40, mais c'est vraiment qu'une rapide optimisation ! Je devrais passer en dessous de la seconde, si tout va bien

Cette après midi je vais bien retoucher la génération, pour avoir un truc propre, commenté, rapide, et je me mettrais à la solution plus tard

Vous vous êtes servi d'une fonction récursive pour générer le labyrinthe ?

Car je viens de tester de cette façon, et à partir de 27 de côté, je n'ai plus d'affichage, je dois certainement dépassé la limite pour la pile d'appel...

En 25*25 je suis à 0.3~

Moi je n'utilise pas de pile d'appel... A vrai dire, je ne sais pas ce que c'est !

Bonne nouvelle, des 90 secondes en 100*100 je suis passé à 0.8392720 secondes. La plus grosse partie de l'optimisation est terminée, maintenant on va piocher les milisecondes, mais c'est toujours bon de le faire

Hmm, je code tous les algorithmes que je trouve et au final ça varie de 250s à 0.05s pour la génération de labyrinthe. C'est abbusé

Moi j'ai fait une pile, car en générale, la récursivité, c'est pas super. En plus, php gère la mémoire à notre place, alors pourquoi pas s'en priver !!!

Juste pour info... C'est quoi une pile (avec des mots simples) ?


Je n'ai pas vraiment utilisé de récursivité dans mon script !

Premier coup, je prend une case au hasard... Je regarde aux alentours les cases possibles (non-visitées et existantes), si il y en a plus de deux, j'enregistre pour revenir en arrière, j'en prend une dans celles possibles, et je continue comme ça... Je sais pas si on peut vraiment appeler ça de la récursivité !

Une pile est une structure de donnée.
Voit ça comme une pile de livre. Tu ajoutes des éléments au sommet, et tu récupére toujours celui en haut de la pile (le dernier ajouté donc).

Tiens : http://www.siteduzero.com/tuto-3-16237-1-les-piles-les-files-en-langage-c.html . C'est un tuto pour du c, mais c'est grossièrement la même chose.

Vous avez pris de l'avance, moi je fait dans les 5 sec sur du 45*45

Je propose, pour les bench on se base sur du 45*45

J'ai pas optimisé..

Sinon un algo qui fait n'importe quoi (rarement des laby resolvable) donne moins de la seconde pour 100*100...

Je vais continuer.

Le 45*45 ça me va aussi ! Voici mes temps sur un P4 2,4GHz, avec des cases de 10px de côté (pour gd) :
Generation du labyrinthe en 0.1010191 secondes
Génération de l'image en 0.0295510 secondes

Je pense être au maximum niveau optimisation sur mon script...



Par contre j'ai vraiment aucune idée pour trouver la solution ! Je sens que je vais me faire chier

bin moi j'en suis encore à chercher comment organiser ma matrice
Pour ceux que ça intéresse, le nombre de portes interne au labyrinthe :

Voila, c'était le truc bien nul qui servait à rien mais ça ma fait marré de le calculer pour savoir à l'avance la taille de ma matrice

Moi ca me sert tes formules

Citation : flobard

Par contre j'ai vraiment aucune idée pour trouver la solution ! Je sens que je vais me faire chier

Des pistes de réfléxions :

• Résolution par la méthode de A* (lien)
• Résolution par la méthode de Dijkstra (lien)
• Résolution par la méthode de Ford-Bellman (lien)
• Résolution par la méthode de Danteig-Ford (lien)
• Résolution par la méthode de la main droite
• Résolution par la méthode de la main gauche
• Résolution par le hasard totale
• EDIT² : Résolution par la méthode de parcours en largeur (lien)
• EDIT² : Résolution par la méthode de parcours en profondeur(lien)

EDIT : Bench avec les paramètres de flobard me donne au final : 0.0933380127 secondes pour la génération du labyrinthe + image

Moi je suis à la ramasse avec mes 4,434 secondes pour le 45x45
(AMD athlon 64 3500+ @ 2.2 GHz)

Si quelqu'un veut de l'aide pour optimiser son script je veux bien l'aider (mais je crois que je vais pas continuer mon script vu le temps qu'il prend )