Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Exercice] des chiffres et des lettres

Le mot le plus long

    9 août 2011 à 20:44:28

    Cet exo est intégralement repris du forum C++. Il a été originellement proposé par Nanoc en septembre 2008. Je trouve que c'est un excellent exercice, assez facilement réalisable en Python. :)


    Introduction



    Vous connaissez très certainement le célèbre jeu télévisé "Des chiffres et des lettres". Ce que je vous propose est de coder un programme qui résout la partie du jeu : "Le mot le plus long".

    Les règles du jeu sont simples mais le jeu est assez difficile. On tire au hasard 9 lettres et on cherche un mot français (orthographié correctement) écrits avec ces 9 lettres. Si on ne trouve pas de mots de 9 lettres, on cherche en 8 lettres et ainsi de suite.

    Le tirage des lettres, se passe de la manière suivante. On demande au joueur si il désire une consonne ou une voyelle et on lui donne une lettre au hasard selon son choix et on recommence pour les 8 autres. Le règlement impose qu'il y ait au minimum 2 voyelles. (Y est une voyelle)

    L'exercice



    Votre programme devra tirer au hasard des lettres selon les règles définies au-dessus.
    Il devra ensuite chercher la meilleure solution possible à partir du dictionnaire suivant:

    Dictionnaire de 323 578 mots (3.5 Mio)

    et l'afficher à l'écran. Si il y a plusieurs solutions, libre à vous de les afficher toutes ou non.

    Ce qui donne par exemple :
    Tirage : S I N U S A M O R
    Solutions possibles en 9 lettres :
    MARSOUINS
    SOUS-MARIN


    Remarque concernant le dictionnaire: Le dico contient des verbes conjugués ainsi que des pluriels. Il est donc suffisamment complet. Il ne contient que des caractères sans majuscules, sans accents et sans cédilles. [edit : il contient aussi des mots contenant un tiret (considérés comme un seul mot), comme vous pouvez le voir sur l'exemple]

    Votre programme devra fonctionner avec le dictionnaire situé dans le même dossier que l'exécutable et ne pas nécessiter d'autres fichiers que celui fourni.


    Bonne chance à tous !
    • Partager sur Facebook
    • Partager sur Twitter
    Anonyme
      9 août 2011 à 22:53:16

      # -*- coding:utf-8 -*-
      
      from __future__ import print_function
      
      try:
          input = raw_input
      except NameError:
          pass
      
      
      from random import choice
      
      CHARS = ["aeiouy", "bcdfghjklmnpqrstvwxz"]
      FILENAME = "liste_finale.txt"
      
      def choicechars():
          n, v = 9, 0
          chars = []
          while n:
              if (n == 2 and not v) or (n == 1 and v == 1):
                  c, v = choice(CHARS[0]), v + 1
                  print("Le nombre de voyelle minimal n'a pas été atteind.",
                        'La voyelle "{0}" a été choisie à votre place.'.format(c),
                        sep='\n')
              else:
                  s = input("Voyelle ou Consonne ?> ").lower()
                  if s in ('v', "voyelle"):
                      c, v = choice(CHARS[0]), v + 1
                  elif s in ('c', "consonne"):
                      c = choice(CHARS[1])
                  else:
                      print('Erreur de saisie : répondre [c] pour "consonne"',
                            'ou [v] pour "voyelle" !')
                      continue
                  print("la lettre", c, "a été choisie.")
              chars.append(c)
              n -= 1
          print(' | '.join(chars))
          return chars
      
      def getwords(chars):
          words = []
          with open(FILENAME) as file:
              while True:
                  ch = list(chars)
                  w = file.readline().strip()
                  if not w:
                      break
                  for c in w:
                      if c == '-':
                          continue
                      if c not in ch:
                          break
                  else:
                      words.append(w)
          words.sort(key=len, reverse=True)
          return words
      
      
      
      if __name__ == "__main__":
          words = getwords(choicechars())
          i = 0
          for w in words:
              if i != len(w):
                  i = len(w)
                  print("Mot(s) à", i, "lettre(s) :")
              print('   ', w)
          print(len(words), "mots(s) trouvé(s).")
      
      • Partager sur Facebook
      • Partager sur Twitter
        9 août 2011 à 23:16:17

        Alors, pour le mot le plus long :
        explication :
        l'idée (plutôt naive) est de charger le dico en générant pour chaque mot une chaine composée des lettres triées de ce mot (cf exemple dans le code).
        Il suffit ensuite de chercher toutes les chaines générées qui constituent le début des lettres du tirage elles aussi triées.

        "Analyse" :
        - il y a un coût initial important du au chargement du dictionnaire.
        - une fois les lettres triées, il est très certainement possible de réduire d'office la plage du dictionnaire parcourue (avec un arbre ?)


        code :
        def load_dico(path):
            mots = []
            with open(path) as dico:
                for mot in dico:
                    mot = mot.strip()
                    mots.append([mot, ''.join(sorted(mot.replace('-','')))])
                    # exemple : ['tout-fou', ['f', 'o', 'o', 't', 't', 'u', 'u']]
            return mots
        
        lettres = ['s', 'i', 'n', 'u', 's', 'a', 'm', 'o', 'r']
        print 'Tirage : ' + ' '.join(lettres)
        
        lettres_triees = ''.join(sorted(lettres))
        mots_trouves = []
        
        for mot in load_dico('liste_finale.txt'):
            if lettres_triees.startswith(mot[1]):
                mots_trouves.append(mot[0])
        
        if mots_trouves:
            mots_trouves = sorted(mots_trouves, key=len, reverse=True)
        
            # on ne garde que les meilleurs solutions:
            nb_lettres_maximum = len(mots_trouves[0].replace('-',''))
            solutions = filter(lambda m: len(m.replace('-','')) == nb_lettres_maximum, mots_trouves)
        
            print 'Solutions possibles en %d lettres :' % nb_lettres_maximum
            for s in solutions: print s
        
        else:
            print 'Pas de solution pour ce tirage.'
        


        pour le tirage :
        voyelle = 'aeiouy'
        consonne = 'bcdfghjklmnpqrstvwxz'
        
        from random import choice
        
         #----------------------------------------------
         #----------------------------------------------
        
        def homme():
            return raw_input('c ou v ? ')
        
        def machine():
            return choice('cv')
        
        def tirage(tireur):
            lettres = ['*'] * 9
            i_lettre = 0
            nb_voyelle = 0
            
            while i_lettre < 9:
                # regles des deux voyelles minimum
                if nb_voyelle == 0 and i_lettre == 7 or nb_voyelle ==1 and i_lettre == 8:
                    lettres[i_lettre] = choice(voyelle)
                    nb_voyelle += 1
                    i_lettre +=1
                    print ', '.join(lettres)
                    continue
        
                choix = tireur()
                if choix == 'c':
                    lettres[i_lettre] = choice(consonne)
                elif choix == 'v':
                    lettres[i_lettre] = choice(voyelle)
                    nb_voyelle += 1
                else:
                    continue
        
                i_lettre +=1
                print ', '.join(lettres)
        
            return lettres
        


        Par contre, je n'obtiens pas des tirages propices à de long mots, alors que dans l'émission il y en a beaucoup plus souvent.

        Je regarde la solution de PsycoPy ;) (un détail : il semble manquer la règle des deux voyelles minimum)
        • Partager sur Facebook
        • Partager sur Twitter
        Anonyme
          9 août 2011 à 23:30:02

          Arf... Oui je n'ai pas bien lu l'énoncé... comme d'hab. Faut que j'apprenne à ouvrir les yeux. :honte:

          J'édite ça tout de suite.
          • Partager sur Facebook
          • Partager sur Twitter
            10 août 2011 à 0:46:24

            Un autre essai :)
            # -*- coding: utf-8 -*-
            import random
            
            # Résolution
            def lettreValide(tirage, marqueurs, lettre):
                valide = False
                for i, c in enumerate(tirage):
                    if lettre == c and marqueurs[i] == False:
                        marqueurs[i] = True
                        return True
                return False
            
            
            
            def chercher(tirage):
                res = []
                dico = open('liste_finale.txt', 'r')
                for line in dico:
                    marqueur = [0] * len(line)
                    line = "".join(line.split('-'))
                    line = "".join(line.split('\n'))
            
                    marqueurs = [False] * len(tirage)
                    motValide = True
                    for c in line:
                        if not lettreValide(tirage, marqueurs, c):
                            motValide = False
                            break
                    if motValide:
                        res.append(line)
                
                dico.close()
            
                return res
            
            # Tirage
            def tirerConsonne():
                consonnes = 'bcdfghjklmnpqrstvwxz'
                return consonnes[random.randrange(len(consonnes))]
            
            def tirerVoyelle():
                voyelles = 'aeiouu'
                return voyelles[random.randrange(len(voyelles))]
            
            
            def creerTirage():
                s = ''
                n_voyelles = 0
                while(len(s) < 10):
                    if (len(s) == 8 and n_voyelles < 2) or (len(s) == 7 and n_voyelles == 0):
                        s += tirerVoyelle()
                    else:
                        c = random.randrange(2)
                        if c == 0:
                            s += tirerConsonne()
                        else:
                            s += tirerVoyelle()
                            n_voyelles += 1
                return s
            
            if __name__ == '__main__':
                tirage = creerTirage()
                print 'Tirage : %s' %tirage
                res = chercher(tirage)
                
                meilleur = 0
                for r in res:
                    if len(r) > meilleur:
                        meilleur = len(r)
            
                print 'solutions possible en %d lettres : '% meilleur
                for r in res:
                    if len(r) == meilleur:
                        print r
            


            edit: erreur sur le randrange.

            edit: explication comme demandée par Yoch.
            Le tirage.

            je tire au hasard un voyelle ou 1 consonne pour chaque lettre du tirage
            si au bout de 7 ou 8 lettre tirées on a pas le compte de voyelle on ajuste.


            Résolution

            Pour chaque mot du dictionnaire
            je supprime les '-'
            ensuite je vérifie s'il est réalisable avec le tirage donné.
            Si oui, je l'ajoute à la liste des résultats.

            • Partager sur Facebook
            • Partager sur Twitter
            Zeste de Savoir, le site qui en a dans le citron !
              10 août 2011 à 1:54:39

              en python 2 ...
              edit: j'ai fait des fonctions ... me suis forcé ...

              #!/usr/bin/env python 
              from random import choice
              
              tout = {'c':'zrtpqsdfghjklmwxcvbn','v':'aeiouy'}
              with open('liste_finale.txt') as dico: dico = [word.strip() for word in dico.readlines()]
              
              def tirage():
                  tirage = ''
                  nb_cons = 0
                  while len(tirage) < 9:
                      if nb_cons == 7:
                          tirage += choice(tout['v'])
                          print 'selection auto de voyelle'
                          print 'tirage :',tirage.replace('',' ').upper()
                          print
                          continue
                      try:
                          tirage += choice(tout[raw_input('<c>onsonne ou <v>oyelle : ')])
                          if tirage[-1] in tout['c']: nb_cons += 1
                          print 'tirage :',tirage.replace('',' ').upper()
                      except:
                          print 'gni ?'
                      print
                  return tirage+'---'
              
              def soluces(tirage):
                  print 'je reflechis ...'
                  print
                  soluces = {}
                  for word in dico:
                      ref = list(tirage)
                      try:
                          for char in word: ref.remove(char)
                      except: continue
                      soluces[len(word)] = soluces.setdefault(len(word),()) + (word,)
                  return soluces
              
              def affichage(soluces):
                  for length,words in sorted(soluces.items(),reverse=1):
                      print 'Solutions possibles en',length,'lettre(s) :'
                      for word in words: print word
                      print
              
              affichage(soluces(tirage()))
              
              • Partager sur Facebook
              • Partager sur Twitter

              "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                10 août 2011 à 9:01:24

                Citation : Grinwik


                Il suffit ensuite de chercher toutes les chaines générées qui constituent le début des lettres du tirage elles aussi triées.



                Pourquoi le début ?

                Session de ton code :

                Tirage : k k k k k k z u t
                Pas de solution pour ce tirage.
                



                or, clairement, zut est le mot le plus long.

                [EDIT : Pour corriger, il suffit de changer if lettres_triees.startswith(mot[1]): par if mot[1] in lettres_triees:
                ]

                Citation : Grinwik

                mots.append([mot, ''.join(sorted(mot.replace('-','')))])
                            # exemple : ['tout-fou', ['f', 'o', 'o', 't', 't', 'u', 'u']]
                





                C'est pas plutôt # exemple : ['tout-fou', 'foottuu'] ?

                Citation : Grinwik


                lettres = ['s', 'i', 'n', 'u', 's', 'a', 'm', 'o', 'r']
                print 'Tirage : ' + ' '.join(lettres)
                





                lettres = list('sinusamor') est quand même plus simple, en particulier pour ceux qui testent ton code.
                • Partager sur Facebook
                • Partager sur Twitter
                  10 août 2011 à 12:06:41

                  Bonjour,

                  Si ce n'est pas trop vous demander, ce serait bien que chacun mette une petite explication (1/2 lignes) sur ce qu'il fait et pourquoi. Donner une indication sur le temps de chargement et le temps de recherche du mot le plus long est aussi souhaitable, ca permettra à tout le monde de suivre.

                  Merci ! :)
                  • Partager sur Facebook
                  • Partager sur Twitter
                    10 août 2011 à 12:52:24

                    Citation : yoch

                    Bonjour,

                    Si ce n'est pas trop vous demander, ce serait bien que chacun mette une petite explication (1/2 lignes) sur ce qu'il fait et pourquoi. Donner une indication sur le temps de chargement et le temps de recherche du mot le plus long est aussi souhaitable, ca permettra à tout le monde de suivre.

                    Merci ! :)



                    de suivre quoi ?

                    sinon j'ai mis des commentaires, je ne sais pas si c'est assez clair, tu me diras:

                    #!/usr/bin/env python 
                    from random import choice
                    
                    tout = {'c':'zrtpqsdfghjklmwxcvbn','v':'aeiouy'}
                    with open('liste_finale.txt') as dico: dico = [word.strip() for word in dico.readlines()]
                    
                    def tirage():
                        tirage = '' # on stocke les lettres dans une chaine
                        nb_cons = 0 # on compte les consonnes tirees
                        while len(tirage) < 9: # temps qu'on a pas tire 9 lettres
                            if nb_cons == 7: # si 7 consonnes sont deja sorties
                                tirage += choice(tout['v']) # on tire une voyelle
                                print 'selection auto de voyelle'
                                print 'tirage :',tirage.replace('',' ').upper()
                                print
                                continue # et on zappe la partie raw_input
                            try:
                                tirage += choice(tout[raw_input('<c>onsonne ou <v>oyelle : ')])
                                # on ajoute une consonne ou une voyelle en fonction de la reponse
                                if tirage[-1] in tout['c']: nb_cons += 1 # on compte les consonnes
                                print 'tirage :',tirage.replace('',' ').upper()
                            except:
                                print 'gni ?' # si la reponse est incorrecte
                            print
                        return tirage+'---' # le dico contient des mots composes avec 3 tirets
                    
                    def soluces(tirage):
                        print 'je reflechis ...'
                        print
                        soluces = {} # on stocke les mots trouvés dans un dict
                        for word in dico: # pour chaque mot du dico
                            ref = list(tirage) # on copie les lettres du tirage
                            try:
                                for char in word: ref.remove(char) # si toutes les lettres du mot
                                # sont presentes dans le tirage, alors ref.remove() ne raise pas d'exception
                            except: continue # si une exception est raise, alors ce mot n'est pas une soluce
                            # et on zappe la partie stockage
                            soluces[len(word)] = soluces.setdefault(len(word),()) + (word,) # on stocke le mot soluce
                            # dans un tuple avec comme clef la longueur du mot
                        return soluces
                    
                    def affichage(soluces):
                        for length,words in sorted(soluces.items(),reverse=1):
                            print 'Solutions possibles en',length,'lettres :'
                            for word in words: print word
                            print
                    
                    affichage(soluces(tirage()))
                    
                    • Partager sur Facebook
                    • Partager sur Twitter

                    "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                      10 août 2011 à 17:10:35

                      Citation : josmiley

                      de suivre quoi ?


                      Ben de suivre les algos proposés et leur efficacité, c'est quand même plus facile pour tout le monde avec une petite explication, voire même un bench (je n'en demande pas tant).

                      Citation : josmiley

                      sinon j'ai mis des commentaires, je ne sais pas si c'est assez clair, tu me diras:


                      Merci infiniment, c'est beaucoup plus clair comme ça. :)

                      Bon, je crois que tout le monde a exploité le fait que le dictionnaire doit de toute façon être parcouru une fois pour donner des algos de recherche en O(n), ce qui me parait être une erreur : imaginez simplement qu'une fois le dictionnaire chargé, on effectues de multiples recherches. A ce moment, les algos proposés ici seront plutôt mauvais.

                      Je suis désolé, je crois que j'aurais dû modifier l'énoncé de départ pour inciter dans ce sens. Mes sincères excuses.
                      • Partager sur Facebook
                      • Partager sur Twitter
                        10 août 2011 à 17:15:26

                        Tu veux nous faire coder un Trie? :-°

                        J'ai commencé hier, je trouve ça plus simple en C. :(
                        • Partager sur Facebook
                        • Partager sur Twitter
                        Zeste de Savoir, le site qui en a dans le citron !
                          10 août 2011 à 17:34:58

                          Citation : GurneyH

                          Tu veux nous faire coder un Trie? :-°


                          Non, pas du tout :p . Je pense que l'on peut trouver d'excellentes solutions assez simple avec la lib standard.

                          Citation : GurneyH

                          J'ai commencé hier, je trouve ça plus simple en C. :(


                          Effectivement, il y a des trucs que j'ai encore tendance à trouver plus naturels en C, comme notamment les arbres. Mais ça ne veut pas dire que c'est réellement le cas, un arbre pouvant être modélisé plutôt facilement avec des listes (enfin bon, moi je ne trouve pas ça spécialement naturel).
                          Ça me fait d'ailleurs penser qu'il serait probablement intéressant de donner un exo mettant en oeuvre des arbres en python :-° .
                          • Partager sur Facebook
                          • Partager sur Twitter
                            10 août 2011 à 17:49:25

                            voilà qui devrait te plaire,
                            le dico est un dict() qui classe les mots selon leurs initiales ...
                            dico = {'a':['a','abaissa',...],'b':[etc...],...}
                            si l'initiale n'est pas contenue dans le tirage, c'est pas la peine de chercher dans cette liste de mots ..

                            #!/usr/bin/env python
                            # -*- coding: utf-8 -*-
                            #!/usr/bin/env python 
                            from random import choice
                            
                            tout = {'c':'zrtpqsdfghjklmwxcvbn','v':'aeiouy'}
                            with open('liste_finale.txt') as f:
                                # un dict  qui trie les mots selon l'initial
                                dico = dict([(i,[]) for i in 'azertyuiopqsdfghjklmwxcvbn'])
                                for word in f.readlines(): dico[word[0]].append(word.strip())
                            
                            def tirage():
                                tirage = '' # on stocke les lettres dans une chaine
                                nb_cons = 0 # on compte les consonnes tirees
                                while len(tirage) < 9: # temps qu'on a pas tire 9 lettres
                                    if nb_cons == 7: # si 7 consonnes sont deja sorties
                                        tirage += choice(tout['v']) # on tire une voyelle
                                        print 'selection auto de voyelle'
                                        print 'tirage :',tirage.replace('',' ').upper()
                                        print
                                        continue # et on zappe la partie raw_input
                                    try:
                                        tirage += choice(tout[raw_input('<c>onsonne ou <v>oyelle : ')])
                                        # on ajoute une consonne ou une voyelle en fonction de la reponse
                                        if tirage[-1] in tout['c']: nb_cons += 1 # on compte les consonnes
                                        print 'tirage :',tirage.replace('',' ').upper()
                                    except:
                                        print 'gni ?' # si la reponse est incorrecte
                                    print
                                return tirage
                            
                            def soluces(tirage):
                                print 'je reflechis ...'
                                print
                                tirage += '---' # le dico contient des mots composes avec 3 tirets
                                soluces = {} # on stocke les mots trouvés dans un dict
                                for lettre in set(tirage[:-3]): # on parcours que les mots dont l'initile est contenu dans tirage
                                    for word in dico[lettre]: # pour chaque mot du dico
                                        ref = list(tirage) # on copie les lettres du tirage
                                        try:
                                            for char in word: ref.remove(char) # si toutes les lettres du mot
                                            # sont presentes dans le tirage, alors ref.remove() ne raise pas d'exception
                                        except: continue # si une exception est raise, alors ce mot n'est pas une soluce
                                        # et on zappe la partie stockage
                                        soluces[len(word)] = soluces.setdefault(len(word),()) + (word,) # on stocke le mot soluce
                                        # dans un tuple avec comme clef la longueur du mot
                                return soluces
                            
                            def affichage(soluces):
                                for length,words in sorted(soluces.items(),reverse=1):
                                    print 'Solutions possibles en',length,'lettres :'
                                    for word in words: print word
                                    print
                            
                            affichage(soluces(tirage()))
                            
                            • Partager sur Facebook
                            • Partager sur Twitter

                            "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                              10 août 2011 à 17:54:48

                              Je suis en train de chercher s'il n'y a pas une manière de mettre les mots du dictionnaire dans une hashtable, et de trouver un moyen de les arranger de sorte à avoir une structure en recherche en O(1), mais je n'ai pas de moyen efficace encore.
                              J'ai cherché aussi du côté des hashsets, mais le problème c'est que ça casse tout pour les mots qui ont plusieurs fois la même lettre. Dommage, parce que trouver si un set est un sous-set d'un autre se fait en O(log n).
                              Si j'arrive à trouver une solution correcte, je vous en fais part.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                10 août 2011 à 18:40:17

                                Citation : josmiley

                                voilà qui devrait te plaire,
                                le dico est un dict() qui classe les mots selon leurs initiales ...
                                dico = {'a':['a','abaissa',...],'b':[etc...],...}
                                si l'initiale n'est pas contenue dans le tirage, c'est pas la peine de chercher dans cette liste de mots ..


                                Bien imaginé, mais il y a beaucoup mieux. ;)

                                Citation : anonymous

                                Je suis en train de chercher s'il n'y a pas une manière de mettre les mots du dictionnaire dans une hashtable, et de trouver un moyen de les arranger de sorte à avoir une structure en recherche en O(1), mais je n'ai pas de moyen efficace encore.


                                Je penses que tu es sur la bonne voie. :)
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  10 août 2011 à 19:52:29


                                  Je pense qu'il faut déja trier les mots par tailles.
                                  Ensuite chaque mot est dans une hash table dont la clef est les lettres dans l'ordre alphabétique.
                                  Pour le 9 lettres suffit de trier les lettres du tirage dans l'ordre et on trouve le mot en O(1).
                                  Pour 8 lettres on fait 9 accès à la hashMap avec les différentes combinaisons en enlevant une lettre du tirage.
                                  Après pour les mots moins long on doit pouvoir faire pareil (toutes les combinaisons de 7 des 9 lettres, 6 des 9 lettres...). Mais peut être qu'il en prenant chaque clef du dictionnaire correspondant à un mot de x lettres. Un index sur la lettre dans le mot, un autre sur le tirage, si la lettre du mot est < à celle courante du tirage alors on passe au mot suivant, si elle est > on passe à la lettre suivante du tirage jusqu'à la fin de celui-ci, si elle est égale on passe à la lettre suivante du tirage et du mot du dictionnaire. On ne remet les deux index à zéro que lorsque l'on change de mot.
                                  Bon c'est peut être pas très clair comme ça mais j'ai pas envie de coder.
                                  [edit]Sauf qu'on doit pas pouvoir mettre plusieurs mots avec la même clef dans une hashTable, et comme il y a des anagrammes, au lieu d'associé une clef un mot ça doit plutôt être une clef une liste de mot.[/edit]
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    10 août 2011 à 20:18:58

                                    Citation : mac.aque


                                    Ensuite chaque mot est dans une hash table dont la clef est les lettres dans l'ordre alphabétique.
                                    Pour le 9 lettres suffit de trier les lettres du tirage dans l'ordre et on trouve le mot en O(1).
                                    Pour 8 lettres on fait 9 accès à la hashMap avec les différentes combinaisons en enlevant une lettre du tirage.
                                    Après pour les mots moins long on doit pouvoir faire pareil (toutes les combinaisons de 7 des 9 lettres, 6 des 9 lettres...).

                                    Oui, excellent ! :)

                                    Pour le problème en question, je pense que cette approche est la plus efficace. On fait dans le pire des cas 510 accès au dictionnaire, ce qui est négligeable. Après, si on cherche à généraliser, je ne sais pas exactement jusqu’où cette approche sera adaptée.

                                    Python possède d'ailleurs des fonctions permettant de simplifier grandement le traitement combinatoire. Pour preuve, mon code :

                                    from io import *
                                    from itertools import combinations
                                    from collections import defaultdict
                                    from random import choice
                                    from time import time
                                    
                                    
                                    words = defaultdict(list)
                                    
                                    
                                    def search_for(letters):
                                        ret = []
                                        for sz in range(len(letters), 0, -1):
                                            for _letters in combinations(letters, sz):
                                                key = ''.join(sorted(_letters))
                                                if key in words:
                                                    ret += words[key]
                                            if ret != []:
                                                return sz, list(set(ret))
                                    
                                    def tirage(nconsonnes, nvoyelles):
                                        if nconsonnes + nvoyelles != 9:
                                            raise RuntimeError('Il faut exactement 9 lettres')
                                        elif nvoyelles < 2:
                                            raise RuntimeError('Il faut au minimum 2 voyelles')
                                        voy  = 'aeiouy'
                                        cons = 'bcdfghjklmnpqrstvwxz'
                                        return [choice(cons) for n in range(nconsonnes)] + [choice(voy) for n in range(nvoyelles)]    
                                    
                                    # chargement du dictionnaire
                                    tstart = time()
                                    infile = open('liste_finale.txt', 'r')
                                    while True:
                                        line = infile.readline()
                                        if line == str(): break
                                        line = line.strip('\n')
                                        key = ''.join(sorted(line)).replace('-','')
                                        words[key].append(line)
                                    infile.close()
                                    tend = time()
                                    print('... chargement du dictionnaire termine [{0:.6f}s]\n'.format(tend - tstart))
                                    
                                    
                                    # boucle principale
                                    continuer = True
                                    while continuer:
                                        nv = int(input('Combien de voyelles (min 2) : '))
                                        nc = int(input('Combien de consonnes : '))
                                        t = tirage(nc, nv)
                                        print('tirage : ', t)
                                        tstart = time()
                                        sz, lst = search_for(t)
                                        tend = time()
                                        print('mots de ' + str(sz) + ' lettres trouves [{0:.6f}s] : '.format(tend - tstart), lst, end='\n\n')
                                        c = ''
                                        while c != 'o' and c != 'n':
                                            c = input('Continuer (O/N) ? : ')[0].lower()
                                            if c == 'n':
                                                continuer = False
                                    


                                    Citation : mac.aque

                                    Mais peut être qu'il en prenant chaque clef du dictionnaire correspondant à un mot de x lettres. Un index sur la lettre dans le mot, un autre sur le tirage, si la lettre du mot est < à celle courante du tirage alors on passe au mot suivant, si elle est > on passe à la lettre suivante du tirage jusqu'à la fin de celui-ci, si elle est égale on passe à la lettre suivante du tirage et du mot du dictionnaire. On ne remet les deux index à zéro que lorsque l'on change de mot.
                                    Bon c'est peut être pas très clair comme ça mais j'ai pas envie de coder.

                                    Effectivement, cette partie est pas vraiment claire, je n'ai rien compris. :-°
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      10 août 2011 à 20:29:55

                                      Citation : yoch


                                      Citation : mac.aque

                                      Mais peut être qu'il en prenant chaque clef du dictionnaire correspondant à un mot de x lettres. Un index sur la lettre dans le mot, un autre sur le tirage, si la lettre du mot est < à celle courante du tirage alors on passe au mot suivant, si elle est > on passe à la lettre suivante du tirage jusqu'à la fin de celui-ci, si elle est égale on passe à la lettre suivante du tirage et du mot du dictionnaire. On ne remet les deux index à zéro que lorsque l'on change de mot.
                                      Bon c'est peut être pas très clair comme ça mais j'ai pas envie de coder.


                                      Effectivement, cette partie est pas vraiment claire, je n'ai rien compris. :-°


                                      Si ça ne fait que 512 accès au dictionnaire avec les permutations c'était une mauvaise idée de toute façon.
                                      C'était juste pour expliquer la comparaison entre les lettres du mot triée et les lettres du tirage triée.
                                      Si par exemple mot est chien => cehin et le tirage trié: acfmop..., alors on compare c et a puis c et c, on passe ensuite au e, on le compare à f, comme f>e on sait que cehin de va pas, on passe au mot suivant. Pas besoin de tester toutes les lettres, dans pas mal de cas une seul doit suffir.
                                      Après on pourrait aussi imaginer un arbre sans lequel les mots du dictionnaires serait stocker,mais ça devient compliqué et ça sera moins bon que 512 accès au dico.
                                      Du coup si on ne fait que des permutations, même plus besoins de s'occuper de la taille des mots (même si supprimer tous les mots de plus de 9 lettres ne coute pas grand chose et allégera un peu la mémoire consommée).
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        10 août 2011 à 20:39:03

                                        J'ai commencé comme ça mac.aque, en effet : trier les mots en mettant leurs lettres dans l'ordre alphabétique.
                                        Mais ta méthode est, il me semble, en O(2m + n) ici avec m la longueur du mot et n le nombre de mots, parce que tu as une somme de coefficients binomiaux.
                                        Le nombre de mots qu'on peut composer au total avec un tirage de m lettres, c'est la somme du nombre de mots de 1 à m lettres qu'on peut composer, ce qui se calcule avec un coefficient binomial (notion de terminale) :
                                        On obtient donc <math>\(\sum^{m}_{k=1}{m \choose k}\)</math> ce qui fait <math>\(2^{m} - {m \choose 0}\)</math>, donc <math>\(2^{m} - 1\)</math>.

                                        On a donc une complexité de O(n + 2m), sauf erreur de ma part.

                                        Si on commence à prendre des tirages plus longs et des mots plus longs, on va tout simplement faire exploser la baraque.

                                        La question : peut-on éviter ce 2m, ou bien le considère-t-on comme fixe, donc égal à 8, donc on réduit tout ça en O(n) ?
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          10 août 2011 à 20:56:49

                                          Citation : anonymous

                                          Si on commence à prendre des tirages plus longs et des mots plus longs, on va tout simplement faire exploser la baraque.


                                          Oui, je sais. C'est ce que je disais plus haut "Après, si on cherche à généraliser, je ne sais pas exactement jusqu’où cette approche sera adaptée".

                                          Ça dépend aussi clairement de la taille du dico : s'il est relativement petit, on peut imaginer un algo en O(N) (N étant le nombre de mots dans le dico) [l'algo que beaucoup ont visiblement implémenté, cf. aussi la solution proposée sur le forum C++], mais en général on peut supposer que la taille du dico augmente avec la taille des mots, et donc la seconde approche serait meilleure.

                                          Citation : anonymous

                                          La question : peut-on éviter ce 2m, ou bien le considère-t-on comme fixe, donc égal à 8, donc on réduit tout ça en O(1) ?


                                          Oui, that is the question. Je suis curieux de voir si quelqu'un va apporter une solution originale au problème.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            10 août 2011 à 21:22:47

                                            Bah à ce niveau-là, c'est pas au hasard qu'on trouvera quelque chose.
                                            Le O(n) est clairement irréductible, la lecture on ne peut pas la segmenter.
                                            Je vais essayer de me concentrer sur ce qui est pour l'instant un O(2m), et qui fait mal, parce que c'est plus cool d'avoir une complexité faible je trouve.

                                            Je cherche une manière d'utiliser les intersections de sets, qui sont des hashsets en python. La vérification de l'inclusion pour un set A qui contient les lettres du tirage, et un set B qui contient les lettres du mot, (A & B) == B donc c'est en gros, du O(log m) pour l'intersection, et O(m) pour l'égalité, parce que je ne connais pas la complexité de l'opération égalité, et je ne pense pas que ce soit au-dessus de O(m). Je n'arrive pas à le trouver sur les internets malheureusement.

                                            Je crois avoir une solution pas trop vilaine pour utiliser des sets de manière efficace, en utilisant des lettres numérotées.
                                            Ainsi, le mot 'aaazerr' deviendrait {'a1','a2','a3','e1','r1','r2','z1'}. On aurait des « lettres » uniques, et vérifier les sous-sets serait alors du O(m).
                                            On pourrait alors obtenir un code en O(m*n), ce qui n'est pas trop mal. Mais surtout, ce serait du O(min(m!,n)) en complexité spatiale dans le pire des pires cas, puisqu'à la fin il ne reste QUE les mots qui marchent, et les mots n'ont pas besoin d'être stockés.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              10 août 2011 à 23:07:14

                                              Dans la méthode de la hasTable, le nombre de mot dans le dictionnaire ne joue pas dans le temps d'exécution (à part pour l'initialisation mais peut être que tu la compte dedans ?). Si le nombre de lettre est fixe on est en O(1) il me semble.
                                              Sinon pour ta technique, tu peux stocker chaque lettre et leur nombre d'apparition, mais pas les réduire à une expression "a3" a comparer car si dans le tirage il y a trois lettres "a", il faut quand même trouvé les mots de 8 lettres qui n'ont que deux "a".
                                              L'algo "naif" qui consiste a comparer tous les mots du dico avec le tirage dépends aussi du nombre de lettre du tirage (puisque pour chaque mot il y aura plus de lettre à comparer), mais c'est vrai qu'il en dépends beaucoup moins. Cet algo est en O(m*n) il me semble (voir moins si l'on gagne sur les comparaisons de chaque mot), donc je comprends pas bien l'histoire des Set et intersection de Set et ce que ça apporte.
                                              Après la longueur des mots de la langue française n'est pas infini, mais bon on peut supposer que l'algo puisse servir à autre chose de similaire.
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                              Anonyme
                                                11 août 2011 à 0:09:47

                                                Est-ce que ceci correspond à vos attentes en terme de complexité ?

                                                # -*- coding:utf-8 -*-
                                                
                                                from __future__ import print_function
                                                
                                                try:
                                                    input = raw_input
                                                except NameError:
                                                    pass
                                                
                                                
                                                from random import choice
                                                
                                                CHARS = ["aeiouy", "bcdfghjklmnpqrstvwxz"]
                                                FILENAME = "liste_finale.txt"
                                                
                                                def getdict(filename):
                                                    d = dict()
                                                    with open(filename) as file:
                                                        for line in file:
                                                            v = line.strip()
                                                            k = list(v)
                                                            k.sort()
                                                            k = hash(''.join(k))
                                                            if k in d:
                                                                d[k].append(v)
                                                            else:
                                                                d[k] = [v]
                                                    return d
                                                
                                                def choicechars():
                                                    n, ls, x = 9, [], 0
                                                    while n:
                                                        if x < 7:
                                                            s = input("Consonne ou voyelle ?> ").lower()
                                                            if s in ('c', 'consonne'):
                                                                c = choice(CHARS[1])
                                                                x += 1
                                                            elif s in ('v', 'voyelle'):
                                                                c = choice(CHARS[0])
                                                            else:
                                                                print("Erreur de saisie : répondre [c] pour consonne ou",
                                                                      "[v] pour voyelle !")
                                                                continue
                                                            print("La lettre", c, "a été choisie.")
                                                        else:
                                                            c = choice(CHARS[0])
                                                            print("La voyelle", c, "a été choisi automatiquement.")
                                                        ls.append(c)
                                                        n -= 1
                                                    return ls
                                                
                                                def searchwords(dict, chars):
                                                    def f(s, n):
                                                        n, r = bin(n)[2:].zfill(9), ''
                                                        for i in range(len(s)):
                                                            if int(n[i]):
                                                                r += s[i]
                                                        return r
                                                    chars = list(chars)
                                                    chars.sort()
                                                    chars = ''.join(chars)
                                                    ls = []
                                                    for n in range(511):
                                                        try:
                                                            ls += dict[hash(f(chars, n))]
                                                        except KeyError:
                                                            pass
                                                    ls.sort(key=len, reverse=True)
                                                    return ls
                                                
                                                dicti = getdict(FILENAME)
                                                chars = choicechars()
                                                print('  ', ' | '.join(chars))
                                                words = searchwords(dicti, chars)
                                                
                                                i = 0
                                                for w in words:
                                                    if i != len(w):
                                                        i = len(w)
                                                        print("Mot(s) à", i, "lettre(s) :")
                                                    print('  ', w)
                                                print(len(words), "mot(s) trouvé(s).")
                                                


                                                [edit] Bon, le code est sale et j'ai complètement zappé le coup des tirets... :-° Mais l'idée est là non ?
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  11 août 2011 à 2:36:37

                                                  Citation : yoch

                                                  mon code




                                                  L'intérêt de l'exercice ne réside pas dans le tirage (et qui est même complètement artificiel puisque dans la réalité il y a deux joueurs indépendants). Le cœur de l'exercice consiste à déterminer de façon efficace, à partir d'un tirage donné, le mot le plus long ; donc on peut supposer que l'utilisateur du programme fournisse un tirage et que l'utilisateur veut voir les mots les plus longs correspondant à ce tirage (imagine que l'utilisateur du programme veut mettre en œuvre le programme en même temps qu'il regarde le jeu se dérouler à la TV pour anticiper la meilleure réponse).

                                                  Bref, je m'attendais à ce que ton programme me donne la possibilité de donner mon propre tirage. En outre, je ne comprends pas pourquoi ton programme me demande le nombre de voyelles et le nombre de consonnes.

                                                  Par ailleurs, la limitation des 9 caractères est très artificielle, imagine par exemple que je cherche le plus long du lexique et constitué de lettres toutes différentes, autrement dit issues du tirage des 26 lettres de l'alphabet. D'ailleurs, un site comme CELUI-CI propose une recherche à partir d'un tirage jusqu'à 15 lettres (ce qui reste encore une restriction artificielle).


                                                  Enfin, je pense que ton code tel quel ne peut traiter ce genre de cas puisque tu utilises la fonction combinations et dont la complexité est exponentielle. Par exemple, si je modifie ton code pour le tirage aaaaaaaaaaaaaaaaaaaaaaa (23 fois la lettre a), ton programme met plus de 10 secondes à répondre. De même si j'entre le tirage 'azertyuiopmlkjhgfdsqwxcvbn', ton code met plus d'une minute. Le code de Gurney traite sans problème et rapidement une entrée de n'importe quelle taille.

                                                  Sinon l'idée de l'utilisation de l'ordonnancement alphabétique des lettres de chaque mot a aussi été proposé par Grinwik.


                                                  Je pense qu'il faudrait demander dans le post original que le code soit accompagné de la version de Python utilisée.


                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                  Anonyme
                                                    11 août 2011 à 2:54:18

                                                    Bon j'ai essayé de faire quelquechose sans prétention, j'ai pas prévu les tirages, et comme le dis Candide je ne vois pas où est l'intérêt. Il est plus intéressant de rentrer ces lettres. Enfin bref, ça à l'air de fonctionner sans trop attendre.

                                                    version 2.7

                                                    #!/usr/bin/python
                                                    # -*- coding:utf8 -*-
                                                    
                                                    import os
                                                    
                                                    def dico(liste1, liste2):
                                                        for mot1, mot2 in zip(liste1, liste2):
                                                            yield (mot1, mot2)
                                                    
                                                    def ajout_dico(liste1, liste2):
                                                        dic = {}
                                                        for i, j in [tup for tup in dico(liste1, liste2)]:
                                                            dic[i] = j
                                                        return dic
                                                    
                                                    def recherche(fichier):
                                                        FICHIER = os.path.join(os.getcwd(), fichier)
                                                        with open(FICHIER, 'r') as f:
                                                            mes_mots = f.readlines()
                                                        return [mot.strip('\n') for mot in mes_mots]
                                                    
                                                    def ordre(chaine):
                                                        chaine = list(chaine)
                                                        chaine.sort()
                                                        return ''.join(chaine)
                                                    
                                                    def ordonne(liste):
                                                        for mot in liste:
                                                            yield ordre(mot)
                                                    
                                                    def main(chaine):
                                                        mot_recherche = ordre(chaine)
                                                        return [mot for mot in d.keys() if \
                                                               mot_recherche in d[mot] \
                                                               and len(mot_recherche) >= len(d[mot])]
                                                    
                                                    def test(m):    
                                                        for i in xrange(len(m)):
                                                            yield main(m[i:])
                                                    
                                                    FILE = 'dico.txt'
                                                    mots = recherche(FILE)
                                                    mots_ord = [mot for mot in ordonne(mots)]
                                                    d = ajout_dico(mots, mots_ord)
                                                    
                                                    mes_lettres = raw_input('Entrer vos lettres: ')
                                                    for result in test(mes_lettres):
                                                        if result:
                                                            print result
                                                            break
                                                    


                                                    Je vais faire dodo maintenant :)

                                                    Edit : J'ai vu qu'il y avait des erreurs, j'essaierai de les résoudre aujourd'hui
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      11 août 2011 à 9:28:09

                                                      Citation : anonymous

                                                      Je cherche une manière d'utiliser les intersections de sets, qui sont des hashsets en python. La vérification de l'inclusion pour un set A qui contient les lettres du tirage, et un set B qui contient les lettres du mot, (A & B) == B donc c'est en gros, du O(log m) pour l'intersection, et O(m) pour l'égalité, parce que je ne connais pas la complexité de l'opération égalité, et je ne pense pas que ce soit au-dessus de O(m). Je n'arrive pas à le trouver sur les internets malheureusement.

                                                      Je crois avoir une solution pas trop vilaine pour utiliser des sets de manière efficace, en utilisant des lettres numérotées.
                                                      Ainsi, le mot 'aaazerr' deviendrait {'a1','a2','a3','e1','r1','r2','z1'}. On aurait des « lettres » uniques, et vérifier les sous-sets serait alors du O(m).
                                                      On pourrait alors obtenir un code en O(m*n), ce qui n'est pas trop mal. Mais surtout, ce serait du O(min(m!,n)) en complexité spatiale dans le pire des pires cas, puisqu'à la fin il ne reste QUE les mots qui marchent, et les mots n'ont pas besoin d'être stockés.


                                                      Je ne suis pas sûr d'avoir compris ce que tu cherches à faire, mais je crois que tu retourne vers le second type d'algo, deja mentionné ici. Tu propose simplement une nouvelle maniere de l'implémenter, il me semble (peut-etre plus efficace, mais il faudrait faire des benchs).

                                                      Citation : candide

                                                      L'intérêt de l'exercice ne réside pas dans le tirage (et qui est même complètement artificiel puisque dans la réalité il y a deux joueurs indépendants).


                                                      Oui, bien d'accord. Avant de continuer, je tiens à préciser que j'ai repris presque mot pour mot l'énoncé du forum C++. C'est criticable en soi, mais je ne peux pas vraiment justifier chaque point de l'exo.

                                                      Citation : candide

                                                      Par ailleurs, la limitation des 9 caractères est très artificielle, imagine par exemple que je cherche le plus long du lexique et constitué de lettres toutes différentes, autrement dit issues du tirage des 26 lettres de l'alphabet. D'ailleurs, un site comme CELUI-CI propose une recherche à partir d'un tirage jusqu'à 15 lettres (ce qui reste encore une restriction artificielle).


                                                      Je ne suis absolument pas d'accord. Je suppose que cette limitation provient de l'émission télévisée (que je n'ai que tres rarement vu, et dont je ne me souviens pas), et qu'elle laisse justement la place à d'autres approches que celle proposée au début du fil. (attends avant de taper, je vais y revenir plus bas ;) )

                                                      Citation : candide

                                                      Enfin, je pense que ton code tel quel ne peut traiter ce genre de cas puisque tu utilises la fonction combinations et dont la complexité est exponentielle. Par exemple, si je modifie ton code pour le tirage aaaaaaaaaaaaaaaaaaaaaaa (23 fois la lettre a), ton programme met plus de 10 secondes à répondre. De même si j'entre le tirage 'azertyuiopmlkjhgfdsqwxcvbn', ton code met plus d'une minute. Le code de Gurney traite sans problème et rapidement une entrée de n'importe quelle taille.


                                                      Je pense que tous les éléments de réponse se trouvent dans la discussion qu'on a eu ci-dessus. Je reprend les points principaux, de mon point de vue :

                                                      On est ici dans un cadre difficilement généralisable, car la complexité depend de 2 facteurs indépendants : la taille du dictionnaire (mettons N), et la longueur du mot à rechercher (mettons M). Maintenant, on a (pour l'instant) 2 approches possible, l'une en O(M2), et l'autre en O(N*M). Laquelle est la meilleure ? Impossible de repondre, il me semble, car le contexte qui va jouer.

                                                      On peut sans problème trouver des cas ou N est largement supérieur a M2 (bon, pour M un peu grand, il ne s'agira plus des mots d'une langue, j'imagine). Maintenant, ton second exemple [tirage de 'azertyuiopmlkjhgfdsqwxcvbn'] est effectivement interessant, mais c'est quand même un cas particulier et une autre problématique : trouver le mot le plus long sans répétitions de caracteres. Si par exemple on donne le choix de l'alphabet utilisé, donc la place pour des tirages multiples, peut-etre existe-il des approches specifiques pour un tel problème (je n'y ai pas réfléchi).

                                                      <hs>Au passage, tres sympa le site pour mots croisés :) .
                                                      Je viens de tomber sur celui-ci, qui a l'air excellent, on pourrait en tirer pas mal d'exos.</hs>

                                                      Citation : candide

                                                      Sinon l'idée de l'utilisation de l'ordonnancement alphabétique des lettres de chaque mot a aussi été proposé par Grinwik.


                                                      Oui, mais non. Cette idée n'est pas tout, et l'approche proposé par Grinwik est tout autre.

                                                      Citation : candide

                                                      Je pense qu'il faudrait demander dans le post original que le code soit accompagné de la version de Python utilisée.


                                                      OK.

                                                      EDIT : proposition d'une methode "mixte" plus bas
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        11 août 2011 à 9:40:25

                                                        Citation : candide

                                                        Citation : Grinwik


                                                        Il suffit ensuite de chercher toutes les chaines générées qui constituent le début des lettres du tirage elles aussi triées.



                                                        Pourquoi le début ?


                                                        Bonne question.. bug de neuronnes ! Merci.


                                                        Citation : fred1599

                                                        Edit : J'ai vu qu'il y avait des erreurs, j'essaierai de les résoudre aujourd'hui


                                                        Je n'ai pas fait attention aux erreurs, mais le style me gène vraiment : okay pour découper le code en fonctions afin d'en faciliter la lecture mais je trouve que tu vas trop loin ;)
                                                        Par exemple :
                                                        - les lignes 6 à 14 peuvent être remplacé par un dict(zip(mots, mots_ord))
                                                        - Cette ligne :
                                                        mots_ord = [mot for mot in ordonne(mots)]
                                                        pourrait se réécrire :
                                                        mots_ord = [ordre(mot) for mot in mots]
                                                        et plus besoin d'ordonne().
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                        Anonyme
                                                          11 août 2011 à 11:04:44

                                                          Citation

                                                          Je n'ai pas fait attention aux erreurs, mais le style me gène vraiment : okay pour découper le code en fonctions afin d'en faciliter la lecture mais je trouve que tu vas trop loin ;)
                                                          Par exemple :
                                                          - les lignes 6 à 14 peuvent être remplacé par un dict(zip(mots, mots_ord))
                                                          - Cette ligne :
                                                          mots_ord = [mot for mot in ordonne(mots)]
                                                          pourrait se réécrire :
                                                          mots_ord = [ordre(mot) for mot in mots]
                                                          et plus besoin d'ordonne().



                                                          Je suis d'accord, la 1ère recherche est une bonne organisation et donc à 3h du matin, j'avais pas trop à coeur l'optimisation du code et des simplifications à faire dessus. :-°

                                                          Merci des conseils.
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            11 août 2011 à 11:20:44

                                                            Re-bonjour,

                                                            Comme il m'est difficile de me décider entre les deux approches qui ont été évoquées, je propose un mix des deux (on évalue laquelle est la plus avantageuse, et on l'utilise) :

                                                            Python 3.2
                                                            from io import *
                                                            from itertools import combinations
                                                            from collections import defaultdict
                                                            from random import choice
                                                            from time import time
                                                            
                                                            
                                                            words = defaultdict(list)
                                                            
                                                            
                                                            def search_for1(letters):
                                                                ret = []
                                                                for sz in range(len(letters), 0, -1):
                                                                    for _letters in combinations(letters, sz):
                                                                        key = ''.join(sorted(_letters))
                                                                        if key in words:
                                                                            ret += words[key]
                                                                    if ret != []:
                                                                        return sz, list(set(ret))
                                                                return 0, []
                                                            
                                                            def search_for2(letters):
                                                                letters = sorted(letters)
                                                                d = defaultdict(list)
                                                                for key in words.keys():
                                                                    i,j = 0,0
                                                                    while j < len(key) and i < len(letters):
                                                                        if key[j] != letters[i]:
                                                                            i += 1
                                                                        else:
                                                                            i += 1
                                                                            j += 1
                                                                    if j == len(key):
                                                                        d[len(key)].extend(words[key])
                                                                best_len = max(d.keys())
                                                                return best_len, d[best_len]
                                                            
                                                            def search_for(letters):
                                                                if 2 ** len(letters) > len(words):
                                                                    print('  use v2; O('+str(len(words))+')')
                                                                    return search_for2(letters)
                                                                else:
                                                                    print('  use v1; O('+str(2 ** len(letters))+')')
                                                                    return search_for1(letters)
                                                            
                                                            
                                                            # chargement du dictionnaire
                                                            tstart = time()
                                                            infile = open('liste_finale.txt', 'r')
                                                            wc = 0
                                                            while True:
                                                                line = infile.readline()
                                                                if line == str(): break
                                                                wc += 1
                                                                line = line.strip('\n')
                                                                key = ''.join(sorted(line)).replace('-','')
                                                                words[key].append(line)
                                                            infile.close()
                                                            tend = time()
                                                            print('Chargement du dictionnaire... ', end='')
                                                            print('ok [{0:.6f}s]'.format(tend - tstart))
                                                            print(wc, 'mots chargés;', len(words), ' cases utilisées. ', len(words)/wc, '%\n')
                                                            
                                                            
                                                            # boucle principale
                                                            while True:
                                                                t = input('Entrez un tirage : ').strip('\n')
                                                                tstart = time()
                                                                sz, lst = search_for(t)
                                                                tend = time()
                                                                print('mots de ' + str(sz) + ' lettres trouves [{0:.6f}s] : '.format(tend - tstart), lst, end='\n\n')
                                                            



                                                            Chargement du dictionnaire... ok [2.714000s]
                                                            323578 mots chargés; 273878  cases utilisées.  0.8464048853753964 %
                                                            
                                                            Entrez un tirage : qwertzuiopasdfghjklyxcvbnm
                                                              use v2
                                                            mots de 14 lettres trouves [3.371000s] :  ['stylographique', 'xylographiques']
                                                            
                                                            Entrez un tirage : sinusamor
                                                              use v1
                                                            mots de 9 lettres trouves [0.020000s] :  ['sous-marin', 'marsouins']
                                                            
                                                            Entrez un tirage : jhejvhbgehfckjslaloi
                                                              use v2
                                                            mots de 10 lettres trouves [2.642000s] :  ['bolchevisa', 'echolalies', 'bolchevise', 'globalisee', 'bolcheviks']
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                            Anonyme
                                                              11 août 2011 à 13:09:37

                                                              Le code précédent n'était pas toujours fonctionnel (manquait certains résultats), j'ai recodé autrement.

                                                              Je laisse coupé en pas mal de fonction pour que se soit bien compréhensible, pour l'instant ça à l'air fonctionnel, faut encore tester.

                                                              J'ai ajouté toutes les solutions possibles, qui permettent aussi d'utiliser le code pour un jeu de scrabble par exemple.

                                                              Voilà le code

                                                              #!/usr/bin/python
                                                              # -*- coding:utf8 -*-
                                                              
                                                              from itertools import permutations
                                                              
                                                              def ordonner(chaine):
                                                                  return ''.join(set(chaine))
                                                              
                                                              
                                                              def solutions(chaine):
                                                                  ch = ordonner(chaine)
                                                                  for a in xrange(len(ch), 0, -1):
                                                                      for i in permutations(ch, a):
                                                                          yield i
                                                              
                                                              def compare(chaine, listes_mots):
                                                                  liste = [''.join(list(i)) for i in solutions(chaine)]
                                                                  for mot in liste:
                                                                      if mot in listes_mots:
                                                                          yield mot
                                                              
                                                              def ma_liste():
                                                                  FICHIER = 'dico.txt'
                                                                  with open(FICHIER, 'r') as f:
                                                                      liste = f.readlines()
                                                                  return [mot.strip('\n') for mot in liste]
                                                              
                                                              def rechercher(ch):
                                                                  return [res for res in compare(ch, l) \
                                                                  if len(ch) >= len(res)]
                                                              
                                                              l = ma_liste()
                                                              char = raw_input('Entrer une chaine : ').upper()
                                                              
                                                              resultats = [m for m in rechercher(char) if len(m) <= len(char)]
                                                              
                                                              print '\n'.join([mot for mot in resultats if len(mot) == len(resultats[0])])
                                                              


                                                              La vitesse est pas très rapide mais reste acceptable jusqu'à 10 ou 11 caractères

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              [Exercice] des chiffres et des lettres

                                                              × 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