3ème défi C & C++ : Découverte du jeu de l'Ane Rouge

Citation:

---

Envoyé par SpiceGuid

Approche originale et solution originale ;)

Je pense aussi que 116 coups c'est à titre indicatif, pour déboguer votre programme c'est mieux si vous avez une limite concrête.


Ça veut dire quoi "effectivement" ?
Avec quel algorithme ?

---

Je ne sais plus qui a dit:

Citation:

---

Une fois écartées toutes les impossibilités, il reste la solution, aussi invraisemblable puisse-t-elle paraitre...

---

(Je me demande si C Doyle n'a pas mis cela dans les levres de Sherlock Holmes :question:)

Le fait est que, d'un point de vue théorique, et quel que soit l'algorithme que tu envisage pour résoudre le problème, tu risque d'écarter toutes les possibilités qui ne te permettent pas d'atteindre l'objectif...

Or, si, de manière théorique, tu en viens à écarter la dernière solution, c'est que tu ne peux pas... trouver de solution correcte ;)

Ce cas, tout théorique, a, il est vrai, fort peu de chances de survenir, mais, "au cas où" il survient, il semble intéressant de faire de manière à ce que l'application te signale gentiment que "aucune solution correcte n'a pu être trouvée" ;)

Citation:

---

Envoyé par diogene

J'ai été tenté de résoudre ce défi (en C) par curiosité (je n'ai pas le droit de concourir :( ).

---

Citation:

---

Envoyé par Les règles des défis C & C++

Les modérateurs, rédacteurs, administrateurs, responsables (enfin toute personnes 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".

---

Il y a 2 classements qui sont établis, celui des "Utilisateurs" et celui des "Responsables DVP". Les seuls personnes qui n'ont pas le droit de concourir sont les membres du jury du défi en cours.

Par contre, ce qui n'est pas indiqué explicitement dans les règles (et qui sera donc mis à jour), c'est que le gagnant dans la catégorie "Responsables DVP" ne gagne rien (mis à par la reconnaissance de ses pairs :P), il concourt pour le fun.

Citation:

---

Envoyé par diogene

Finalement, j'arrive à une solution en 116 coups, après avoir examiné à peu près 24000 configurations (ce qui est finalement assez peu) et utilisé 500kbytes environ d'allocation dynamique de mémoire, en un peu moins de 0.18s (Athlon 32bits 2.2Ghz).

---

Bravo!

@koala01
oui effectivement, sur une petite configuration c'est envisageable.

Ca y est je viens de finir mon petit programme à moi qui crache des solutions ! Ouf ! :D
C'était une grosse debug-party :aie:

Je programme en C, pour l'instant il est tout moche et un bon lot d'optimisation seraient possibles pour l'accélérer...
Mon résultat est bien une solution optimale 116 coups, après une recherche que je pense exhaustive, mais je dois vérifier un truc qui me paraît bizarre à l'exécution. Je ne peux pas encore dire s'il n'y a qu'une unique solution en 116 coups (en éliminant les symétries du plateau de départ), mais maintenant ce serait facile.

Mon petit programme fait 550 lignes à la louche, et n'utilise que les librairies standard du C, c'est donc portable. L'exécutable pèse 30ko, tourne sous Ubuntu Intrepid. La solution est trouvée en 0.2s sur mon portable Core 2 Duo (1 seul thread) à 1.8 GHz, et examine 20 000 configurations avant de tomber sur la solution.
Par contre, pour la consommation mémoire, je sais que ce n'est pas grand-chose mais je ne sais comment faire pour avoir une valeur... Quelqu'un a une idée siou plaît ?

J'ai trouvé 964 solutions (ouf !).
Il ne me reste plus qu'a implémenter la recherche de la plus courte...

EDIT : j'ai 116 coups, comme tout le monde
--
Jérémie
On ne gagne même pas son poids en Carambar ?

Bonjour !

@komput : pour répondre à ta question, j'utilise souvent Valgrind. C'est une suite d'outils qui permet notamment de détecter les fuites mémoire, la consommation de mémoire dans le temps, etc.

@jfouche : 964 cela semble beaucoup non ? Tu comptes les symétries dedans ? En enlevant toutes les symétries je tombe à une dizaine de solutions. Par contre, je n'ai pas encore compté le nombre de déplacement qu'impliquent ces solutions.

@Organisateurs : Que voulez-vous comme sortie ? Un affichage d'une solution, de la plus courte, de toutes les solutions ?

Je ne fais pas partie des organisateurs de ce défis, mais je crois que l'on peut dire que, ce qu'il veulent, c'est minimium une solution(s'il y en a une)

Pour le reste, c'est à toi de justifier dans la doc le fait que tu aie choisi d'afficher la première solution trouvée, la plus rapide, la plus longue ou toutes les variations possibles ;)

Citation:

---

Envoyé par cghengy

@Organisateurs : Que voulez-vous comme sortie ? Un affichage d'une solution, de la plus courte, de toutes les solutions ?

---

Citation:

---

Envoyé par Règles spécifiques du défi §3.1

• Le programme doit utiliser les règles spécifiées dans le paragraphe précédent.
• Le programme doit rechercher et afficher la liste des coups à jouer pour obtenir la solution (ou une des solutions s'il y en a plusieurs) ainsi qu'éventuellement un système de coordonnées permettant de reproduire les coups à jouer.
• S'il n'y a pas de solution, le programme doit le détecter et l'afficher.
• Le programme doit afficher, lorsqu'il a terminé, le temps mis pour trouver la solution ainsi que le nombre de déplacements effectués.
• Le nombre de déplacements à afficher est le nombre de déplacements pour aller le plus directement possible de la position initiale à la position finale. Il ne comprend pas les éventuels errements dûs à la recherche de la solution. De plus, même si une pièces se déplace de 2 cases en un seul mouvement, il faudra tout de même compter 2 déplacements.

---

Clairement, ce qui est demandé, c'est l'affichage d'une seule solution (accompagné peut être du nombre de solutions possibles mais ce n'est pas demandé).

Citation:

---

Envoyé par Critères d'évaluation des programmes §4.2

Fonctionnement du programme (sur 8 points)

• Capacité du programme à résister à un mauvais paramètre ou à un mauvais format de fichier de positions initiales des pièces (sur 1 point)
• Obtention d'une solution valide. C'est le temps d'exécution et le nombre de coups nécessaires pour obtenir la solution qui sont notés. (sur 3 points)
• Affichage de la solution. C'est uniquement l'aspect "esthétique" de la présentation de la solution qui est noté. (sur 3 points)
• Comportement face à une solution impossible (sur 1 point).

---

Comme la notation introduit aussi la notion de solution minimale, autant afficher la solution optimale (celle avec le moins de déplacement) trouvée en un minimum de temps.

En ce qui concerne l'aspect présentation de la solution, il n'y a pas d'indications ni de contraintes afin ne pas brider la fibre esthétique qui est en vous et donc vous pouvez faire ce que vous voulez (avec la console).

Je viens de soumettre mon projet fait en C++.

Bon ben, j'imagine que c'est perdu d'avance, mon programme trouve la solution de l'aneRouge en 9 secondes :aie: en ayant visité au total 12000 plateaux.

Je sais exactement ce qui en est la cause, d'ailleurs, c'est ma recherche d'états successeurs qui est vraiment trop lourde.

Si on a déjà soumis le projet, peux-t-on toujours travailler dessus et le ressoumettre ? :p

Citation:

---

Envoyé par JulienDuSud

Je viens de soumettre mon projet fait en C++.

Bon ben, j'imagine que c'est perdu d'avance, mon programme trouve la solution de l'aneRouge en 9 secondes :aie: en ayant visité au total 12000 plateaux.

---

Cela ne veut pas dire charrette :D

Les critères d'évaluations sont suffisamment souples pour permettre de faire de manière à ce que l'algorithme mis en oeuvre et la manière dont il est mis en oeuvre soit bien plus importants que les performances "brutes" du programme ;)

Entre une politique de codage stricte, des commentaires utiles et intéressants, une documentation cohérente et tant d'autres critères, il y a la place pour palier un éventuel "manque" de perfs;)

Citation:

---

Je sais exactement ce qui en est la cause, d'ailleurs, c'est ma recherche d'états successeurs qui est vraiment trop lourde.

Si on a déjà soumis le projet, peux-t-on toujours travailler dessus et le ressoumettre ? :p

---

Je trouve peut être dommage que tu te sois pressé pour remettre le travail alors que tu avais encore plus de trois semaines devant toi pour le "peaufiner"...

Après tout, la gestion correcte d'un projet passe aussi par le fait de le rendre à temps certes, mais d'utiliser le temps qui nous est imparti pour le réaliser à bon escient... Tu as peut être manqué une occasion à ce point de vue ;)

Je le répète, je n'ai rien à voir dans l'organisation de ce projet, mais, selon moi, il n'y a pas vraiment de raison de t'empêcher de le remanier jusqu'au dernier moment, pour autant que tu choisisse une politique de numérotation de version cohérente...

Par contre, je serais presque d'avis que cela devrait occasionner un certain handicap, évoluant avec le nombre de versions présentées de manière à rester honnête avec ceux qui auront pris la peine de mieux gérer leur temps (et pour t'apprendre pour la prochaine fois que la précipitation ne mène pas à grand chose ;))

Merci pour cette réponse koala01,

Le fait est que j'ai du me précipiter de le remettre car je pars dans 3 jours en vacances et je n'aurais pas le temps de continuer à le peaufiner entre temps :<

Je ne connais pas ma date exacte de retour pour l'instant, mais ça peut aller jusque fin avril, du coup, j'ai préféré participer. Toutes manières, ce n'est pas gagner qui m'intéresse, juste le fait de participer :)

Mais le fait est que tu avais donc encore bien au minimum trois jours devant toi, et que tu aurais pu décider de t'accorder un peu le temps de la vérification ;)

Mais bon, comme je l'ai dit, je n'ai pas le pouvoir de décision là dessus, et il faudra donc attendre que ram-0000 te réponde lui-même ;)

Et je peux parfaitement comprendre que, ne sachant pas si tu aurais encore le temps de le rendre dans les temps alors que tu ne sais pas quand tu rentre, tu aie décidé de le remettre "asap" ;)

Enfin, l'important est effectivement de participer, mais c'est vrai que, tant qu'à faire, autant mettre toutes ses chances de son coté :D

Citation:

---

Envoyé par coyotte507

Sinon on peut arriver à la solution en 6200 coups sans jamais retomber sur la même configuration! oO

---

L'idée est amusante, je vais voir comment trouver efficacement le plus long chemin avant de tomber sur une solution ;)
Mais toutes les solutions sont accessibles en 137 coups maxi. Il y a 8 configurations finales différentes, accessibles au mieux en 116, 118, 135 et 137 coups. Cela correspond à 4 solutions et par symétrie, on a les 4 autres.

Citation:

---

Envoyé par cghengy

@komput : pour répondre à ta question, j'utilise souvent Valgrind. C'est une suite d'outils qui permet notamment de détecter les fuites mémoire, la consommation de mémoire dans le temps, etc.

---

Merci, c'est pas mal ! D'ailleurs, il m'indique que je gère très mal ma mémoire :aie: mais ça je le savais mon petit programme est une bêta de chez bêta.
Sinon je trouve tout en 0.43 seconde, et Valgrind dit que j'ai alloué 9 Mo de mémoire (je n'ai rien libéré jusqu'à la fin, pas besoin).

Je crois que je ne vais plus toucher la partie algo, mais je vais m'occuper de la cosmétique il en a vraiment besoin :roll: et puis il y a un truc que je trouve bizarre dans la recherche, ça marche pas comme je le voudrais... :mur:

Et voilà... quand je disais :mur::mur: ... une modif bidon, et maintenant j'ai bien 964 solutions différentes !!

Citation:

---

Envoyé par jfouche

J'ai trouvé 964 solutions (ouf !).
Il ne me reste plus qu'a implémenter la recherche de la plus courte...

---

Tu as peut-être raison... quant au pourquoi et au comment de cette différence (entre 8 et 964 il y a un gros gros gap) je ne sais pas encore... Mais je ne sais vraiment pas qui a raison !

Citation:

---

Envoyé par jfouche

On ne gagne même pas son poids en Carambar ?

---

Bonne idée ... mais pondéré avec le nombre de solutions trouvées :mrgreen:

Citation:

---

Envoyé par komput

maintenant j'ai bien 964 solutions différentes !!

---

Cool, ou bien on a p'tet raison, on bien on a le même algo foireux ;)

Citation:

---

Envoyé par komput

quant au pourquoi et au comment de cette différence (entre 8 et 964 il y a un gros gros gap) je ne sais pas encore... Mais je ne sais vraiment pas qui a raison !

---

Bah, en fait, j'ai la fleme de tester en vrai...

[EDIT]
Ca y est, le sort en est jeté...
Sources uploadées (ça se dit, en francais ?).
Bonne chance à tous (mais trop quand même :P ).
--
Jérémie

Citation:

---

Envoyé par jfouche

Sources uploadées (ça se dit, en francais ?).

---

Téléchargés peut être alors ?

Citation:

---

Envoyé par ram-0000

Téléchargés peut être alors ?

---

J'aurais vu Téléchargé pour downloadé :D , mais "Google Traduction" te donne raison.
Peut être envoyés...
--
Jérémie, kidoutt

Citation:

---

Envoyé par jfouche

Peut être envoyés...

---

J'aime bien téléverser moi ;)

Après avoir essayé plusieurs optimisations non-triviales (dont certaines n'ont eu aucun effet ou se sont révélées contre-productives) j'ai le sentiment que ma performance actuelle de 23 secondes × Ghz est une sorte d'optimum pour l'approche force brute.
Si quelqu'un ici a essayé l'approche force brute (ou peut très facilement modifier son programme pour essayer cette approche) j'apprécierai qu'il veuille bien communiquer son temps × Ghz ;)

À présent je vais essayer une approche plus fine, histoire de voir lesquelles super-astuces deviennent enfin productive et lesquelles deviennent au contraire à laisser de côté. En espérant que ça me donne des armes pour battre les programmes en C, même si pour le coup je n'y crois pas fort.

En ce qui me concerne : 1 seconde pour la force brute à 1.5 GHz
--
Jérémie