Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Exercice] solveur de mots-croisés

pour débutants

    23 août 2011 à 18:16:20

    Bonjour,

    J'imagine que tout le monde ici sait jouer aux mots croisés ;) . Souvenez vous la frustration lorsque on se retrouve bloqués avec un mot vraiment difficile.
    Là encore, Python va nous aider. :)


    Objectif



    Nous allons nous servir d'un dictionnaire de mots, pour chercher facilement tous les mots correspondants à une structure donnée. Ensuite, pour effectuer une recherche, l'utilisateur devra fournir une chaine spécialement formatée : chaque mot inconnu sera remplacé par une '*' (exemple : *e*r**d -> ['deprend', 'meprend', 'reprend']).


    Votre mission :


    • 1. Charger les mots d'un dictionnaire depuis un fichier.
    • 2. Proposer à l'utilisateur de rechercher des mots.
    • 3. Effectuer la recherche et afficher les résultats.




    Pour lire le fichier, vous devrez utiliser le module io, dont la documentation se trouve ici. Le chapitre du cours traitant ce sujet se trouve .

    Pour la recherche de motif, je suggère d'utiliser les expressions régulières du module re. Vous pouvez consulter la documentation officiele à ce sujet, comme lire ce chapitre du tutoriel du SdZ. Vous pouvez aussi faire autrement, si vous le désirez.

    Pensez à indiquer la version de Python utilisée.

    Bonne chance ! :)
    • Partager sur Facebook
    • Partager sur Twitter
      24 août 2011 à 1:02:22

      Bonsoir merci pour l'exercice. J'utilise la version 3.2 de python.

      Voici ma solution:

      import re
      
      s = input("Entrez votre mot:")
      l, c, regex = [], 0, re.compile(s.lower().strip().replace("*","."))
      
      with open("dict.txt","r") as file:
          for mot in file:
              if len(mot.strip()) == len(s) and regex.findall(mot):
                  l.append(mot.strip().title())
                  c += 1
      
      print("Nombre de mots trouvés: {}\nMots: {}".format(c,", ".join(l)))
      


      Edit: Nouveau code avec modifications, merci Grinwik.
      • Partager sur Facebook
      • Partager sur Twitter
        24 août 2011 à 2:55:37

        Solution sympatique !
        Une remarque Python : les lignes 9 à 12 peuvent être remplacées par la méthode replace() des chaines.
        • Partager sur Facebook
        • Partager sur Twitter
          24 août 2011 à 9:20:46

          @ Asimoov :
          Joli code ! :)

          Petite remarque : les ligne 4 et 5 peuvent être remplacées par :
          l, c, regex = [], 0, re.compile(s.lower().strip().replace("*","."))
          


          Ton code traite les tirets dans le dico comme des lettres, mais je n'ai pas vraiment spécifié ce point.

          • Partager sur Facebook
          • Partager sur Twitter
            24 août 2011 à 10:09:00

            Merci yoch, j'ai réédité mon code par contre pour les tirets je ne vois pas trop comment faire.
            J'essayerais de trouver tout à l'heure. o_O

            Edit: C'était prévisible je n'ai pas trouvé.
            • Partager sur Facebook
            • Partager sur Twitter
              27 août 2011 à 23:48:58

              En fait, il n'y a pas besoin de parser le fichier pour le découper en lignes. Avec un mot par ligne, la regexp est tout à fait capable de se débrouiller...

              dictionnaire =  open( "dictionnaire.txt" ).read()
              
              # retourne tous les mots qui correspondent
              re.compile("^" + s.lower().strip().replace("*",".") + "$", re.MULTILINE).findall( dictionnaire )
              



              • Partager sur Facebook
              • Partager sur Twitter
                28 août 2011 à 0:57:55

                Oh pas bête la guêpe !

                L'exercice semble très intéressants, je le ferrais en C :)
                • Partager sur Facebook
                • Partager sur Twitter
                🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
                  28 août 2011 à 1:40:34

                  Citation : @che


                  L'exercice semble très intéressants, je le ferrais en C :)



                  Ça pourrait être l'occasion de te mettre un peu à Python. C'est un bon langage à pratiquer en tandem avec le C... ;)
                  • Partager sur Facebook
                  • Partager sur Twitter
                  Zeste de Savoir, le site qui en a dans le citron !
                    28 août 2011 à 1:50:13

                    L'occasion de réessayer, tu as raison ...
                    En effet, j'ai pas totalement apprécié Python la première fois.

                    Je suis actuellement un peu occupé, mais je vais réessayé.
                    • Partager sur Facebook
                    • Partager sur Twitter
                    🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
                      28 août 2011 à 6:55:52

                      Ah excellent Lord Casque Noir.
                      • Partager sur Facebook
                      • Partager sur Twitter
                        28 août 2011 à 9:45:22

                        Citation : Lord Casque Noir

                        En fait, il n'y a pas besoin de parser le fichier pour le découper en lignes. Avec un mot par ligne, la regexp est tout à fait capable de se débrouiller...

                        dictionnaire =  open( "dictionnaire.txt" ).read()
                        
                        # retourne tous les mots qui correspondent
                        re.compile("^" + s.lower().strip().replace("*",".") + "$", re.MULTILINE).findall( dictionnaire )
                        



                        Joli ! :)

                        Non seulement un appel à read() est infiniment plus que construire une liste de mots, mais la recherche est aussi 2x plus rapide avec ta methode. Un petit bench :

                        Mon code original :
                        from io import *
                        import re
                        from time import time
                        
                        
                        def load_dico(filename):
                            # chargement du dictionnaire
                            tstart = time()
                            with open(filename, 'r') as infile:
                                words = [line.strip('\n') for line in infile]
                            print('Chargement du dictionnaire... ', end='')
                            print('ok, {0} mots chargés [{1:.6f}s]'.format(len(words), time() - tstart))
                            return words
                        
                        def search_for(pattern, dico):
                            reg = re.compile('^' + pattern.replace('*', '\w') + '$')
                            return [word for word in dico if reg.match(word)]
                        
                        dico = load_dico('liste_finale.txt')
                        # boucle principale
                        while True:
                            pattern = input('Entrez un mot (exemple : a**) : ').strip('\n')
                            tstart = time()
                            words = search_for(pattern, dico)
                            print(repr(words) + ' [{0:.6f}s] '.format(time() - tstart), end='\n\n')
                        


                        Chargement du dictionnaire... ok, 323578 mots chargés [0.361000s]
                        Entrez un mot (exemple : a**) : abs***s
                        ['abscons', 'absents', 'absides', 'absolus', 'abstrus'] [0.299000s]
                        
                        Entrez un mot (exemple : a**) : sar**o**
                        ['sarcloir', 'sarclons'] [0.305000s]


                        Code modifié :
                        from io import *
                        import re
                        from time import time
                        
                        
                        def load_dico(filename):
                            # chargement du dictionnaire
                            tstart = time()
                            with open(filename, 'r') as infile:
                                words = infile.read()
                            print('Chargement du dictionnaire... ', end='')
                            print('ok, {0} mots chargés [{1:.6f}s]'.format(len(words), time() - tstart))
                            return words
                        
                        def search_for(pattern, dico):
                            return re.compile('^' + pattern.replace('*', '\w') + '$', re.MULTILINE).findall(dico)
                            
                        dico = load_dico('liste_finale.txt')
                        # boucle principale
                        while True:
                            pattern = input('Entrez un mot (exemple : a**) : ').strip('\n')
                            tstart = time()
                            words = search_for(pattern, dico)
                            print(repr(words) + ' [{0:.6f}s] '.format(time() - tstart), end='\n\n')
                        


                        Chargement du dictionnaire... ok, 3616553 mots chargés [0.038000s]
                        Entrez un mot (exemple : a**) : tom**a**
                        ['tomahawk', 'tombeaux', 'tomerais', 'tomerait'] [0.162000s]


                        PS : Au passage, ma regex ne traite pas les tirets comme des lettres.
                        • Partager sur Facebook
                        • Partager sur Twitter
                          28 août 2011 à 23:15:35

                          comme optimisation simple, on peut charger le dictionnaire quand même (en prenant chaque ligne) et créer une liste de mots pour chaque longueur (dico.setdefault(len(mot),[]).append(mot)).

                          Puisque la longueur du mot cherché est connu, yapuka chercher dans la bonne liste.

                          Note : "grep "^tom..a..$" liste_finale.txt" => 10 ms
                          • Partager sur Facebook
                          • Partager sur Twitter
                            30 août 2011 à 15:19:35

                            Bon sur le conseil de nohar, me voila remis au Python. Cette fois ci, j'accroche déjà beaucoup plus :)(peut-être dû au fais que cette fois ci je sais à peu près ce que je vais voir)

                            J'ai essayer de voir comment je pourrais faire.
                            Au début, j'ai essayer de faire un truc que l'on pourrait réutiliser plus rapidement donc j'ai utilisé les dico :
                            # -*-coding:utf-8 -*
                            
                            # Permet la comparaison entre les chaines à trou (stringh) et les mots
                            # Ben quoi ? Je connais pas encore les regex en Python  
                            def strhcmp(string, stringh):
                              i = 0
                              stringh = stringh.lower()
                              for Char in string.lower():
                                if Char != stringh[i] and stringh[i] != '*':
                                  return False
                                i+=1
                              return True
                            
                            # On lit le fichier
                            dicoMot = {}
                            with open("dico.txt", "r") as fichierDico:
                              listMot = fichierDico.read().split()
                            
                            
                            # On classe les mots en fonction de leur taille
                            for string in listMot:
                              if len(string) not in dicoMot.keys():
                                dicoMot[len(string)] = []
                              dicoMot[len(string)] += [string]
                            
                            mot = ""
                            while 1:
                              mot = input()
                              if mot.lower() in ["quit", "q", "exit"]:
                                break
                              # On regarde dans la liste correspondant à la taille de mot s'il n'y a pas un mot qui pourrait passez  
                              for string in dicoMot[len(mot)]:
                                if strhcmp(string, mot):
                                  print string
                            


                            Et ensuite j'ai essayer faire seulement l'exercice sans me préoccuper d'autre chose :
                            # -*-coding:utf-8 -*
                            
                            mot = "*ache"
                            # Même fonction que le premier code
                            def strhcmp(string, stringh):
                              i = 0
                              stringh = stringh.lower()
                              for Char in string.lower():
                                if Char != stringh[i] and stringh[i] != '*':
                                  return False
                                i+=1
                              return True
                            
                            dicoMot = {}
                            with open("dico.txt", "r") as fichierDico:
                              listMot = fichierDico.read().split()
                            # On garde uniquement les mots qui on la même taille que mot
                            listMot = [string for string in listMot if len(string) == len(mot)]
                            
                            # Et on regarde si y en a pas un qui passe  
                            for string in listMot:
                              if strhcmp(string, mot):
                                print string
                            

                            Résultat :
                            bache
                            cache
                            fache
                            gache
                            hache
                            kache
                            lache
                            mache
                            sache
                            tache
                            vache


                            Si vous avez des retours, n'hésitez pas ;)
                            C'est mon premier code en Python \o/

                            Je précise que je n'ai pas encore fini le tuto (donc que je maitrise pas du tout python). J'essayerais de comprendre vos code dès que j'ai fini le tuto.
                            • Partager sur Facebook
                            • Partager sur Twitter
                            🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
                              30 août 2011 à 20:37:29

                              En Python, il y a une petite fonction très pratique appelée enumerate. Ça te permet de remplacer ce code :

                              i = 0
                              for char in string:
                                  if char != some_str[i]:
                                      pass
                                  i += 1
                              


                              avec ceci :
                              for i, char in enumerate(string):
                                  if char != some_str[i]:
                                      pass
                              


                              Par ailleurs, tu l'avais utilisé dans ton premier code, mais tu peux aussi utiliser in dans ton deuxième :

                              #ceci
                              if Char != stringh[i] and stringh[i] != '*':
                                  #...
                              
                              # en ceci
                              if stringh[i] not in (Char, '*'):
                              
                              • Partager sur Facebook
                              • Partager sur Twitter
                                30 août 2011 à 20:41:46

                                Citation : Fayden

                                En Python, il y a une petite fonction très pratique appelée enumerate.


                                A ce propos, il pourrait faire un petit tour ici pour approfondir certains points.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  30 août 2011 à 20:48:06

                                  Dès que j'ai finit le tuto je lis les autres tuto.

                                  @Fayden: Pas bête, j'en ai des choses à apprendre :)

                                  Merci
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                  🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
                                    2 septembre 2011 à 12:03:04

                                    petit code sans prétention mais exercice très utile ça m'a permis de me documenter sur les expressions régulières :p

                                    #-*-coding:Latin-1-*
                                    
                                    import re
                                    
                                    continuer=True
                                    print("***Solveur de mot croisés***\n\n")
                                    
                                    with open("dictionnaire.txt") as fichier:
                                        dictionnaire = str(fichier.read())
                                    dictionnaire = dictionnaire.split("\n")
                                    
                                    while continuer==True:
                                        mot_cache = input("\nEntre un mot (remplace les lettres manquantes par '*': ")
                                        try:
                                            if not re.search("^([\*?a-z]){2,}$", mot_cache):
                                                raise ValueError
                                        except ValueError:
                                            mot_cache = input("Mor invalide :\n\
                                    Entre un mot (remplace les lettres manquantes par '*': ")
                                        expression = "^" + re.sub("\*", "[a-z]", mot_cache) + "$"
                                        print("Liste des mots correspondants: ")
                                        for mot in dictionnaire:
                                            if re.search(expression, mot):
                                                print(mot)
                                    
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      4 septembre 2011 à 12:23:29

                                      Plusieurs jours que je me prends la tête avec ça, je ne comprenais pas pourquoi ça ne fonctionnait pas alors que théoriquement si. J'avais juste oublié les accolades dans mon print :-°

                                      Donc, c'est en python3, je n'ai pas utilisé les expressions régulières car je ne les comprends pas trop et j'ai fait ça avec des classes pour m'entrainer à la POO.
                                      Commentaires bienvenus :)

                                      # -*- coding:utf-8 -*-
                                      # solveur de mots croisés
                                      
                                      class Dico(object):
                                          """La classe pour contenir le dictionnaire des mots
                                             Les mots sont triés dans des listes en fonction de leur longueur
                                          """
                                          def __init__(self):
                                              self.dico = []
                                              for i in range(26):
                                                  #liste de 26 listes. Mot le plus long =25lettres
                                                  self.dico.append([])
                                      
                                          def remplissage_dico(self):
                                              # ouverture du fichier
                                              self.f = open("chiffres_lettres_dico.txt", "r")
                                      
                                              # boucle pour remplir le dictionnaire
                                      
                                              word = self.f.readline()    #pour sauter la première ligne
                                              longueur = 0    #pour gérer les listes en fonction du nombre de lettres
                                      
                                              while 1:
                                                  word = self.f.readline().strip('\n')
                                                  if word=='':
                                                      break
                                                  else:
                                                      longueur = len(word)
                                                      self.dico[longueur].append(word)
                                      
                                              # fermeture du fichier
                                              self.f.close()
                                      
                                              return self.dico
                                      
                                      
                                      class Application(object):
                                          """Corps de l'application"""
                                          def __init__(self):
                                              self.dico = Dico().remplissage_dico()
                                              self.mot_trouve = []
                                      
                                          def quel_mot(self):
                                              mot = input('Veuillez entrer un mot de la forme "t*s*": ').strip("\r")
                                              # on sélectionne le dico correspondant au nombre de lettres
                                              dico = self.dico[len(mot)]
                                      
                                              for m in dico:
                                                  d = True
                                                  for i, l in enumerate(mot):
                                                      if l != '*' and l != m[i]:
                                                          d = False
                                                  if d:
                                                      self.mot_trouve.append(m)
                                      
                                              print("Les mots trouvés sont : {}".format(self.mot_trouve))
                                      
                                      
                                      if __name__ == '__main__':
                                          test = Application().quel_mot()
                                      
                                      • Partager sur Facebook
                                      • Partager sur Twitter

                                      [Exercice] solveur de mots-croisés

                                      × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                      × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                      • Editeur
                                      • Markdown