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:
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.
# -*- 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).")
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)
# -*- 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.
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()))
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.
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()))
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.
Non, pas du tout . 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 .
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()))
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.
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 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]
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.
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).
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) ?
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.
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.
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.
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 ?
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.
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
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.
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().
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.
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']
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
× 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.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.