[Resolu][MY-AL]Recherche de mots dans dico

Pour les scripts écrits en C#
Règles du forum
Merci de respecter la NOMENCLATURE suivante pour vos TITRES de messages :

Commencez par le niveau de vos scripts
DB = Débutant
MY = Moyen
CF = Confirmé

Puis le domaine d'application
-RS = Réseau
-AL = Algorithmie

Exemple :

[DB-RS] Mouvement perso multijoueur
EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

[Resolu][MY-AL]Recherche de mots dans dico

Message par EmileF » 24 Jan 2020 21:23

Bonjour,

Je vais essayer d'être clair.

J'ai un dico de 239000 mots.
J'ai une grille de 5x5 lettres générées au hasard.

J'essaye de créer un algorithme qui me permettrai de créer une liste des mots possibles en prenant les lettres de ma grille dans tous les sens, de gauche à droite, de bas en haut, en diagonale et inversement.

J' ai essayé de créer moi même un script en utilisant des strings au lieu des listes ou des arrays, j'ai un petit début avec le premier et le deuxième caractère, mais je n'arrive pas trouver comment aller au delà, surtout s'il faut changer de direction en cas d'échec dans la recherche.

Si quelqu'un avait un petit conseil, un tuto, ou autre pour me permettre d'avancer un peu, ce serait sympa.

En tout cas, merci
Dernière édition par EmileF le 25 Jan 2020 21:38, édité 1 fois.
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [MY-AL]Recherche de mots dans dico

Message par EmileF » 25 Jan 2020 12:03

Bonjour,

J'avais fait une fonction de recherche de mots qui fonctionnait.
Dans mes recherches j'ai fait connaissance avec les ReGex, qui m'ont permis du condenser ma fonction en une seule ligne de code. Mais ceci ne me permet que de rechercher les mots que dans un cas.

C'est là que je suis bloqué, et mon vieil esprit ne me permet pas de progresser. J'ai bien entendu parlé de récursivité, mais je n'arrive pas à l'appliquer dans mon cas.

Si quelqu'un pouvait me mettre sur la voie ce serait super

Voilà le début de mon script:

Code : Tout sélectionner

   
   //le dico est un simple string et les mots sont séparés par un espace 
    private void RechercheMots()
    {
        Possibles = "";
        int i = 0;
        //les 2 premières cases de ma grille
        string t = " " + Cases[i].text + Cases[i + 1].text;
        string liste = RechercheMotsCommencantPar(dico, t);
        print(liste);
    }


    private string RechercheMotsCommencantPar(string source, string text)
    {
        string liste = "";
        foreach (Match item in Regex.Matches(source, text))
        {
            int i = item.Index;
            int f = dico.IndexOf(" ", i + 1);
            liste += dico.Substring(i, f - i);
        }
        return liste + " ";
    }
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [MY-AL]Recherche de mots dans dico

Message par djulio74 » 25 Jan 2020 13:05

Salut Emile!
déjà est-ce que tu a bien ordonné tes éléments de ta grille?
par exemple de ton cas, avec Dim = nombre de colone et de ligne, donc Dim = 5.
et "Case" un array de DIM x Dim élément pour chacune des cases de ta grille, Case.length = 25 donc.
histoire de bien ordonner tes élément "Case" , en pseudo code :

Code : Tout sélectionner

// pour chacune des lignes
for ( int i = 0 , i < Dim, i ++){
	// chacune des colones
	for ( int j = 0 ; j < Dim ; j ++){
		Case[i * Dim + j] = Random.lettre;
	}
}
tu te retrouve bien avec premiere ligne "Case" de 0 à 4, deuxieme de 5 à 9 etc..
à partir de la tu peut savoir quelles sont les cases voisine en fonction d'une direction. Genre la "Case" au dessus d'une "Case" est la "Case[i + Dim], encore en pseudo code :

Code : Tout sélectionner

// la case au dessus d'une autre : 
	Case[auDessus de i] = Case[ i + Dim];
// la case a droite : 
	Case[Adroite de i] = Case[i + 1];
// la case en haut a gauche : 
	Case[hautGauche de i] = Case[i -1 + Dim];
Attention a mettre des condition pour les cases sur les bord de la grille, Exemple et case du bas peuvent pas avoir de case voisines plus bas (hors grille)
en gros faire un array de 8 élément pour chaque direction possible (haut, bas, gauche, droite, hautGauche, hautDroite... etc)

Code : Tout sélectionner

int [] Direction = new int[8]{
	Direction[0] = +1, 		// case de droite
	Direction[1] = -1, 		// case de gauche
	Direction[2] = Dim, 		// case en Haut
	Direction[3] = -Dim , 		// case en Bas
	Direction[4] = Dim + 1, 	// case en Haut a Droite
	Direction[5] = Dim - 1, 	// case en Haut a Gauche
	Direction[6] = - Dim + 1, 	// case en Bas a droite
	Direction[7] = - Dim - 1, 	// case en Bas a Gauche
	};
	
Pour rechercher tes mots
- pour chaque case de la grille, si des mots du dico commence par la lettre de la case, stocker le mot dans un array.
- -> si cet array de mots n'est pas vide :
- - -> pour chaque direction possible :
- - - -> stocker dans un array les mots du précedent array qui ont pour deuxieme lettre celle de la case voisine
- - - -> recommencer dans la même direction jusqu'au bout de la grille
- - - -> A chaque fois que tu met un mot dans un array, si la lettre qui a permis de l'y mettre est sa derniere lettre,
stocker le mot dans un array a part " Mot du dico trouvé".

C'est une methode qui je pense pourrait fonctionner.

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [MY-AL]Recherche de mots dans dico

Message par EmileF » 25 Jan 2020 14:08

Salut Djulio et merci

Pour ce qui est de l'ordre des cases et des directions, c'est la méthode que j'emploie.
Je vérifie les limites de la grille comme tu me l'indiques aussi.

C'est ensuite que ça coince car j'essaye d'utiliser la récursivité, et j'avoue que je m'y perds un peu

Je n'utilise pas les arrays mais je travaille avec des strings pour pouvoir utiliser les Regex, mais je pense que ça ne change rien pour les algorithmes.

voila un début de mes fonctions

Code : Tout sélectionner

    private void RechercheMots()
    {
        Possibles = "";
        for (int i = 0; i < 25; i++)
        {
            RechercheMots(dico, i, " " + Cases[i].text);
        }
    }

    //fonction récursive
    private void RechercheMots(string dico, int i, string t)
    {
        string s = "";
        //pour connaitre la position de la case
        int l = i / 5;
        int c = i % 5;
        if (c < 4) //cases horizontale suivante
        {
            s = t + Cases[i + 1].text;
        }
        if (l < 4)//cases en dessous
        {
            if (c < 4)//case en bas à droite
                s = t + Cases[i + 6].text;
            else if (c > 0)//case en bas à gauche
                s = t + Cases[i + 4].text;
            else //case juste en dessous
                s = t + Cases[i + 5].text;
        }
        if (s != "")
        {
            string liste = RechercheMotsCommencantPar(dico, s);
            if (liste.Length > 1)
            {
                RechercheMotsComplets(liste, s.Length - 1);
                RechercheMots(liste, i + 1, s);
            }
        }

    }

    //si la longueur des mots correspond à n c'est un mot possible(je pense)
    private void RechercheMotsComplets(string liste, int n)
    {
        int d = 1;
        retour:
        int f = liste.IndexOf(" ", d);
        int l = f - d;
        if (l > n) return;
        if (l == n)
        {
            Possibles += " " + liste.Substring(d, f - d);
            d = f + 1;
            goto retour;
        }
    }

    //retourne un string contenant les mots possibles séparés par un espace.
    private string RechercheMotsCommencantPar(string source, string text)
    {
        string liste = "";
        foreach (Match item in Regex.Matches(source, text))
        {
            int i = item.Index;
            int f = dico.IndexOf(" ", i + 1);
            liste += dico.Substring(i, f - i);
        }
        return liste + " ";
    }
Ce n'est pas complet, mais je voudrais savoir si je suis dans la bonne direction

En tout cas merci

Edit:
Voila pour cette grille générées au hasard
U Z E R T
M G Z R A
J M T Z O
A I G R E
R E S S P
ce script me sort "ER RA MM MG SES ES RE ES"
Je ne comprend pas pourquoi il me sort "SES", "MM" et "MG" sont dans mon dico;
et pourquoi il ne me sort pas "AIGRE"
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [MY-AL]Recherche de mots dans dico

Message par djulio74 » 25 Jan 2020 14:38

Alors comme ça dans le désordre :
- tu n'as pas l'air de chercher les 8 directions possibles
- tes conditions sont pas exhaustive, tu chercher juste si dernière ligne ou colonne, tu devrait aussi avoir les première. Si l ==0, tu devrait pas chercher en bas par exemple.
- essaye déjà de modifier ton script et ne faire des recherches que dans une direction, genre juste a l'horizontal droite voir s'il te trouve aigre.
- vu qu'il te manque des condition j'ai l'impression, si t'es première colonne deuxième ligne, sur le A de aigre, si tu cherche a gauche par exemple, tu va te retrouver sur la dernière colonne première ligne sur le P.
- regarde si tes recherchemot et motcomplet fonctionne bien :
- - a l'appuiye d'une touche, cherche par exemple tout les mots commençant par A. juste ça.

En gros essaye de partitionner ton script, lancer des fonctions individuellement avec une condition de lettre précise, ou de direction précise vois ou ça bloque

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [MY-AL]Recherche de mots dans dico

Message par EmileF » 25 Jan 2020 14:52

Djulio a écrit : tu n'as pas l'air de chercher les 8 directions possibles
Je sais mais c'est pour l'essai.
Djulio a écrit : - tes conditions sont pas exhaustive, tu chercher juste si dernière ligne ou colonne, tu devrait aussi avoir les première. Si l ==0, tu devrait pas chercher en bas par exemple.
Et mes cases sont rangées de haut en bas et de gauche à droite. Donc la ligne 0 est en haut.

pour le reste j'ai modifié mon script

Code : Tout sélectionner

    
    //fonction récursive
    private void RechercheMots(string dico, int i, string t)
    {
        string s = "";
        //pour connaitre la position de la case
        int l = i / 5;
        int c = i % 5;
        int p = 0;
        if (c < 4) //cases de droite
        {
            p = i + 1;
        }
        if (c > 0) //cases de gauche
        {
            p = i - 1;
        }
        if (l < 4)//cases en dessous
        {
            if (c < 4)//case en bas à droite
            {
                p = i + 6;
            }
            else if (c > 0)//case en bas à gauche
            {
                p = i + 4;
            }
            else //case juste en dessous
            {
                p = i + 5;
            }
        }
        if (l > 0)//cases en dessus
        {
            if (c < 4)//case en haut à droite
            {
                p = i - 4;
            }
            else if (c > 0)//case en haut à gauche
            {
                p = i - 6;
            }
            else //case juste en dessus
            {
                p = i - 5;
            }
        }
        if (p != 0)
        {
            s = t + Cases[p].text;
            string liste = RechercheMotsCommencantPar(dico, s);
            if (liste.Length > 1)
            {
                RechercheMotsComplets(liste, s.Length - 1);
                RechercheMots(dico, p, s);
            }
        }

    }
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [MY-AL]Recherche de mots dans dico

Message par djulio74 » 25 Jan 2020 14:58

d’après ce que je vois, tu fais pas de recherche de mot pour chaque direction, mais tu fais toute les direction avant de trouver le mot.
en gros ton p est remplacé plusieurs fois.

Code : Tout sélectionner

if (c < 4) //cases de droite
{
p = i + 1;
}
if (c > 0) //cases de gauche
{
p = i - 1;
}
tu fais le deux a la suite, si c ==2 alors les deux conditions sont vraie par exemple.

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

djulio74
Messages : 682
Inscription : 19 Déc 2009 22:55

Re: [MY-AL]Recherche de mots dans dico

Message par djulio74 » 25 Jan 2020 15:01

tu devrais avoir pluto une liste de direction. un fonction qui, pour chaque direction verifie que la case n'est pas sur un bord concerné, si c'est ok, lance la fonction RechercheMot avec p.

______________________________________________________________
\_______________________ Impossible is nothing _______________________/

EmileF
Messages : 673
Inscription : 18 Mars 2017 19:39

Re: [MY-AL]Recherche de mots dans dico

Message par EmileF » 25 Jan 2020 18:04

Merci Djulio, tu es un chef.

Grâce à tes explications, j'ai réussi à faire fonctionnel mon script.

Le voici:

Code : Tout sélectionner

    private void RechercheMots()
    {
        Possibles = "";
        //parcours la grille
        for (int i = 0; i < 25; i++)
        {
            //recherche les mots du dico à partir de la case courante 
            //avec comme première lettre, la lettre de cette case
            RechercheMots(dico, i, " " + Cases[i].text);
        }
    }

    List<int> Dir = new List<int> { 1, 6, 5, 4, -1, -6, -5, -4 };

    private int Direction(int i, int dir)
    {
        //pour connaitre la position de la case
        int l = i / 5;
        int c = i % 5;
        switch (dir)
        {
            case (1): //droite
                if (c < 4) return i + 1;
                break;
            case (6): //bas droite
                if (l < 4 && c < 4) return i + 6;
                break;
            case (5): //bas
                if (l < 4) return i + 5;
                break;
            case (4): //bas gauche
                if (l < 4 && c > 0) return i + 4;
                break;
            case (-1): // gauche
                if (c > 0) return i - 1;
                break;
            case (-6): // haut gauche
                if (l > 0 && c > 0) return i - 6;
                break;
            case (-5): // haut
                if (l > 0) return i - 5;
                break;
            case (-4): // haut droite
                if (l > 0 && c < 4) return i - 4;
                break;
            default:
                break;
        }
        return 0;

    }

    //fonction récursive
    private void RechercheMots(string dico, int i, string t)
    {
        //pour connaitre la position de la case
        int l = i / 5;
        int c = i % 5;
        string liste;
        for (int d = 0; d < 8; d++)
        {
            int p = Direction(i, Dir[d]);
            if (p!= 0)
            {
                //constitue le nouveau début de mot
                string s = t + Cases[p].text;
                //cherche dans la liste les mots qui commence par ce début
                liste = RechercheMotsCommencantPar(dico, s);
                //si la liste est plus grande que 0
                if (liste.Length > 1)
                {
                    print(liste);
                    //collectionne les mots de la liste dont la longueur correspond au début
                    RechercheMotsComplets(liste, s.Length - 1);
                    //continue la recherche à partir de la nouvelle position avec le nouveau début
                    RechercheMots(liste, p, s);
                }

            }
        }
    }

    //si la longueur des mots correspond à n c'est un mot possible(je pense)
    private void RechercheMotsComplets(string liste, int n)
    {
        int d = 1;
        retour:
        int f = liste.IndexOf(" ", d);
        int l = f - d;
        if (l > n) return;
        if (l == n)
        {
            string mot = " " + liste.Substring(d, f - d);
            if (!Regex.IsMatch(Possibles, mot))
            {
                Possibles += mot;
                liste.Remove(d-1, f - d+1);
            }
            d = f + 1;
            goto retour;
        }
    }

    //retourne un string contenant les mots possibles séparés par un espace.
    private string RechercheMotsCommencantPar(string source, string text)
    {
        string liste = "";
        foreach (Match item in Regex.Matches(source, text))
        {
            int i = item.Index;
            int f = source.IndexOf(" ", i + 1);
            liste += source.Substring(i, f - i);
        }
        return liste + " ";
    }

pour l'exemple j'ai creer une grille avec les lettres de "ANTICONSTITUTIONNELLEMENT" en les disposant de façon à ce quelles puissent se lire à la suite l'une de l'autre en partant du haut gauche et en descendant vers le bas droite;

Code : Tout sélectionner

ANTIC
ITSNO
TUTIO
LLENN
EMENT
voilà la liste des mots que mon script à trouvé. Le seul petit bémol est qu'il a mis dans les eaux de 20 secondes pour tout calculer. Y aurait-il une astuce pour réduire cette durée
AN ANTI ANTICONSTITUTIONNEL
ANTICONSTITUTIONNELLE
ANTICONSTITUTIONNELLEMENT
ANS ATTISIONS ATTENTION
ATTENTIONNE ATTENTIONNEE
ATTENTIONS ATTENTISTE ATTENTE
ATTENTENT ATTELE ATTELEE ATTELLE
ATTEINT ATTEINTE ATTEINTS ATTEINS
ATTICISTE AI AIT AINSI NI TI TIC TIN
TINT TINTIONS TINTIN TINTE TINTENT
TINTEE TINTEMENT TINTEMENTS TINS
TITI ICI ION IONONE IONIE IONIEN
IONIENNE IONS INITIONS INITIE
INITIENT INITIEE INTITULE INTITULENT
INTITULEE INTENTION INTENTIONNE
INTENTIONNEL INTENTIONNELLE
INTENTIONNELLEMENT INTENTIONNEE
INTENTIONS INTENTE INTENTENT
INTENTEE INTUITU INSISTIONS
INSISTE INSISTENT INSTITUT
INSTITUTION INSTITUTIONNEL
INSTITUTIONNELLE INSTITUTIONS
INSTITUTS INSTITUE INSTITUENT
INSTITUEE INSU INSULTIONS
INSULTE INSULTENT INSULTEE
INCONTINENT INCONTINENTE
INCONTINENTS INCONSTITUTIONNEL
INCONSTITUTIONNELLE
INCONSTITUTIONNELLEMENT
INCISION INCISIONS INCITIONS
ISITE COI COIN COIT COITE
COITS COIS COINS COINCONS
COINCIONS CON CONTIONS CONTINT
CONTINENT CONTINENTE CONTINENTS
CONTIENT CONTIENNE CONTIENNENT CONTINS CONTE CONTENT CONTENTION CONTENTIONS CONTENTE CONTENTENT CONTENTEE CONTENTEMENT CONTENTS CONTENIONS CONTENONS CONTEE CONTUS CONTUSION CONTUSIONNE CONTUSIONNEE CONTUSIONS CONSISTIONS CONSISTE CONSISTENT CONSTITUTION CONSTITUTIONNEL CONSTITUTIONNELLE CONSTITUTIONNELLEMENT CONSTITUTIONS CONSTITUE CONSTITUENT CONSTITUEE CONSTELLE CONSUL CONSULTIONS CONSULTE CONSULTENT CONSULTEE CONCOIT CONCOIS CONCIS CONCISION COCO COCOON COCON COCONS CI CISTE CITIONS IULE TU TUT TUTIE TUTELLE TUTU TUTTI TUE TUENT TUEE TULLE TUS TITUS SI SIONISTE SINITE SINO SINON SINE SIEN SIENNOIS SIENNE SIEENT SITE SITET SITUE SITUENT SITUEE SIS STE STENO STEM STELE SU SUT SUE SUENT SUEE SUET SUI SUIT SUINT SUINTIONS SUS SUSTENTE SIC NO NOIE NOIENT NON NONNE NONE NIONS NIE NIENT NIEE NIEME NIELE NIELLE NICOIS OINT OIE OINS ON ONT ONS ONC OC UT ULM ULULE ULULEMENT ULULEMENTS US USIONS USINIONS USINONS USINE USINENT USINEE USITE USITEE USUEL USUELLE USUELLEMENT USUS TIEN TIENT TIENNE TIENNENT TE TENNIS TENEMENT TENTIONS TENTE TENTENT TENTEE TENIONS TENON TENONS TEE TEL TELE TELEE TELETE TELL TELLE TELLEMENT TETIN TETINE TETE TETEE TETU TETUE TETUS TETTIN TEINT TEINTIONS TEINTE TEINTENT TEINTEE TEINTS TEINS INNE INNEE INNEITE INNEISTE ITEM LE LU LUT LUTIN LUTINE LUTINS LUTE LUTEINE LUE LUETINE LULU LUI LUIT LUTTIONS LUTTE LUTTENT LUS LUSIN LENT LENTE LENTEMENT LENTS LENINISTE LENITION LEU LET LEI EN ENTIONS ENTITE ENTE ENTENT ENTENTE ENTEE ENTETIONS ENTETE ENTETENT ENTETEE ENTETEMENT ENTETEMENTS ENIEME ENONCONS ENONCIONS EME EMEU EMEUT EMEUTE EMEUS EMET EMETINE EMETS ELEMENT ELEMENTS ELEIS ELLE ELU ELUT ELUTION ELUE ELUS EU EUT EUE EUS ET ETIONS ETISIE ETE ETENT ETEE ETEULE ETETE ETETEMENT ETETEMENTS ETEINT ETEINTE ETEINTS ETEINS ETUI NE NENE NENNI NEE NET NETS ME MEN MENT MENE MENENT MENEE MENNONITE MEME MEMEMENT MELE MELENT MELEE MELUSINE MENTI MENTION MENTIONNE MENTIONNENT MENTIONNEE MENTIONNIONS MENTIONNONS MENTIONS MENTIE MENTIT MENTIS MENTE MENTENT MENIONS MENIN MENINE MENONS ML MLLE MEUT MEUTE MEULE MEULENT MEUS MET METIS METS
La différence entre l'intelligence et la stupidité est que l'intelligence est limitée.

Avatar de l’utilisateur
Alesk
Messages : 2303
Inscription : 13 Mars 2012 09:09
Localisation : Bordeaux - France
Contact :

Re: [Resolu][MY-AL]Recherche de mots dans dico

Message par Alesk » 25 Jan 2020 22:51

Pour accélérer la recherche, tu va devoir structurer ton dictionnaire de manière à optimiser les recherches dedans.

Je tente un truc de tête, donc c'est pas garanti que ça soit idéal !

Pour chaque mot, tu supprimes toutes les lettres en double, puis tu les classes par ordre alphabétique :

Code : Tout sélectionner

ANTICONSTITUTIONNELLEMENT -> ANTICOSUELM -> ACEILMNOSTU
ATTENTION -> ATENIO -> AEINOT
ATONE -> AENOT
CONSTITUTIONS -> CONSTIU -> CINOSTU
SINON -> INOS
BARAGE -> ABEGR
RAGE -> AEGR
LARGEMENT -> AEGLMNRT
VOITURE -> EIORTUV
TOITURE -> EIORTU
ROUTE -> EORTU
TOUR -> ORTU
OU -> OU
ça te fera une clé d'identification à associer à chaque mot, que tu peux stocker sous la forme d'un dictionary, avec cette chaine simplifiée comme clé, et comme valeur une List<string>() qui contiendra tous les mots associés.

Puis tu fais une seconde structure ou tu les tries du plus long au plus court, en créant une hiérarchie avec les plus longs à la racine :

Code : Tout sélectionner

ACEILMNOSTU           >> ANTICONSTITUTIONNELLEMENT + tous les mots qui contiennent les mêmes lettres
    -> AEINOT         >> ATTENTION + tous les mots qui contiennent les mêmes lettres
        -> AENOT      >> ATONE + tous les mots qui contiennent les mêmes lettres
    -> CINOSTU        >> CONSTITUTIONS etc ...
        -> INOS       >> SINON ...
AEGLMNRT              >> LARGEMENT ...
    ->ABEGR           >> BARAGE ...
        -> AEGR       >> RAGE ...
EIORTUV               >> EIORTUV ...
    -> EIORTU         >> TOITURE ...
        -> EORTU      >> ROUTE ...
            -> ORTU   >> TOUR
                -> OU >> OU
Et/ou bien l'inverse : tu commences par les plus courts à la racine, et tu mets les plus longs ensuite.

A partir de là, tu auras une structure plus pratique pour réduire les listes de mots à parcourir pour trouver ce que tu cherches.
J'ai pas le temps de réfléchir plus en avant là dessus, mais ça te fait déjà une base de réflexion.

Répondre

Revenir vers « (C#) CSharp »