Le jeu du Boogle

Soyez le premier à donner votre avis sur cette source.

Vue 5 582 fois - Téléchargée 871 fois

Description


Le jeu du Boogle


Ce code est le résultat en C# du défis lancé par Pijaku dans cette discussion.

Le Défi


Le but était d'écrire un code trouvant tous les mots possibles en suivant les règles du Boggle, avec une méthode récursive.
Pikaju nous a fourni un fichier texte contenant 323 781 mots.

Deux projets


Suite à l'intervention de CarlVb, un deuxième projet est né, avec un dictionnaire sous forme d'arbre.
Les deux projets sont présents dans le zip. Le second est jouable.
La description ci dessous est celle du premier projet, pour rester en lien avec le tutoriel

Description des Classes

Dico


Cette classe permet le chargement du fichier texte, dont le chemin est passé en paramètre. Elle retourne une collection de string composée de tous les mots du fichiers.

Le premier fichier fourni par Pijaku contenait des lettres avec leurs signes diacritiques (accents, cédilles, etc.), la classe possède donc une méthode pour s'en affranchir. Bien qu'elle ne soit plus utile, je l'ai laissée pour la postérité.

De


Cette classe représente un dé.
Elle permet le tirage aléatoire d'une face.
Elle possède les coordonnées du dé dans la grille de jeu.
L'index du dé dans la collection représentant cette grille.

Une méthode retourne la collection de dés adjacents, en fonction des coordonnées, en ôtant les dés de chemins déjà explorés.

Chemin


Contient un chemin unique de dé, retourne le texte constitué.
Cette classe est clonable, de façon a créer autant de «sous chemins» avec les dés adjacents au dé en cours que nécessaire.

Resultat


Permet l'affichage par colonne selon le nombre de lettres des mots trouvés.

DecompteMots


Permet le calcul des points.

Tirage


Classe qui effectue le tirage de la grille et la recherche des mots.

Tirage de la grille


Les 16 dés sont placés dans une collection «disponibles».
Le processus choisit aléatoirement un dé disponible, par position dans la grille.
Ce dé est lancé de façon à obtenir la face visible, les coordonnées et l'index sont saisis, il est ensuite déplacé vers la collection «tirés».
Recherche des Mots


Choix du type de collection et des outils de recherche.

L'évaluation différée des requêtes Linq dans le cas d'une méthode récursive telle que celle utilisée n'engendre que le désarroi, quand l'évaluation s'exécute dans l'instance recursive suivante.
J'ai donc opté pour des List<T> en grand majorité.
J'ai constaté que
List<T> mesMots = monDico.Where(c => c.StartWith(«A»)).ToList<string>();

s'exécute plus lentement que
List<T> mesMots = monDico.FindAll(c => c.StartWith(«A»));

Première phase de recherche

En premier lieu, on restreint le dictionnaire au seuls mots formés uniquement avec des lettres du tirage. Une boucle foreach parcourt les dés de la grille.
Chaque dé initie un chemin, le dictionnaire est réduit aux mots commençant par ce chemin.

Le chemin et le dictionnaire ainsi réduit sont passés en paramètre à la méthode récursive.
La Méthode Récursive

La méthode parcoure l'ensemble des dés adjacents qui n'ont pas déjà été utilisés dans le chemin «père».
S'il n'y en a aucun, ce chemin s'arrête et on retourne à l'appel précédent.

Pour chaque dés adjacent, le chemin est cloné, le dé est ajouté au clone.
Le dictionnaire est réduit aux mots commençant par cette séquence.
Si le chemin fait plus de trois lettres, on regarde s'il constitue un mot.
S'il reste des mots dans le dictionnaire, alors le clone et la nouvelle réduction du chemin sont envoyé en paramètre d'un nouvel appel de cette méthode.

Et ainsi de suite jusqu'à l'obtention de la totalité des mots de la grille.
Multithread?

La question de savoir si le mulitithread apporterait un gain de temps s'est posée.
Trois options sont présentes dans le code, sans, 2 threads de recherches, 4 threads de recherche.
Il suufit de commenter les options que l'on ne veut pas tester.

Les Formulaires


Form1, affiche le tirage sur des labels, les mots dans un datagridview, et les métadonnées sur des labels.

Si l'on sélectionne un mot dans ce le datagridview, il se colore dans la grille du tirage.

Un bouton permet un nouveau tirage.

Le menu Fichier/Export en CSV, permet l'export du tirage et des résultats pour les comparer avec mes compagnons de jeu.

Le menu Fichier/Saisir une grille permet l'affichage d'un autre formulaire à partir duquel on peut forcer un tirage, essayez avec RDIEUIANOSSTSABA.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

vb95
Messages postés
2079
Date d'inscription
samedi 11 janvier 2014
Statut
Contributeur
Dernière intervention
24 février 2020
86
super comme source !
beau travail d'équipe
Whismeril
Messages postés
14265
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
25 février 2020
346 > vb95
Messages postés
2079
Date d'inscription
samedi 11 janvier 2014
Statut
Contributeur
Dernière intervention
24 février 2020

Merci
pijaku
Messages postés
12261
Date d'inscription
jeudi 15 mai 2008
Statut
Modérateur
Dernière intervention
19 février 2020
9
Bonjour,

A noté.
Whismeril
Messages postés
14265
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
25 février 2020
346
MAJ, ajout du projet avec le dictionnaire sous forme d'arbre.
Ce projet est jouable.
Tous les chemins sont affichés, mais les mots en doubles ne sont compté qu'une fois pour les points.
Le joueurs peut afficher toutes les solutions, les mots qu'il a trouvés sont coloré en bleu clair.
La sélection d'un mot dans la grille de résultats colore les dé dans le tirage.
Le joueur peut ajouter un mot au dictionnaire.
carlvb
Messages postés
199
Date d'inscription
mercredi 23 avril 2003
Statut
Contributeur
Dernière intervention
25 mai 2017
3 > Whismeril
Messages postés
14265
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
25 février 2020

Salut Whis,

C'est peut-être une erreur chez moi mais le zip ne semble contenir que l'ancienne version datée du 14/03.

A plus tard.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.