Sujet Précédent Sujet Suivant

VBA Excel - Récursivité - Jeu du Boggle

pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 - Modifié par pijaku le 6/02/2014 à 15:36
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 - 5 août 2014 à 11:52
Bonjour Mesdames, Messieurs,

Il y a deux ans, j'ai voulu créer une fiche pratique, sur CCM, intitulée "le jeu du boggle". visible ICI. Comme vous pourrez le voir en y jetant un oeil, c'est pas mal, mais pas top...

A l'époque, je ne connaissais pas la récursivité et j'avais toutefois réussi à "bricoler" un code qui à défaut d'être parfait, fonctionnait à peu près.

Fini l'à peu près pour moi, je souhaites refonder ce code afin de le rendre réellement opérationnel.

Pour cela, je vais avoir besoin de vous...

Il faut, pour cette "appli", plusieurs codes. Je vais créer, dans ce sujet, une réponse par code. Suffira de suivre en commentant ces réponses pour améliorer les codes VBA proposés.

Les différents codes nécessaires :
- récupérer un dictionnaire extrait d'un fichier .txt dans une variable sous VBA (soit une variable tableau, soit un objet dictionary)
- tirage aléatoire des lettres,
- comparaison des lettres du tirage avec l'alphabet afin de voir qu'elles lettres sont manquantes,
- grâce aux lettres manquantes, épurer la liste des mots du dico,
- trouver peut être une seconde méthode d'épuration de cette liste...
- créer un code qui va trouver les mots du dico pouvant être formés à partir de lettres adjacentes de la grille.

Voici déjà le classeur de base, avec :
- un range nommé grille '-----> Menu Insertion/Noms/Définir
- trois boutons de commande :
=>tirage (il fonctionne) -- Code : Sub Tirage()
=>solutions (ne fonctionne pas) -- code : Sub RetirerMotsLettresManquantes()
=>efface (il fonctionne) -- Code : Sub Efface()

Le classeur : http://cjoint.com/?DBgpyvwtxf3

Pour celles et ceux qui n'aiment pas trop télécharger via des sites de pièce jointe, envoyez moi votre mail perso via MP, je vous ferais un envoi particulier.

Merci d'avance.
Cordialement,
Franck

71 réponses

Réponse 1 / 71
f894009 Messages postés 17185 Date d'inscription dimanche 25 novembre 2007 Statut Membre Dernière intervention 15 avril 2024 2
Modifié par f894009 le 4/03/2014 à 18:27
Bonjour a vous tous,

A la demande de Pijaku, j'ai donc fait des test sur deux versions et cela donne les resultats suivants:

Test sous W8, Intel core I5--3210M 2.5GHz:

peu importe la version excel, resultats sensiblement identiques et seulement 32% occupation processeur

boggle-like_v0.43test.xls

XL 2007
- Charger dico : 3.38 s
- Détruire : 174.80 s

XL 2010
- Charger dico : 3.16 s
- Détruire : 173.30 s

XL 2013
- Charger dico : 3.45 s
- Détruire : 177.66 s


boggle-like_v0.43_v2_test.xls

XL 2007
- Charger dico : 3.41 s
- Détruire : 177.19 s

XL 2010
- Charger dico : 3.20 s
- Détruire : 176.68 s

XL 2013
- Charger dico : 3.31 s
- Détruire : 178.71 s


A+
2
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 4/03/2014 à 18:41
Bonjour et merci pour ton rapport de test,
Directement sur me fichier téléchargé ou après (relis mon message précédent) l'avoir sauvegardé dans un autre dossier, fermé, puis ouvert à nouveau ?
0
f894009 Messages postés 17185 Date d'inscription dimanche 25 novembre 2007 Statut Membre Dernière intervention 15 avril 2024 2
Modifié par f894009 le 4/03/2014 à 19:12
Re,

copier fichier dans un repertoire et ouvert/fermer plusieurs fois. Aux premiers essais, voyant que c'etait plutot long, j'ai cru qu'excel etait plante. J'ai trouve des temps en remontant le fil du sujet, donc j'ai recommence en attendent que cela se fasse.
0
carlvb Messages postés 199 Date d'inscription mercredi 23 avril 2003 Statut Contributeur Dernière intervention 25 mai 2017 11
4 mars 2014 à 18:54
Bonjour f894009,

Merci beaucoup de votre retour.
Pouvez-vous essayer d'ouvrir le fichier et l'enregistrer toujours au format xls mais sous un autre nom avant de relancer le test. Merci d'avance
0
f894009 Messages postés 17185 Date d'inscription dimanche 25 novembre 2007 Statut Membre Dernière intervention 15 avril 2024 2
4 mars 2014 à 19:19
Re,

172.71 s pour la destruction, reste dans la plage 173-179
0
carlvb Messages postés 199 Date d'inscription mercredi 23 avril 2003 Statut Contributeur Dernière intervention 25 mai 2017 11
4 mars 2014 à 19:31
Re,

Encore merci pour ces résultats. Il y a vraiment donc un problème lors de la destruction, la mémoire met trop de temps à se libérer chez quatre testeurs différents.

Bonne soirée.
0
Réponse 2 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
7 févr. 2014 à 13:44
Ta "charnière", pijaku , c'est la conjugaison des deux.
Il est adroit (même si lent) de réduire la liste les mots possibles.
Mais il n'est pas adroit, une fois établie cette liste "épurée", de travailler depuis elle plutôt que depuis les chemins de la grille.
Ta manière de retirer les mots impossibles n'est toutefois pas forcément la plus complète et la plus adroite.
Je vais m'atteler (après ma partie de pêche) à cette première étape que nous appellerons étape d'épuration.
1
Réponse 3 / 71
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
Modifié par Whismeril le 9/02/2014 à 21:50
Bonsoir, j'ai finit le mien, en C#, je suis plus à l'aise dans ce langage.

Comme Uc j'avais remarqué que la position des dés est figée dans ton xls. J'ai pensé à une erreur, et mon tirage est aussi aléatoire dans la position.
C'est corrigeable au besoin.

Pour le principe, je charge une fois le dictionnaire, passe tout en majuscule sans accent.
Mon chargement supprime les mots composés, mais je peux changer ça aussi

Ensuite j'initie chaque dés et effectue le tirage, chaque dé connait ses coordonnées pour la construction des mots.

Je commence par le dé en haut à gauche, je cherche les dés adjacents, j'en choisi un.
S'il existe des mots qui commence par ces deux lettres, je réduit le dico à ces mots (très gros gain de temps dans les recherches!)
je recherche les adjacents en excluants les deux premiers dés et ainsi de suite de manière récursive.
Si un chemin de plus de trois lettres est un mot connu, il est stocké.

Voici le code

Le dictionnaire 
    /// <summary>
    /// Classe permettant de charger et de gérer le dictionnaire
    /// </summary>
    public class Dico
    {
        private List<string> dico;
        private IEnumerable<string> dicoAppure;

        public Dico(string path)
        {
            Ouvrir(path);
        }

        /// <summary>
        /// Charge le fichier en paramètre, passe tous les mots en majuscules sans accent, exclu les mots composés
        /// </summary>
        /// <param name="path"></param>
        /// <returns></returns>
        public List<string> Ouvrir(string path)
        {
            char[] separateurs = { ' ','/','\t', '\\', Convert.ToChar(10) };
            string[] tab = File.ReadAllText(path,Encoding.ASCII).Split(separateurs);

            Regex maRegex = new Regex("^[A-Z]{3,}$");
            
            dico = (from mot in tab
                                 let m = RemoveDiacritics(mot.Trim()).ToUpperInvariant()
                                 where m.Length > 2 && maRegex.IsMatch(m)
                                 select m
                                
                                
                                ).ToList<string>();



            return dico;                   
        }

        /// <summary>
        /// Methode qui supprime les accents, source http://www.developpez.net/forums/d286030/dotnet/langages/csharp/supprimer-accents-lettre/
        /// </summary>
        /// <param name="stIn"></param>
        /// <returns></returns>
        private string RemoveDiacritics(string stIn)
        {
            string stFormD = stIn.Normalize(NormalizationForm.FormD);
            StringBuilder sb = new StringBuilder();

            for (int ich = 0; ich < stFormD.Length; ich++)
            {
                UnicodeCategory uc = CharUnicodeInfo.GetUnicodeCategory(stFormD[ich]);
                if (uc != UnicodeCategory.NonSpacingMark)
                {
                    sb.Append(stFormD[ich]);
                }
            }

            return (sb.ToString().Normalize(NormalizationForm.FormC));
        }

        /// <summary>
        /// Liste de mots qui constitue ce dictionnaire
        /// </summary>
        public List<string> Liste { get { return dico; } }
    }



un dé 

    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>
        /// 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 = new Random();
            FaceVisible = faces[rdm.Next(faces.Length-1)].ToString();
            this.X = X;
            this.Y = Y;
            Index = 4 * X + Y;
        }

        /// <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 FaceVisible;
        }

    }


le tirage et la recherche de solution 
    public class Tirage
    {

        List<De> tires;

        /// <summary>
        /// Assure le tirage des disponibles 16 dés et la recherche de solutions
        /// </summary>
        /// <returns></returns>
        public Tirage(Dico MonDico)
        {
            this.MonDico = MonDico;

            Solutions = new List<string>();

            NouveauTirage();
        }

        public void NouveauTirage()
        {
            //dés disponilbes
            List<De> disponibles = new List<De>();
            disponibles.Add(new De("ETUKNO"));
            disponibles.Add(new De("EVGTIN"));
            disponibles.Add(new De("IELRUW"));
            disponibles.Add(new De("DECAMP"));
            disponibles.Add(new De("EHIFSE"));
            disponibles.Add(new De("RECALS"));
            disponibles.Add(new De("ENTDOS"));
            disponibles.Add(new De("OFXRIA"));
            disponibles.Add(new De("NAVEDZ"));
            disponibles.Add(new De("EIOATA"));
            disponibles.Add(new De("GLENYU"));
            disponibles.Add(new De("BMAQJO"));
            disponibles.Add(new De("TLIBRA"));
            disponibles.Add(new De("SPULTE"));
            disponibles.Add(new De("AIMSOR"));
            disponibles.Add(new De("ENHRIS"));
            
            //dés tirés
            tires = new List<De>();

            //effectue le tirage de la grille
            for (int x = 0; x < 4; x++)
                for (int y = 0; y < 4; y++)
                    UnDe(disponibles, tires, x, y);

            //List<Chemin> chemins1 = CalculChemins();
            List<Chemin> chemins2 = CalculCheminsRecursif();
        }


        /// <summary>
        /// Lance un dé de la liste des dés disponibles, et le place dans la liste des dés tirés
        /// </summary>
        /// <param name="disponibles"></param>
        /// <param name="tires"></param>
        /// <param name="X"></param>
        /// <param name="Y"></param>
        private void UnDe(List<De> disponibles, List<De> tires, int X, int Y)
        {
            Random rnd = new Random();
            De monDe = disponibles[rnd.Next(disponibles.Count)];

            monDe.Tirage(X, Y);
            tires.Add(monDe);
            disponibles.Remove(monDe);
        }

        /// <summary>
        /// retourne les dés tirés
        /// </summary>
        public List<De> Des 
        { 
            get { return tires; }
            set { tires = value; }
        }

        /// <summary>
        /// Calcul tous les chemins de 3 dés possibles par récursivité
        /// </summary>
        private List<Chemin> CalculCheminsRecursif()
        {
            List<Chemin> chemins = new List<Chemin>();

            foreach (De d in tires)
            {
                Chemin monChemin = new Chemin();
                monChemin.Des.Add(d);
                RechercheRecursive(monChemin, chemins, MonDico.Liste.FindAll(m => m.StartsWith(monChemin.Texte)));
            }

            Solutions = (from c in chemins
                         select c.Texte).ToList<string>();

            return chemins;
        }

        /// <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="chemins">Liste des chemins valide</param>
        /// <param name="dico">dictionnaire appuré à chaque instance</param>
        private void RechercheRecursive(Chemin chemin, List<Chemin> chemins, 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);

                int i;
                if (monChemin.Texte == "LUNE") 
                    i = monChemin.Des.Count;

                if (monChemin.Texte.Length > 2 && !chemins.Exists(m => m.Texte == monChemin.Texte) && dico.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);

                List<string> dicoReduit = dico.FindAll(m => m.StartsWith(monChemin.Texte));
                if (dicoReduit.Count > 0)
                    RechercheRecursive(monChemin, chemins, dicoReduit);//s'il existe des mots commencant par cette sequence on continue
                else
                    continue;//sinon on passe au dé adjacent suivant

            }
        }

        public Dico MonDico { get; set; }

        public List<string> Solutions { get; set; }

     }


J'ai fait quelques dizaines de tirages ça tourne en moyenne autour d'une seconde de calcul.


Penser aux balises de coloration syntaxique: bouton <>, préciser le langage :<code csharp>.
Quand la solution est trouvée, mettre la discussion Résolue.
1
Réponse 4 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 8/03/2014 à 20:47
Bon...
Je vois que les choses sont en de TRES bonnes mains en ce qui concerne les fondements à proprement parler.
Je vais dans ce cas commencer à me pencher, de mon côté, au "camouflage" avancé par pijaku : à savoir "cacher" Excel et utiliser un userform.
Je vais essayer de le faire :
1) sans ne rien perdre de ce qui a été développé à partir d'une grille existante sur Excel
2) sans ne rien toucher aux traitements sur la base de cette grille
3) en "ouvrant" à pijaku la possibilité de choisir la taille et l'emplacement de ma "pseudo grille" à afficher sur l'userform (la seule que l'utilisateur verra finalement)
Je pense y parvenir sans trop de difficultés, mais vais devoir m' "isoler" un peu pour au moins 36 heures (essais obligent).

Je vais par ailleurs essayer (je dis bien essayer, car Excel et son VBA n'ont pas cette vocation) de "gimpiser" le Userform sans faire appel à l'importation d'une image.Je pense simplement à la discussion que pijaku a ouverte sur CCM ici
http://www.commentcamarche.net/forum/affich-29822256-realisation-d-une-image-pour-le-design-d-un-jeu#123
il souhaite une image non "gourmande". Je vais essayer de la réduire à un minimum, quitte à la rendre un peu moins "GIMP"
Je vais surtout m'efforcer d'éviter que des "images" ne viennent réduire à peau ce chagrin la place nécessaire à l'affichage des solutions, hein ...

A très bientôt.

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
1

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 71
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
Modifié par pijaku le 6/02/2014 à 15:46
Re-

Le premier code est celui du tirage aléatoire des lettres formant la grille.
Le voici : 
Sub Tirage()
Dim Cubes As Variant, Cel As Range, cpt As Byte, carac As Integer

cpt = 0
Sheets("feuil1").Range("grille").ClearContents
Cubes = Array("ETUKNO", "EVGTIN", "IELRUW", "DECAMP", "EHIFSE", "RECALS", "ENTDOS", "OFXRIA", "NAVEDZ", "EIOATA", "GLENYU", "BMAQJO", "TLIBRA", "SPULTE", "AIMSOR", "ENHRIS")
Randomize
For Each Cel In Range("grille")
    Do
        carac = CInt((6 * Rnd()) + 1)
        If carac < 6 And carac > 1 Then Cel.Value = Mid(Cubes(cpt), carac, 1)
    Loop While Cel.Value = ""
    cpt = cpt + 1
Next Cel
End Sub


L'array "Cubes" réponds aux contraintes de la règle du jeu, imposant les lettres sur les faces des différents dés...

Cordialement,
Franck
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
10 févr. 2014 à 09:19
Suite à la remarque d'ucfoutu, ICI, voici le nouveau code de tirage : 
Sub Tirage()
Dim Cubes As Variant, cpt As Byte, carac As Integer, AleaLig As Integer, AleaCol As Integer

 'la grille choisie : Range("D2:G5")
Sheets("feuil1").Range("grille").ClearContents
Cubes = Array("ETUKNO", "EVGTIN", "IELRUW", "DECAMP", "EHIFSE", "RECALS", "ENTDOS", "OFXRIA", "NAVEDZ", "EIOATA", "GLENYU", "BMAQJO", "TLIBRA", "SPULTE", "AIMSOR", "ENHRIS")
Randomize
Do While WorksheetFunction.CountA(Sheets("feuil1").Range("grille")) < 16
    cpt = WorksheetFunction.CountA(Sheets("feuil1").Range("grille"))
    Do
        AleaLig = (5 - 2) * Rnd() + 2 ' 5 = dernière ligne de la grille, 2 = première ligne
        AleaCol = (7 - 4) * Rnd() + 4 ' 7 = dernière colonne de la grille, 4 = 1ère colonne
    Loop While Sheets("feuil1").Cells(AleaLig, AleaCol) <> ""
    Do
        carac = CInt((6 * Rnd()) + 1)
    Loop While carac > 6 Or carac < 1
    Sheets("feuil1").Cells(AleaLig, AleaCol).Value = Mid(Cubes(cpt), carac, 1)
Loop
End Sub
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
10 févr. 2014 à 10:52
Pas vraiment d'accord avec ce tirage qui :
- prend les dés toujours dans le même ordre , ce qui n'est pas très "déontologiquement" aléatoire, même si est aléatoire la cellule d'attribution
- oblige entre autres à retirer "jusqu'à plus soif" lorsque alealig,aleacol a déla servi.
Je te propose ceci : 
cubes = Array("ETUKNO", "EVGTIN", "IELRUW", "DECAMP", "EHIFSE", "RECALS", "ENTDOS", "OFXRIA", "NAVEDZ", "EIOATA", "GLENYU", "BMAQJO", "TLIBRA", "SPULTE", "AIMSOR", "ENHRIS")
  touille_cubes cubes '================> voir cette proc plus bas
  Randomize
  For Each Cel In grille
      Do
          carac = CInt((6 * Rnd()) + 1)
          If carac < 6 And carac > 1 Then Cel.Value = Mid(cubes(cpt), carac, 1)
      Loop While Cel.Value = ""
      cpt = cpt + 1
  Next Cel
avec cette procédure : 
Private Sub touille_cubes(ByRef cubes)
 Dim i As Integer, nb As Integer, ou As Integer, temp As String
 nb = UBound(cubes)
 For i = 0 To nb / 2
   ou = Int(((15 - i) * Rnd))
   temp = cubes(ou)
   cubes(ou) = cubes(nb - i)
   cubes(nb - i) = temp
 Next
End Sub

Ce qu'elle fait : elle touille tout simplement les dés avant le tirage. Leur ordre devient donc améatoire
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
10 févr. 2014 à 11:01
Merci.
Ce n'est pas tant l'aspect "déontologique" qui me gênait, mais surtout l'obligation de retirer "jusqu'à plus soif".
Ton alternative est parfaite pour ce souci.

Autre chose qui me "dérange" dans ce bout de code, c'est le tirage du dé. Lorsque l'on fait 
CInt((6 * Rnd()) + 1)
, on obtient des chiffres entre 1 et 7... N'y a t'il pas une autre méthode pour n'obtenir que des chiffres compris entre 1 et 6??
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
10 févr. 2014 à 11:09
Deux détails également me posent question :
1- dans ta procédure touille_cubes, tu utilises Rnd sans avoir au préalable Randomize. Normal?
2- Une erreur de mon fait, dans cette ligne : 
If carac < 6 And carac > 1
. Il convient de remplacer les supérieur et inférieur stricts par supérieur ou égal et inférieu ou égal : 
If carac <= 6 And carac >= 1
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 10/02/2014 à 11:14
Oui (écrit trop vite) ===>>
CInt((5 * Rnd()) + 1)

et du coup : 
cubes = Array("ETUKNO", "EVGTIN", "IELRUW", "DECAMP", "EHIFSE", "RECALS", "ENTDOS", "OFXRIA", "NAVEDZ", "EIOATA", "GLENYU", "BMAQJO", "TLIBRA", "SPULTE", "AIMSOR", "ENHRIS")
  touille_cubes cubes
  Randomize
  For Each Cel In grille
      Do
          carac = CInt((5 * Rnd()) + 1)
          Cel.Value = Mid(cubes(cpt), carac, 1)
      Loop While Cel.Value = ""
      cpt = cpt + 1
  Next Cel
puisque la verif "If carac < 6 And carac > 1 Then " est alors inutile
0
Réponse 6 / 71
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
6 févr. 2014 à 15:29
Re-

Le second code est celui permettant de retirer des mots de la liste, si une des lettres qui le compose est dans la liste des lettres manquantes. 

Sub RetirerMotsLettresManquantes()
Dim lettresutilisees(), lettresmanquantes()
Dim ListeMotsTemp() As String, Lettr$, mot$
Dim i&, j&, k&, test As Boolean
Dim MonDico1 As Object, MonDico2 As Object, c

lettresutilisees = Range("grille") '-----> Menu Insertion/Noms/Définir
Set MonDico1 = CreateObject("Scripting.Dictionary")
For Each c In lettresutilisees
    MonDico1(c) = ""
Next c
Set MonDico2 = CreateObject("Scripting.Dictionary")
For Each c In Array("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")
    If Not MonDico1.exists(c) Then MonDico2(c) = ""
Next c
lettresmanquantes = Application.Transpose(MonDico2.keys)
ListeMotsTemp = ListeMots
Erase ListeMots
For i = 0 To UBound(ListeMotsTemp)
    mot = ListeMotsTemp(i)
    For j = 1 To UBound(lettresmanquantes)
        Lettr = lettresmanquantes(j, 1)
        If InStr(mot, Lettr) = 0 Then
            test = True
            Exit For
        End If
    Next j
    If test = False Then
        ReDim Preserve ListeMots(k)
        ListeMots(k) = ListeMotsTemp(i)
        k = k + 1
    End If
Next i
End Sub
0
Réponse 7 / 71
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
Modifié par pijaku le 6/02/2014 à 16:49
Re-

Ici je souhaites voir avec vous comment extraire les mots se trouvant dans ce dictionnaire (pour info il s'agit du fichier fr.dic disponible avec Firefox... Je n'ai pas été cherché bien loin), pour les placer dans une variable de mon classeur...

http://cjoint.com/?DBgpIuve868

Première question, au vu des données, vous travailleriez avec un objet dictionary ou une variable tableau?

Voici un code réalisé grâce à Internet : 
Sub Dictionnaire()
Dim Tb() As String, Chemin As String, num As Long, i As Long

Chemin = ThisWorkbook.Path
num = FreeFile
Open Chemin & "\DicoFirefoxFrancais.txt" For Input As #num
i = -1
While Not EOF(1)
  i = i + 1
  ReDim Preserve Tb(i)
  Line Input #1, Tb(i)
Wend
Close #num
End Sub


Maintenant, il faut traiter le résultat...
Or, le créateur du dico Firefox n'a pas mâché mon "travail". En effet, il n'y a, dans le fichier txt proposé, aucun retour chariot...
Donc, dans le code donné ci-dessus, 
UBound(Tb) = 0
...

Cordialement,
Franck
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
Modifié par pijaku le 7/02/2014 à 11:02
Voici ce que j'ai pu faire pour "traiter" les données issues du dictionnaire Firefox.

1- La procédure
Le début n'a que peu changé. J'ai juste ajouté un Timer pour chronométrer le temps d'exécution.

Par contre, comme le fichier txt ne comprends qu'une seule ligne, pour n'obtenir que des mots à l'arrivée, il a fallut scinder cette ligne.
La ligne est représentée dans le code par Tb(0).
Scindée :
- en séparant grâce aux "/" (Ligne 20 du code)
- en séparant grâce à des espaces insécables (Chr(9) Ligne 22 du code)
- en séparant grâce à des "passages à la ligne" (Chr(10) Ligne 23) 

Option Explicit

Dim ListeMots

Sub Dictionnaire()
Dim Tb() As String, Chemin As String, num As Long, i As Long, PremierJet() As String
Dim Start As Single

Start = Timer
Chemin = ThisWorkbook.Path
num = FreeFile
Open Chemin & "\DicoFirefoxFrancais.txt" For Input As #num
i = -1
While Not EOF(1)
  i = i + 1
  ReDim Preserve Tb(i)
  Line Input #1, Tb(i)
Wend
Close #num
PremierJet = Split(Tb(0), "/")
For i = LBound(PremierJet) To UBound(PremierJet)
    PremierJet(i) = Split(PremierJet(i), Chr(9))(1)
    PremierJet(i) = Split(PremierJet(i), Chr(10))(1)
    PremierJet(i) = RemplaceCarSpec(PremierJet(i))
Next i
ListeMots = Affine(PremierJet)
MsgBox "Enregistrement en mémoire de : " & UBound(ListeMots) & " mots, en : " & Timer - Start & " secondes."
End Sub


Ainsi scindée, nous obtenons une variable tableau composée de mots...
Ou presque.
En fait, il reste des chiffres dans certains mots (ex : 1er = premier) et les caractères spéciaux.

2- Les Fonctions :
Nous allons donc traiter ces mots grâce à deux fonctions :

Fonction n°1 : RemplaceCarSpec (appel Ligne 24 du code) : 
Function RemplaceCarSpec(monMot As String)
Dim motTemp As String
motTemp = Replace(monMot, "é", "e")
motTemp = Replace(motTemp, "ï", "i")
motTemp = Replace(motTemp, "è", "e")
motTemp = Replace(motTemp, "-", "")
motTemp = Replace(motTemp, "ç", "c")
motTemp = Replace(motTemp, "ë", "e")
motTemp = Replace(motTemp, "ê", "e")
motTemp = Replace(motTemp, "ü", "u")
motTemp = Replace(motTemp, "â", "a")
motTemp = Replace(motTemp, "ä", "ae")
motTemp = Replace(motTemp, "ô", "o")
motTemp = Replace(motTemp, "ÿ", "y")
motTemp = Replace(motTemp, "î", "i")
motTemp = Replace(motTemp, "Å""", "oe")
motTemp = Replace(motTemp, "û", "u")
motTemp = Replace(motTemp, "æ", "ae")
motTemp = Replace(motTemp, "Ã¥", "a")
motTemp = Replace(motTemp, "ö", "o")
motTemp = Replace(motTemp, "Ã", "a")
motTemp = Replace(motTemp, "É", "e")
motTemp = Replace(motTemp, "È", "e")
motTemp = Replace(motTemp, "Ã...", "a")
motTemp = Replace(motTemp, "Å'", "oe")
RemplaceCarSpec = UCase(motTemp)
End Function

Comme son nom l'indique, elle remplace les caractères spéciaux...

Fonction n°2 : Affine (Appel Ligne 26 du code de la Sub Dictionnaire) 
Function Affine(Tbl)
Dim TbTemp(), i As Long, CptTbNum As Long, CptTemp As Long

For i = LBound(Tbl) To UBound(Tbl)
    If Len(Tbl(i)) > 2 And Len(Tbl(i)) < 17 Then
        If Not IsNumeric(Right(Tbl(i), 1)) And Not IsNumeric(Left(Tbl(i), 1)) Then
            ReDim Preserve TbTemp(CptTemp)
            TbTemp(CptTemp) = Tbl(i)
            CptTemp = CptTemp + 1
        End If
    End If
Next i
Affine = TbTemp
End Function

Cette fonction est un peu particulière car nous lui passons une variable tableau en paramètre, et elle nous retourne une variable tableau.
Elle sert à deux traitements :
- La longueur des mots (de 3 à 16 lettres) (cf ligne 5 du code)
- S'ils comportent des caractères numériques en début ou en fin de mot (ligne 6)

Voilà.
A vos avis.
Peut-on notamment améliorer la vitesse d'exécution?
Utilisation d'un objet dictionary?
Autre méthode?
0
Réponse 8 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 6/02/2014 à 17:54
Bonjour,
je ne connais pas ce jeu (ne suis pas joueur), mais tout me parait défini dans ce que je lis ici :
"Chaque joueur cherche des mots pouvant être formés à partir de lettres adjacentes du plateau. Par «adjacentes», il est sous-entendu horizontalement, verticalement, ou en diagonale. Les mots doivent être de 3 lettres au minimum, peuvent être au singulier ou au pluriel, conjugués ou non, mais ne doivent pas utiliser plusieurs fois le même dé pour le même mot."
A partir de là, si j'ai bien compris :
- tu as une grille composée aléatoirement de 16 lettres
- tu veux chercher si, en suivant un chemin horizontal, vertical ou diagonal tu peux composer un (ou plusieurs) mot(s) d'une liste préexistante.

Des précisions me manquent pour réfléchir :
1) chaque chemin peut-il être parcouru à l'envers ? (exemple dans "amonbc" : ai-je le mot "mon" uniquement ou également le mot "nom" ?)
2) les directions sont-elles "rigides" ou non ?
J'entends par rigide une direction qui, une fois prise, impose qu'elle reste une droite et non un parcours en zig-zag

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
Réponse 9 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 6/02/2014 à 18:17
Pour que tu comprennes bien mes questions :
Prenons l'exemple d'un jeu d'échecs :
- la reine peut s'y déplacer d'un point à un autre dans toutes les directions, mais une seule pour chacun de ses déplacements. Elle n'est pas autorisée à suivre, dans l'un de ses déplacements, un chemin en "zigzag" entre cellules contigües. C'est cela, que l'appelle la rigidité d'un déplacement.

Pour être plus clair :
regarde cette grille :
T P U C
F A O R
A O I J
I X M N
et dis-moi (réponse oui ou non) si tes règles font que le mot PAIX y est une solution admise.

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
6 févr. 2014 à 18:31
Salut,

Pour répondre clairement, oui. PAIX figure dans les réponses possibles, et, si on trouve le mot MON, NOM figurera également parmi les réponses possibles.
D'autres, dans la grille que tu proposes, seraient :
COUPAT
JOUR
MIAOU (à condition qu'il soit dans le dictionnaire)
PAT
PUAT
JOIN
MOI
PURIN
ROI
FAX
FAI (si fournisseur d'accès internet est dans le dico...)
FAIM
etc...
En fait, le chemin se fait en zigzag, en ligne droite ou en un mixe des 2, peu importe, l'important étant qu'une "case" ne peut être utilisée qu'une seule fois par mot. Dans l'exemple précédent, PAIX utilise le P et le A de COUPAT. Les 2 mot sont bons. Par contre, on ne peut pas faire le mot COURIR car le même R serait utilisé 2 fois...

Dis moi, tu t'attaques directement au noeud de mon problème, la fonction récursive qui cherche les mots dans la grille?

En fait, cette étape, que je réservais pour la fin, je souhaite vraiment la construire, ensemble, de A à Z. Y compris par l'établissement au préalable de l'algorithme etc... Vraiment ne louper aucune étape, car je compte m'en servir pour m'exercer à la récursivité...
Tout cela, tu l'auras compris, dans un but pédagogique pour moi, mais également pour les internautes.
0
Réponse 10 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
6 févr. 2014 à 20:35
"Dis moi, tu t'attaques directement au noeud de mon problème"
Oui. Et ne n'est pas par hasard.
Je t'explique :
- je suis fondamentalement "émotif-actif-primaire" (défaut ou qualité ? On va voir)
- le "noeud" d'un problème est pour moi à la fois ce que l'on doit faire en amont pour le traiter/définir/arrêter et ce que l'on "voit" d'utile en lui pour l'utiliser en aval.
Alors, ma foi ... je reste avec mes "élans" incontrôlés et ma pauvre "vision" très personnelle des ensembles.

Ton problème n'est pas simple, compte tenu de plusieurs aspects, parmi lesquels un nombre assez impressionnant de chemins possibles en partant de chacune des lettres de la grille, d'une part et, d'autre part, du fait qu'un "dé" utilisé ne peut l'être qu'une seule fois.****
Il importe de réfléchir très calmement à tout, avant de décider d'une méthode.
Il importe également de ne pas perdre de vue que cette appli est sous VBA/.Excel et que cette particularité pourrait conduire à certaines méthodes que ne permettraient ni VB6 ni VB.Net (qui imposeraient entre autres le traitement d'un tableau dynamique, sans autre possibilité).

*** à ce propos : je ne vois pas dans les "règles" s'il ne peut être utilisé qu'une seule fois en tout et pour tout, ou s'il ne peut être utilisé qu'une seule fois dans un chemin parcouru ====>> va falloir le préciser.

J'attends tes précisions avant de commencer à faire travailler mes pauvres neurones. Je sais d'ores et déjà que le temps de ma réflexion sera bien plus important que celui, une fois arrêtée ma "réflexion", du développement du mécanisme décidé.
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
6 févr. 2014 à 21:25
Bonsoir, je ne vous embêterais pas beaucoup, ne faisant du VBA qu'en dilettante.
Il existe un dictionnaire du scrabble (ODS) dont certaine version se trouve en fichier texte, ici par exemple.
Bon il n'y a peut être pas les mots de 15 lettres, difficiles au scrabble!

Il importe également de ne pas perdre de vue que cette appli est sous VBA/.Excel et que cette particularité pourrait conduire à certaines méthodes que ne permettraient ni VB6 ni VB.Net (qui imposeraient entre autres le traitement d'un tableau dynamique, sans autre possibilité).

Oui, mais en .Net il y a Linq...
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
6 févr. 2014 à 22:14
Bonjour, Whismeril,
Linq (ou alors tu voudras bien m'expliquer comment) ne permettra d'éviter ni l'utilisation forcée et rigide d'un tableau dynamique, ni celle de boucles imbriquées sur ce tableau. En d'autres termes, ce ne sera certes pas linq qui pourra permettre les repères nécessaires pour diminuer de manière significative le nombre de "chemins" à poursuivre et encore moins celui des "dès" déjà utilisés !
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
6 févr. 2014 à 23:40
Ça ne solutionnera sans doute pas tout, mais ça peut facilement faire un premier tri dans le dictionnaire, en sortant une liste de tous les mots possible avec les lettres présente utilisée une seule fois.
Ça réduirait de manière significative le temps d'exécution sur la partie calculant les chemins possibles.

Pour ce calcul, on peut partir d'une case puis se déplacer dans une direction (donc deux lettres) et chercher dans la liste réduite les mots commençant par ces 2 lettres, et ainsi de suite. Si on trouve un mot on le stocke, et on continue jusqu'à ce qu'il n'y ait plus de mot possible.
On remote ensuite d'un noeud et on prend une direction différente, etc.

Je ne dis pas que c'est simple, mais c'est une piste.

Une autre utilisation possible de Linq serait le chargement du dictionnaire.
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 7/02/2014 à 06:54
"Pour ce calcul, on peut partir d'une case puis se déplacer dans une direction (donc deux lettres) et chercher dans la liste réduite les mots commençant par ces 2 lettres, et ainsi de suite. Si on trouve un mot on le stocke, et on continue jusqu'à ce qu'il n'y ait plus de mot possible.
On remote ensuite d'un noeud et on prend une direction différente, etc"
C'est dans tout ce qui est ici souligné, que réside la seule vraie difficulté. Linq n'"a rien à y "voir" (dans ces soulignés). Et c'est probablement là (ces soulignés) que l'on pourrait tenter de faire appel à des fonctionnalités de Excel (ses objets) et VBA/Excel (manipulations de plages; de tableaux, de propriétés de cellules, etc...) que n'offrent ni VB6 ni VB.Net.
Et cette utilisation de Excel et de son VBA pourraient peut-être aider à répondre plus agilement à cette partie ( ces soulignés-là) :
"du fait qu'un "dé" utilisé ne peut l'être qu'une seule fois"
Tout cela demande selon moi une réflexion liminaire très fine et approfondie avant de commencer quoi que ce soit.

PS : lorsque je parle (s'agissant de Excel et non de son VBA) de "ses objets", c'est au fait qu'ils ont plusieurs propriétés utilisables, que je pense en premier. Ces propriétés pourraient probablement être utilisées (depuis VBA) là où VB6 et VB.Net n'auraient d'autre choix que celui de stockages de données complémentaires.
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
7 févr. 2014 à 09:25
Bonjour Messieurs,

Pour répondre aux questions posées, un dé ne peut être utilisé qu'une seule fois, dans un même mot (donc dans un chemin). Une fois le mot composé, les dés sont de nouveau tous réutilisables.

En fait, il n'y a que 2 règles (mais au combien contraignante pour nous) :
Un mot peut être formé :
- en utilisant des lettres adjacentes (horizontales, verticales, diagonales)
- en n'utilisant qu'une fois le même dé.

Prenons un exemple :


Dans cet exemple, nous ne pouvons pas former le mot CECI, car il utiliserai pour cela 2 fois le C situé en C3.
Par contre, nous pouvons former CHIEN (C3,B3,C2, D2,D2), puis COR (C3, D3, E3), puis BUT (B5,C5, C4), puis COMMIS (C3, D3, D4, E4 et E5). Attention toutefois, pour le mot COMMIS, à ne pas utiliser 2 fois le M en D4.
Pour illustrer un dernier chemin, CHIOTS est un bon exemple : C3, B3, C2, D3, C4, D5.

Analysons comment le code pourrait trouver le mot CHIOTS.
On lui soumet le mot complet CHIOTS, à lui de voir s'il peux le former dans la grille.
Il devrait donc :
1- Boucler sur toutes les lettres du mot, jusqu'à ce que :
> soit on arrive à une impasse (cf les tests dans l'étape 2)
> soit on arrive à la dernière lettre
Supposons 3 lettres qui se suivent dans un mot N, N+1 et N+2
2- La lettre N trouvée, il faut [stocker son "adresse"]* puis analyser les cellules voisines, pour y chercher la lettre suivante N+1. 2 choix :
> on trouve la lettre N+1 ==> On recommence l'étape 2 avec les lettres N+1 et N+2
> on ne la trouve pas. Dans ce cas [on "déstocke" son "adresse"]**
--> Si la lettre N est la première du mot, on la cherche ailleurs dans la grille. Si on la trouve ==> On recommence l'étape 2 avec les lettres N et N+1. Si on ne la trouve pas, le mot n'est pas possible à former.
--> Si la lettre N n'est pas la première du mot, on "remonte" à la lettre N-1 et on recommence l'étape 2 avec N-1 et N.

* pour ne pas utiliser 2 fois le même dé dans un même mot
** par adresse j'entends essentiellement 2 possibilités :
- soit on numérote au préalable les dés de 1 à 16
- soit on utilise l'adresse des objets Range de la plage "grille"

Dans ce cheminement, la récursivité apparait clairement :
- instructions du point d'arrêt = Etape 1,
- instructions, Etape 2
- appel récursif avec le changement des paramètres selon résultat de l'étape2

@ Whismeril : même si tu ne pratiques VBA qu'en dilettante, ton aide est précieuse. Jusqu'à l'établissement de l'algorithme final, peu importe le langage de programmation. Non?
Et puis, plus on est de cerveaux, mieux c'est.

@ucfoutu : vas y, lâche toi dans tes élans incontrôlés. ;-) ... mais fait nous part de tes visions ô combien éclairante.
0
Réponse 11 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 7/02/2014 à 22:39
Je me suis pris au jeu, j'avance bien, mais voilà que j'ai des états d'âme fondamentaux qui m'empêchent de continuer sans une réponse très précise relative aux règles mêmes de ce jeu !
Exemple avec cette grille, dans laquelle je recherche le mot "PAIX" : 
A P V X
Y A P I
I K I X
O X W Z
On y voit très clairement que ce mot y est trouvé plusieurs fois.
Et dans un tel cas : combien de mots trouvés comptabilises-tu (pour le score) ? Un seul ou tous ?
Il va de soi que ma continuation dépend GRANDEMENT de la réponse précise à cette question (car la suite du traitement diffère terriblement dans un cas et dans l'autre !)



________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
Modifié par pijaku le 8/02/2014 à 09:11
Bonjour,

Aucune indication n'est donnée dans la règle du jeu.
Cependant, on peut déduire de ceci :
Lors du calcul des points, chaque joueur lit à haute voix les mots trouvés. Si deux joueurs ou plus ont trouvé le même mot, il est rayé des listes le contenant.
que les mots doivent être unique.
Pour moi, PAIX ne peut compter qu'une seule fois.

EDIT : trouvé ICI : Un même mot peut être formé dans différents endroits de la grille, il ne comptera qu'une fois. Comme ça c'est clair.
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
8 févr. 2014 à 10:44
Voilà qui va me faciliter grandement le travail. Bonne nouvelle.
Je m'y replongerai ce soir.
0
Réponse 12 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 8/02/2014 à 21:06
Des nouvelles, quand-même ...
1) Tous mes essais faits de manière "conventionnelle", tant en récursivité qu'en procédures successives (en remontant les "noeuds") se traduisent par un temps d'exécution extrêmement long, compte tenu des possibilités de chemin en zigzag et des "combinaisons possibles" de chemins (sans parler du contrôle de la non réutilisation d'une cellule déjà utilisée dans le chemin) ===>>> A abandonner donc, sans la moindre hésitation.
2) je me suis donc dirigé (mon premier "élan" instinctif, que j'aurais dû suivre d'entrée de jeu) vers l'utilisation des objets Excel. Je n'ai pas terminé (loin s'en faut), mais je suis déjà parvenu à réduire considérablement (à moins du quart) le nombre des itérations qu'il faudra exercer. C'est déjà pour le moins appréciable et cela va nous donner une base bien plus réduite sur laquelle travailler.
Je reprends cette tâche demain (là, j'ai le tournis).

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
9 févr. 2014 à 09:44
Bonjour,

J'ai également eu une autre idée...
Mais bon, là c'est dimanche, et, famille oblige, je ne pourrais pas la creuser. Je tente ça demain et vous tiens informés.

Je reprends cette tâche demain (là, j'ai le tournis). C'est dimanche pour toi aussi, alors : repos... Le problème sera encore là demain!
Merci de ton implication, ça fais plaisir.

Amicalement,
Franck
0
Réponse 13 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
9 févr. 2014 à 10:38
Une remarque à propos de cette partie :
"Je n'ai, pour l'instant, fait qu'enlever les mots dont une des lettres ne fait pas partie de la liste des lettres contenues dans la grille. "
Elle n'est pas vraiment adroite.
Pourquoi ,? ===>>
parce-qu'elle nécessite à elle-seule une boucle préalable sur la liste totale des mots (en vue de retirer ceux "impossibles" en fonction de la grille). Or, elle aboutit certes à ,une liste X réduite, mais, pour la suite de ton traitement, tu vas devoir re-parcourir les mots de cette liste X (que tu avais déjà parcourus) ===>> soit nb leur nombre : tu auras ainsi parcouru 2 fois ces nb mots.
Pour être clair : soit une liste de départ de 20000 mots épurée à 600. De la manière dont tu procèdes, le nombre total de mots parcourus est dont : 20600.
Il vaut peut-être mieux traiter directement lors du premier parcours, et de d'autant que pour la même grille, un mot peut être trouvé "impossible" d'entrée de jeu. Dans ce cas-ci, par exemple :
la grille contient bien toutes les lettres du mot, mais, pour chaque lettre du mot, ne contient pas un nombre au moins égal au nombre de cette lettre dans le mot. Or, mes petits tests font ressortir que telle est la situation de très loin la plus fréquente.
Or, cette méthode qui consiste à "ignorer" un mot d'entrée de jeu ne saurait (par définition) s'appliquer globalement, puis cette décision d'ignorer est différente selon chaque mot.
Je vais continuer sur cette base, donc.
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
10 févr. 2014 à 08:24
Bonjour,

la grille contient bien toutes les lettres du mot, mais, pour chaque lettre du mot, ne contient pas un nombre au moins égal au nombre de cette lettre dans le mot.
L'idée est très intéressante. Je n'y ai jamais songé.
Il est vrai que l'épuration doit être maximale et réalisée en une seule fois.

Cependant, je voulais également, dans cette appli, "répartir" les longs temps de traitement VBA.
Je pensais à réaliser quelque chose comme cela :
1- à l'ouverture du classeur : chargement du dictionnaire
2- à chaque tirage (clic sur bouton tirage) : épuration du dictionnaire
3- à chaque clic sur le bouton "Solutions" : calcul des combinaisons possibles.
Ceci afin d'éviter les temps de chargement trop long pour l'utilisateur.
Mais s'il y a un quelconque moyen d'alléger l'appli, ne surtout pas hésitr.
0
Réponse 14 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 9/02/2014 à 16:45
Une chose m'inquiète par ailleurs, au niveau du remplissage aléatoire de la grille de jeu :
tel que tu le fais, il n'est pas exactement aléatoire, dans la mesure où la case A1 puise toujours parmi ETUKNO, la case A2 toujours parmi IELRUW, etc ...
Est-ce VOULU (une REGLE du jeu) ou une erreur ?
Si vraiment voulu, n'en parlons plus
Si erreur : je la corrige dès ta réponse

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
Modifié par pijaku le 10/02/2014 à 08:30
Salut ucfoutu.

Pour cette question, il y a 16 dés dont les faces sont ETUKNO, IELRUW etc... Normalement, dans le jeu réel, les dés "tombent" sur une "case" de la grille aléatoirement. Il faut également le faire, C'est un aspect que j'avais zappé... Je m'en occupe de suite...
Il existe également des variantes du jeu informatiques qui utilisent un Random pour chaque dé sur l'alphabet en totalité. Cependant, je trouve que l'esprit du jeu n'est plus respecté.
A noter également qu'il existe une variante avec une grille de 5x5...
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
10 févr. 2014 à 09:22
La correction du code de tirage aléatoire ICI
0
Réponse 15 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
9 févr. 2014 à 22:12
Bonsoir, Whismeril;
je ne comprends pas bien ton truc, là :
"Je commence par le dé en haut à gauche, je cherche les dés adjacents, j'en choisi un.
S'il existe des mots qui commence par ces deux lettres, je réduit le dico à ces mots (très gros gain de temps dans les recherches!)
je recherche les adjacents en excluants les deux premiers dés et ainsi de suite de manière récursive. "
C'est ce que j'ai souligné, qui m'interpelle ...
Rassure-moi : tu recommences ensuite la totalité de cette opération en partant de chacune des autres cases ?
0
Réponse 16 / 71
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
Modifié par Whismeril le 9/02/2014 à 23:05
Bonsoir,

si la première ligne A B C D,

Je prends, A, je filtre le dictionnaire par les mots commençant par A (6620 entrées contre 72192 au départ).
Parmi les adjacents je choisis B, il y a 359 mots commençant par AB, on continue sur ce chemin.
Je choisis ensuite C, il reste 3 mots commençant par ABC, on continue.
Enfin je choisi D, il n'y a aucun mots commençant par cette suite, je remonte d'un noeud et change de direction on recommence.

J'ai comparé avec la force brute sur trois caractères, c'est plus rapide dans la mesure ou il n'y a pas autant de mots qu'il y a de chemins possibles.
Dans les essais que j'ai fait ça ne c'est pas présenté. Il y a 408 chemins de 3 lettres et je n'ai jamais trouvé plus d'une trentaine de mots de 3 lettres, en comprenant les doublons.

Penser aux balises de coloration syntaxique: bouton <>, préciser le langage :<code csharp>.
Quand la solution est trouvée, mettre la discussion Résolue.
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
9 févr. 2014 à 23:08
Dans la méthode de recherche récursive, j'ai laissé trainé un bout de code en trop 
               int i;
                if (monChemin.Texte == "LUNE") 
                    i = monChemin.Des.Count;

Je m'en servais pour déboguer, j'avais mis une grille ou il devait trouver lune, un point d'arrêt sur ce bout de code et je voyais comment ça se passait.
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 9/02/2014 à 23:15
Et tu ne recommences pas en commençant par B plutôt que par A, puis par C, etc ... jusqu'à commencer par P (et chaque fois tout reprendre au début) ?
Car si tu ne le fais pas ...tu as mal lu les règles du jeu.
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
10 févr. 2014 à 06:45
Je commence par explorer tous les chemins qui débutent par A.
Ensuite je passe à B, puis C ....
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
10 févr. 2014 à 07:37
Cette méthode, passe en revue chaque dé de la grille, et lance la recherche récursive à partir de chacun d'entre eux 

        /// <summary>
        /// Calcul tous les chemins de dés possibles par récursivité
        /// </summary>
        private List<Chemin> CalculCheminsRecursif()
        {
            List<Chemin> chemins = new List<Chemin>();

            foreach (De d in tires)//ici chaque dé
            {
                Chemin monChemin = new Chemin();
                monChemin.Des.Add(d);
                RechercheRecursive(monChemin, chemins, MonDico.Liste.FindAll(m => m.StartsWith(monChemin.Texte)));//lance la recherche récursive sur la liste de mots commençant par la lettre en cours
            }

            Solutions = (from c in chemins
                         select c.Texte).ToList<string>();

            return chemins;
        }
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
10 févr. 2014 à 07:41
Celle ci cherche tous les chemins possibles à partir de la lettre de départ.
Dés que le chemin fait plus de 3 dés on regarde si on peut stocker le mot. 
        /// <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="chemins">Liste des chemins valide</param>
        /// <param name="dico">dictionnaire appuré à chaque instance</param>
        private void RechercheRecursive(Chemin chemin, List<Chemin> chemins, List<string> dico)
        {
            List<De> adjacents =chemin.DernierDe.Adjacents(tires, chemin.Des);//recherche des adjacents
            if (adjacents.Count == 0) return;//s'il n'y en a plus on remote d'un niveau

            foreach (De d in adjacents)
            {
                Chemin monChemin = chemin.Clone();//je clone le chemin car à chaque instance récursive il m'en faut un dédié
                monChemin.Des.Add(d);// j'ajoute le dé en cours 

                if (monChemin.Texte.Length > 2 && !chemins.Exists(m => m.Texte == monChemin.Texte) && dico.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);

                List<string> dicoReduit = dico.FindAll(m => m.StartsWith(monChemin.Texte));
                if (dicoReduit.Count > 0)
                    RechercheRecursive(monChemin, chemins, dicoReduit);//s'il existe des mots commencant par cette sequence on continue
                else
                    continue;//sinon on passe au dé adjacent suivant

            }
        }
0
Réponse 17 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 11/02/2014 à 08:27
Tiens, puisque l'on parle des règles du jeu ...
Une autre précision manque (et elle n'est pas négligeable du tout, car elle conditionne également le développement, de manière cruciale) :
Prenons par exemple le mot trouvé "MAINTENANT" sur un chemin x
Combien de mots sont à comptabiliser pour ce chemin ?
- un seul, le plus long (MAINTENANT) ?
- ou huit (MAI,MAIN, MAINTE, TENANT, NET,NIA,ANE,ANET,) ?
Et c'est même plus complexe lorsque la dernière lettre du mot le plus long est à une case de la première).
Alors ? Comment fait-on, ... ?

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
11 févr. 2014 à 08:29
Salut ucfoutu,

8 sont à comptabiliser : les 7 + maintenant.
Et selon, tu peut également trouver TENIA...
En fait, le chemin n'est valide que pour le mot "en cours". Il est réinitialisé à la fin de chaque mot trouvé.
Par conséquent, dans la grille ci dessous, tu trouves MAIN, réinitialise le chemin, et tu peux trouver MAINS. Ces deux mots sont comptabilisés...
M A I N
T U N S
Y P Z C
V B N J

Également une question subsidiaire réside dans les noms propres... Acceptés ou non?
Cela dépends de ce que nous choisirons, cette règle n'étant pas précisée.
Dans ton cas, on ajoutera AIN, ou pas...
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
11 févr. 2014 à 08:38
tu trouves MAIN, réinitialise le chemin, et tu peux trouver MAINS. Ces deux mots sont comptabilisés


J'ai appliqué ce principe en créant un clone de chemin à chaque récursion (ça se dit récursion?). Ainsi si MAIN existe dans le dictionnaire, il est stcoké comme un premier chemin, que je clone et auquel j'ajoute le S, ect....
0
Réponse 18 / 71
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
Modifié par ucfoutu le 13/02/2014 à 08:44
A Pilaku :
Je viens, en tentant une autre approche, de m'apercevoir que ton dico contient des mots avec apostrophe. Il faut supprimer ce signe.

PS ; je m'en suis aperçu en comptabilisant (une fois pour toutes et en utilisant asc(65) ) le nombre de chaque lettre de chaque mot.
En précisant que j'importe le dico dans excel, ainsi que cette comptabilisation. Cette moulinette prend plusieurs minutes, mais n'est faite qu'une seule fois, puisque le classeur est ensuite enregistré et garde donc une fois pour toutes ces données. Ces données sont donc déjà présentes dès que l'on ouvre le classeur distribué.

l'apostrophe n'étant sur aucun des dés ===>> une décision est à prendre à propos de ces mots. ===>>
soit on ne les accepte pas du tout
soit on les accepte sans l'apostrophe (et on supprime alors l'apostrophe dans le dico).


________________________
Réponse exacte ? => "REPONSE ACCEPTEE" facilitera les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement répéter son contenu. Je n'interviend
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
13 févr. 2014 à 08:41
Bonjour,

Je fais ça en priorité, ce matin. Je reviens ici avec un fichier txt "cleanifié" de toutes apostrophes.
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
13 févr. 2014 à 08:46
Pas la peine de le nettoyer ! Une simple moulinette fait cela à partir du dico déjà communiqué.
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
Modifié par pijaku le 13/02/2014 à 08:59
Ok.
Pour répondre à ta question : on les accepte sans l'apostrophe (et on supprime alors l'apostrophe dans le dico).

Tu dis :
PS ; je m'en suis aperçu en comptabilisant (une fois pour toutes et en utilisant asc(65) ) le nombre de chaque lettre de chaque mot.
En précisant que j'importe le dico dans excel, ainsi que cette comptabilisation. Cette moulinette prend plusieurs minutes, mais n'est faite qu'une seule fois, puisque le classeur est ensuite enregistré et garde donc une fois pour toutes ces données.
Ton classeur n'est pas trop "lourd"? 3-4 Mo? plus?
0
ucfoutu Messages postés 18038 Date d'inscription lundi 7 décembre 2009 Statut Modérateur Dernière intervention 11 avril 2018 211
13 févr. 2014 à 10:57
Il devient inévitablement plus lourd, puisqu'il contient autant de lignes que le dico sur 27 colonnes entièrement remplies.
L'avantage serait :
- de ne pas refaire tous les calculs, délà faits une fois pour toutes à l'ouverture du classeur
- de pouvoir jouer pour le reste de la prog avec les agilités de Find, countif et counta
Il me serait possible de passer de 27 colonnes à 2 seulement, mais cela impliquerait une lenteur ajoutée (un split) à chaque "examen"
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
13 févr. 2014 à 12:37
Je viens de réaliser cette feuille "Dictionnaire" comportant 27 colonnes sur 300 000 et quelques lignes.
Le poids du classeur est de 13Mo.
Ca ne gène pas?
Perso ça me trouble un peu. Lorsque je vois un classeur de cette taille sur le Net, je ne télécharge pas... Alors, de là à l'utiliser moi-même...

Une solution alternative à laquelle je pense est d'utiliser une bdd Access, juste pour cette feuille. Tu en penses quoi?
0
Réponse 19 / 71
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 14
14 févr. 2014 à 14:59
Re-

J'ai une solution relativement stable...

Dites moi ce qu'il convient de faire?

Mon avis : attendre tranquillement qu'ucfoutu rentre de la pêche, le féliciter pour ses prises du jour, attendre qu'il ait sa solution et tester chacun son appli.
Si vous préférez que je donne directement ma solution, pas de souci. Je préfères attendre, pour ne pas gêner la réflexion d'ucfoutu (c'est toujours un peu troublant de lire un code en en cherchant un autre...).

Vous dites...
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
14 févr. 2014 à 18:14
Salut, ça me va, tout comme Uc je fais ça pour m'amuser entre deux journées de boulot (j'irai à la pêche quand je serais retraité moi aussi)!

Je travaille un peu la présentation, car si je poste le projet complet, il ne faut pas que ce soit trop moche quand même.

Et j'essaye de trouver une belle requête ou combinaison de requêtes, pour passer mes listes de mots (une de 3 lettres, une de 4 etc....) en une belle grille, comme je l'exporte dans le csv.
Pour l'instant je fais une boucle for.
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
14 févr. 2014 à 18:22
Ha, au fait dans ce message, je voulais écrire que je charge le fichier avec un split, mais le p**** de correcteur d'orthographe m'a mit "salit".

J'ai aussi une petite correction à faire dans mes algos, j'ai inversé le X et le Y quand je saisie les coordonnées des dés.
Dans l'absolue ça ne change rien, mais le futur lecteur pourrait s'en émouvoir.
0
Réponse 20 / 71
noctambule28 Messages postés 31791 Date d'inscription samedi 12 mai 2007 Statut Webmaster Dernière intervention 13 février 2022 5
14 févr. 2014 à 18:54
Salut à tous,

Je lis votre post depuis le début et CHAPEAU ; je trouve cela assez génial, l'enthousiasme que vous avez tous dégagé pour arriver au résultat.
Un beau travail d'équipe ;-)
0

Discussions similaires

fonction modulo en VBA
krisprolss -
Benouille -

2 réponses
Comment fonctionne la fonction FormulaR1C1
cs_razmokets -
wape -

2 réponses
Le Modulo en VB6
elkasmi_ahmed -
econs -

2 réponses
le reste d'une division
hellouma -
MPi -

4 réponses
Affichage du userform dès l'ouverture du fichier excel
payhpayh7 -
aslalaud -

4 réponses
Rejoignez-nous