2ème défi C & C++ : Recherche de solution au solitaire

Bonjour à toutes et à tous,

Vous étiez nombreux à attendre l'annonce d'un nouveau défi, le voilà.

Le sujet de ce deuxième défi concerne la recherche de solution au jeu du solitaire. Ce défi commence maintenant (lundi 2 février 2009) et les copies sont ramassées le dimanche 8 mars à minuit.

Pour plus d'information, les différents points d'entrée sont :

• Serveur des défis C & C++
• Les règles générales des défis C & C++
• Les règles particulières de ce défi

Parmi les changements dans ce 2ème défi, on notera :

• Les défis sont aussi ouverts au langage C++ (pas de sectarisme primaire :P)
• Les défis sont ouverts aux modérateurs, rédacteurs et autres responsables du forum. Toutefois, leur classement sera à part et ne donnera pas lieu à un prix (c'est pour le fun uniquement)
• Les défis sont ouverts aux équipes.

Si vous prévoyez de participer au défi, envoyer un petit MP aux organisateurs. Il ne s'agit nullement d'un engagement de votre part mais cela nous permet de composer un jury avec suffisamment de membres en fonction du nombre de challenger prévisibles.

Si vous avez la moindre question concernant ce défi ou si un point du règlement vous parait obscur, il suffit de poster dans la suite de ce message (les questions et les réponses sont publiques).

Bon courage à tous

Bonjour,
Le descriptif du défi mentionne un solitaire triangulaire. Celui ci n'est pas représentable avec la convention donnée (avec "." "x" et " ").
Est-ce intentionnel ?

Citation:

---

Envoyé par Ulmo

Bonjour,
Le descriptif du défi mentionne un solitaire triangulaire. Celui ci n'est pas représentable avec la convention donnée (avec "." "x" et " ").
Est-ce intentionnel ?

---

Le descriptif du défi reprend la page de Wikipédia.

Effectivement, le modèle en triangle n'est pas adaptable au défi courant (de même que d'autres modéles plus exotiques avec des cases hexagonales).

Les seuls modèles utilisables par ce défi sont les modèles de plateau avec des cases carrées.

Citation:

---

Envoyé par Ulmo

Bonjour,
Le descriptif du défi mentionne un solitaire triangulaire. Celui ci n'est pas représentable avec la convention donnée (avec "." "x" et " ").
Est-ce intentionnel ?

---

J'allais justement poser la même question !

Citation:

---

Envoyé par ram-0000

Le descriptif du défi reprend la page de Wikipédia.

Effectivement, le modèle en triangle n'est pas adaptable au défi courant (de même que d'autres modéles plus exotiques avec des cases hexagonales).

Les seuls modèles utilisables par ce défi sont les modèles de plateau avec des cases carrées.

---

Ca va faciliter un peu le problème ça :mouarf:

Est-ce qu'il faut toutes les solutions (l'intitule le laisse penser), ou une solution (la formulation le laisse penser)?

Citation:

---

Envoyé par Jean-Marc.Bourguet

Est-ce qu'il faut toutes les solutions (l'intitule le laisse penser), ou une solution (la formulation le laisse penser)?

---

Pour ce défi, il suffit de trouver une seule solution (certaines configurations de plateau de jeu ont plusieurs milliers de solutions).

Titre du post rectifié.

Règles du défi clarifiées, paragraphe 3.1

Citation:

---

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.

---

Peut-on utiliser Boost.Graph? (dans le sujet, c'est spécifié d'utiliser avec parcimonie les libs externes)

Citation:

---

Envoyé par Trunks

Peut-on utiliser Boost.Graph? (dans le sujet, c'est spécifié d'utiliser avec parcimonie les libs externes)

---

N'oubliez pas que votre programme sera testé et recompilé sur une machine qui ne dispose peut être pas de l'environnement de développement dont vous avez l'habitude. L'usage de librairies externes peut avoir un impact non négligeable sur l'aspect déploiement de la solution.

De plus, le but d'un défi, à la différence de la vraie vie, n'est pas de savoir si vous savez utiliser LA librairie qui implémente l'algorithme de la mort qui tue mais plutôt si vous savez implémenter vous même cet algorithme.

Je dirais donc, dans la mesure du possible, restez classique, ce défi peut être résolu uniquement avec les librairies et les concepts de base.

Et pour compiler, il faut avoir un make ou un projet Visual ? J'imagine qu'utiliser SCons n'est pas recommandé :(

Citation:

---

Envoyé par Matthieu Brucher

Et pour compiler, il faut avoir un make ou un projet Visual ? J'imagine qu'utiliser SCons n'est pas recommandé :(

---

Je viens de lire la doc de SCons que je ne connaissais pas et ce que je lis :

Citation:

---

Envoyé par La documentation SCons

Because SCons is written in Python, you must obviously have Python installed on your system to use SCons. Before you try to install Python, you should check to see if Python is already available on your system by typing python -V (capital 'V') or python --version at your system's command-line prompt.

---

ne m'incite pas à le choisir dans le cadre de ce défi. Attention, je ne dis pas que SCons est mauvais mais je pense que vu la taille du projet final, un portage avec un Makefile ou sous la forme d'un projet Visual Studio me semble plus simple.

Je m'autorise un post en passant, qui n'est pas une question pour une fois:
Le sujet n'a pas l'air évident, bon courage à tous les participants ;)

On peut utiliser tr1/tr2 (pour shared_ptr)?

Citation:

---

Envoyé par Trunks

On peut utiliser tr1/tr2 (pour shared_ptr)?

---

J'avoue ne pas bien comprendre la question. Un petit peu plus d'explications s'il te plait ?

Il s'agit de Technical Reports qui proposent de nouvelles choses qui sont souvent implémentées dans les dernières versions des compilateurs (GCC 4.3, ICC 11, ...).

Citation:

---

Envoyé par Matthieu Brucher

Il s'agit de Technical Reports qui proposent de nouvelles choses qui sont souvent implémentées dans les dernières versions des compilateurs (GCC 4.3, ICC 11, ...).

---

Dans ce cas, j'aurai la même réponse que pour l'usage de la librairie Boost.Graph :

Citation:

---

Envoyé par ram-0000

N'oubliez pas que votre programme sera testé et recompilé sur une machine qui ne dispose peut être pas de l'environnement de développement dont vous avez l'habitude. L'usage de librairies externes peut avoir un impact non négligeable sur l'aspect déploiement de la solution.

De plus, le but d'un défi, à la différence de la vraie vie, n'est pas de savoir si vous savez utiliser LA librairie qui implémente l'algorithme de la mort qui tue mais plutôt si vous savez implémenter vous même cet algorithme.

Je dirais donc, dans la mesure du possible, restez classique, ce défi peut être résolu uniquement avec les librairies et les concepts de base.

---

Il n'est pas possible d'être exhaustif et de dire vous avez le droit d'utiliser ca ca et ca mais pas ca ca et ca. Il y a bien trop de bibliothèques et je ne veux pas brider les gens dans leurs idées.

Maintenant, il faut aussi que les personnes qui participent à ce défi se posent les questions :

• Est ce que ce "machin" est vraiment utile pour ce que je veux faire
• Est ce que c'est standard ou couramment admis/utilisé
• Est ce que le jury risque de l'avoir par défaut
• Est ce que si j'en ai vraiment besoin et que le jury risque de ne pas l'avoir, je peux le réimplémenter facilement
• ...

Je pense que c'est par rapport à la gestion mémoire (pointeurs intelligents). Ca ne pèse pas lourd (qqs en-têtes). Au pire, on les ajoute (c'est ce que je comptais faire de mon côté).

Si c'est C ou C++ windows et linux,
peut être proposer un compilateur commun. Par exemple :
- mingw sous linux
- gcc 4.x sous linux

non?
cela donnerais une base de ce que l'on as droit ou non de base?

Citation:

---

Envoyé par Mongaulois

Si c'est C ou C++ windows et linux,
peut être proposer un compilateur commun. Par exemple :
- mingw sous linux
- gcc 4.x sous linux

non?
cela donnerais une base de ce que l'on as droit ou non de base?

---

Je garde cette excellente idée pour le prochain défi (car il y en aura un). Pour le défi courant, c'est trop tard.

ram-0000, si je ne me suis pas planté, tu as légèrement sous-estimé le nombre de solutions...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

1.02154e+16 ways to reach   .x. ... ....... ....... ....... ... ...   1.02154e+16 ways to reach   ... ... ....... x...... ....... ... ...   4.08616e+16 ways to reach   ... ... ....... ...x... ....... ... ...   1.02154e+16 ways to reach   ... ... ....... ......x ....... ... ...   1.02154e+16 ways to reach   ... ... ....... ....... ....... ... .x.

---

Et j'ai pas assez de mémoire pour les autres plateaux avec mon algo actuel. (Il faudrait passer en 64 bits pour l'utiliser d'ailleurs).

Citation:

---

Envoyé par Jean-Marc.Bourguet

ram-0000, si je ne me suis pas planté, tu as légèrement sous-estimé le nombre de solutions...

---

Juste une remarque, j'espère que tu as bien compris et correctement interprété cette règle particulière du défi

Citation:

---

Envoyé par les règles de ce défi

Le caractère « . » signifie que la case est initialement vide. Il signifie aussi que la dernière bille restante doit être sur cette case pour que la solution soit valide (règle particulière du « Solitaire » pour ce défi).
...
L'exemple suivant montre le contenu d'un fichier permettant de spécifier la forme du plateau de jeu ainsi que la position initiale du premier trou et donc la position finale de la dernière bille devant rester en jeu.

---

dans le paragraphe 3.3. Format du fichier de description du plateau de jeu

De toute façon, le but de ce défi n'est pas de trouver toutes les solutions (et là, je suis d'accord, il peut y en avoir plusieurs suivant la configuration initiale du plateau) mais une solution.