Donnez votre avis

Exemple de méthode récursive: la résolution d'une grille de Boogle

Posez votre question

Exemple de méthode récursive: la résolution d'une grille de Boogle


Suite au défi lancé par Pijaku dans cette discussion, j'ai posté un code fonctionnel en C# ici.


Ce tutoriel a pour objectif de s'appuyer sur ce code pour décrire l'utilisation d'une méthode récursive.

Éléments en présence

Le dictionnaire


Nous disposons d'une List<string> de 323 781 mots.
Cette liste est issue d'un fichier texte, séparé par des points-virgules, fourni par Pijaku dans la discussion en référence.


Pikaju nous a mis quelques petits pièges dans le fichier, en effet chaque ligne se termine par un ; et il y a une ligne vide entre chaque ligne de mots.
Ce n'est qu'assez tard dans le développement que je me suis aperçu que ce formatage posait un problème lors de l'import. Le premier mot de chaque ligne se trouvait concaténé avec un retour de ligne (\r\nANNIVERSAIRE par exemple). D'ou coup ces mots n'étaient pas trouvables par la recherche récursive.

J'ai résolu ce point en chargeant le fichier d'un coup et en remplaçant tous les retours de ligne par une chaine vide. Le string ainsi constitué est donc composé uniquement de mots séparés par des ;. Un split permet de créer la collection de mots. j'utiliser Except (méthode d'extension issue de Linq) pour enlever les chaines vides restantes, dont, au moins, la dernière entrée de la liste. 
       /// <summary>
        /// Ouvre le nouveau dictionnaire fourni par Pijaku, celui ci est présenté au format csv.
        /// Cependant notre ami nous a mis quelques pièges, le dernier mot de chaque ligne est suivi d'un ; et il y a une ligne vide entre deux lignes de mots
        /// Un simple split sur les ; et les \r\n ne donc suffit pas
        /// </summary>
        /// <param name="path"></param>
        /// <returns></returns>
        public void Ouvrir(string path)
        {
            char[] separateurs = { ';' };//le split se fera juste sur les ;

            //je charge tout le fichier dans RedAllText, supprime les retours de lignes avec Replace, Splite, et enlève les eventuelles chaines vides avec Except
            //Dico est une List pour que la requete soit executée aussitôt.
            dico = File.ReadAllText(path, Encoding.ASCII).Replace("\r\n","").Split(separateurs).Except(new [] {""}).ToList<string>();
        }

Linq ou pas?


Ma première idée a été de profiter de la puissance et de la rapidité d'exécution des requêtes Linq, et des collections associées IEnumerable<T>.
Cependant c'était sans compter l'évaluation différée des requêtes qui 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é sur ma machine, 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»));

Pour être exact la recherche par Where va plus vite que celle par FindAll, mais le cast en List<string> plombe le temps d'exécution.
Donc à Where, j'ai préféré FindAll et à Any, j'ai préféré Exist.

La grille de jeu


Au moment de la recherche, le tirage est déjà effectué.
Ce tirage est représenté par une List<De> appelée «tires».
Pour l'exemple nous allons travailler sur cette grille.

Principe de la recherche


L'algorithme doit parcourir la grille, y extraire tous les chemins possibles (environ 12 millions de 1 à 16 lettres!), et chercher dans le dictionnaire si le chemin représente un mot connu.

Commençons par enlever du dictionnaire tous les mots contenant au moins une lettre qui n'apparait pas dans la liste.
Il faut constituer la collection des lettres non tirées, la requête étant évaluée aussitôt, je ne cast pas.
Une expression régulière est élaborée pour accepter un mot contenant tout sauf au moins une lettre de la collection.
Une requette FindAll, sur les mots validés par la Regex est effectuée. 
            //première réduction du dico avec seulement les lettres tirées sur suggetion de Ucfoutu, utilisation de regex
            string[] alphabet = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
            var lettres = alphabet.Except(tires.Select(c => c.FaceVisible).Distinct());//liste des lettres non tirées
            Regex maRegex = new Regex(string.Format("^[^{0}]+$",string.Join("",lettres)));
            List<string> dicoExclu = MonDico.Liste.FindAll(c => maRegex.IsMatch(c));

Cette réduction permet un gain de temps considérable pour deux raisons:
-dans notre exemple, il ne reste plus que 27 427 mots, donc les requêtes suivante seront exécutées plus rapidement.
-A chaque étape, on vérifie qu'il existe des mots commençant par le chemin en cours, plus le dictionnaire est restreint plus vite un chemin ne menant à rien est abandonné.

Partons du R, il y a 4825 mots dans le dictionnaire réduit qui commencent par R


Ce dé a 3 lettres adjacentes


Il n'y a aucun mots commençant par RD dans notre dictionnaire de 4825 mots, pas dans le dictionnaire complet me direz vous, c'est possible.
Mais il n'y a que 213 mots commençant par RU et 125 par RI, soit beaucoup moins que dans le dictionnaire complet.

Voyons I, ce dés a 8 lettres adjacentes, dont une est déjà utilisée.


Il existe 38 mots dans le dictionnaire de 125 mots commençant par RID.

D possède 5 lettres adjacentes, dont 2 sont déjà utilisées.


Il n'existe pas de mot commençant par RIDI dans le dictionnaire de 38 mots.
Ce chemin est donc abandonné, les dizaines (centaines) de milliers de sous-chemins existant après RIDI ne seront pas parcourus.
Avec le dictionnaire complet, il resterait 42 mots, soit 42 branches de chemins à rechercher.

Sur cette grille le fait d'exclure les mots contenant une lettre non tirées, fait passer le temps de résolution de 5s à 0.7s, considérable!.

Et la méthode récursive dans tout ça?


Et bien, je viens de vous la décrire.
A partir d'une lettre:
-Listage des adjacents autorisés
-Y'a t il des mots commençant par la séquence lettre+adjacent?
-Oui, à partir d'une lettre:
-Listage des adjacents autorisés
-Y'a t il des mots commençant par la séquence 2 lettres+adjacent?
-Oui, a partir d'une lettre:
-Listage des adjacents autorisés
-Y'a t il des mots commençant par la séquence 3 lettres+adjacent?
-etc........
A chaque récursion, on clone le chemin en cours pour qu'il soit unique pour la récursion suivante. 

        /// <summary>
        /// Recherche par progression successive dans la grille, on teste s'il existe encore des mots commencant par le chemin
        /// en cours avant d'enclencher une instance supplémentaire.
        /// </summary>
        /// <param name="chemin">Chemin en cours</param>
        /// <param name="dico">dictionnaire appuré à chaque instance, il est impérativement sous forme de liste, en effet un Ienumerable créé par Linq sera évalué à postériori et dans les recursions succesives ça met le bazard/param>
        private void RechercheRecursive(Chemin chemin, List<string> dico)
        {
            List<De> adjacents =chemin.DernierDe.Adjacents(tires, chemin.Des);
            if (adjacents.Count() == 0) return;

            foreach (De d in adjacents)
            {
                Chemin monChemin = chemin.Clone();
                monChemin.Des.Add(d);

                List<string> dicoReduit = dico.FindAll(m => m.StartsWith(monChemin.Texte));//je commence par réduire le dictionnaire à la liste des mots commençant par le chemin en cours
                if (dicoReduit.Count() > 0)
                {
                    if (monChemin.Texte.Length > 2 && !chemins.Exists(m => m.Texte == monChemin.Texte) && dicoReduit.Exists(m => m == monChemin.Texte))//si le mot n'est pas déjà listé, et s'il existe on stocke le chemin
                        chemins.Add (monChemin );
                    
                    RechercheRecursive(monChemin, dicoReduit);//s'il existe des mots commençant par cette séquence on continue
                }
                else
                    continue;//sinon on passe au dé adjacent suivant

            }
        }


Cette méthode doit être appelée la première fois par une boucle qui parcours la grille. 
        /// <summary>
        /// Recherche dé par dé
        /// </summary>
        /// <param name="dicoExclu"></param>
        private void LanceRecherche(List<string> dicoExclu)
        {
            //début de la recherche Dé, par dé en lancant la méthode récursive
            foreach (De d in tires)
            {
                Chemin monChemin = new Chemin();
                monChemin.Des.Add(d);
                List<string> dicoReduit = dicoExclu.FindAll(c => c.StartsWith(monChemin.Texte));

                if (dicoReduit.Count() > 0) RechercheRecursive(monChemin, dicoReduit);
            }


Ci joint le code de la classe De, la recherche des dés adjacents se fait sur les coordonnées dans la grille.
Except permet de sortir les dés déjà utilisés. 
    public class De
    {
        private string faces;

        /// <summary>
        /// Construit un dé à partir d'un string listant chaque face
        /// </summary>
        /// <param name="Faces"></param>
        public De(string Faces)
        {
            faces = Faces;
        }

        /// <summary>
        /// Construit un dé sans faces pour les grilles saisies
        /// </summary>
        public De(string FaceVisible, int Index)
        {
            this.FaceVisible = FaceVisible;
            this.Index=Index;
            Y = Index / 4;
            X = Index - 4 * Y;
        }

        /// <summary>
        /// Abscise du dé dans le tableau
        /// </summary>
        public int X { get; set; }

        /// <summary>
        /// Ordonnée du dé dans le tableau
        /// </summary>
        public int Y { get; set; }

        /// <summary>
        /// Face visible après le tirage
        /// </summary>
        public string FaceVisible { get; set; }

        /// <summary>
        /// Index du dé dans la liste
        /// </summary>
        public int Index { get; set; }

        /// <summary>
        /// Méthode choisant aléatoirement la face visible, les coordonnées du dé dans le plateau sont transférés par cette méthode
        /// </summary>
        /// <param name="X"></param>
        /// <param name="Y"></param>
        public void Tirage(int X, int Y, Random rdm)
        {
            FaceVisible = faces[rdm.Next(faces.Length-1)].ToString();
            this.X = X;
            this.Y = Y;
            Index = 4 * Y + X;
        }

        /// <summary>
        /// Retourne les dés adjacents à l'instance en cours, en sortant les dés contenus dans la liste exception
        /// </summary>
        /// <param name="Tirage">Tableau de dés correspond au tirage</param>
        /// <param name="excepetions">Liste de dés à exclure du resultat</param>
        /// <returns></returns>
        public List<De> Adjacents(List<De> Tirage, List<De> excepetions)
        {
            return (from De d in Tirage
                    where (d != this && Math.Abs(d.X - X) < 2 && Math.Abs(d.Y - Y) < 2)
                    select d
                    ).Except(excepetions).ToList<De>();
        }

        public override string ToString()
        {
            //return X.ToString() + " " + Y.ToString(); 
            return FaceVisible;
        }

    }

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de Utilisateur anonyme
Les tops du mois