Le jeu du Boogle
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.
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.