Exemple de méthode récursive: la résolution d'une grille de Boogle
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;
}
}