Partage

[Exercice] solveur de mots-croisés

pour débutants

23 août 2011 à 18:16:20

Bonjour,

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


Objectif



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


Votre mission :


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




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

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

Pensez à indiquer la version de Python utilisée.

Bonne chance ! :)
24 août 2011 à 1:02:22

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

Voici ma solution:

import re

s = input("Entrez votre mot:")
l, c, regex = [], 0, re.compile(s.lower().strip().replace("*","."))

with open("dict.txt","r") as file:
    for mot in file:
        if len(mot.strip()) == len(s) and regex.findall(mot):
            l.append(mot.strip().title())
            c += 1

print("Nombre de mots trouvés: {}\nMots: {}".format(c,", ".join(l)))


Edit: Nouveau code avec modifications, merci Grinwik.
24 août 2011 à 2:55:37

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

@ Asimoov :
Joli code ! :)

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


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

24 août 2011 à 10:09:00

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

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

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

dictionnaire =  open( "dictionnaire.txt" ).read()

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



28 août 2011 à 0:57:55

Oh pas bête la guêpe !

L'exercice semble très intéressants, je le ferrais en C :)
Étudiant - Codeur en C | Articles | Mes projets                                                                 ache.one         Copying is an act of love.    -   
28 août 2011 à 1:40:34

Citation : @che


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



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

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

Je suis actuellement un peu occupé, mais je vais réessayé.
Étudiant - Codeur en C | Articles | Mes projets                                                                 ache.one         Copying is an act of love.    -   
28 août 2011 à 6:55:52

Ah excellent Lord Casque Noir.
28 août 2011 à 9:45:22

Citation : Lord Casque Noir

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

dictionnaire =  open( "dictionnaire.txt" ).read()

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



Joli ! :)

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

Mon code original :
from io import *
import re
from time import time


def load_dico(filename):
    # chargement du dictionnaire
    tstart = time()
    with open(filename, 'r') as infile:
        words = [line.strip('\n') for line in infile]
    print('Chargement du dictionnaire... ', end='')
    print('ok, {0} mots chargés [{1:.6f}s]'.format(len(words), time() - tstart))
    return words

def search_for(pattern, dico):
    reg = re.compile('^' + pattern.replace('*', '\w') + '$')
    return [word for word in dico if reg.match(word)]

dico = load_dico('liste_finale.txt')
# boucle principale
while True:
    pattern = input('Entrez un mot (exemple : a**) : ').strip('\n')
    tstart = time()
    words = search_for(pattern, dico)
    print(repr(words) + ' [{0:.6f}s] '.format(time() - tstart), end='\n\n')


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

Entrez un mot (exemple : a**) : sar**o**
['sarcloir', 'sarclons'] [0.305000s]


Code modifié :
from io import *
import re
from time import time


def load_dico(filename):
    # chargement du dictionnaire
    tstart = time()
    with open(filename, 'r') as infile:
        words = infile.read()
    print('Chargement du dictionnaire... ', end='')
    print('ok, {0} mots chargés [{1:.6f}s]'.format(len(words), time() - tstart))
    return words

def search_for(pattern, dico):
    return re.compile('^' + pattern.replace('*', '\w') + '$', re.MULTILINE).findall(dico)
    
dico = load_dico('liste_finale.txt')
# boucle principale
while True:
    pattern = input('Entrez un mot (exemple : a**) : ').strip('\n')
    tstart = time()
    words = search_for(pattern, dico)
    print(repr(words) + ' [{0:.6f}s] '.format(time() - tstart), end='\n\n')


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


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

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

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

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

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

J'ai essayer de voir comment je pourrais faire.
Au début, j'ai essayer de faire un truc que l'on pourrait réutiliser plus rapidement donc j'ai utilisé les dico :
# -*-coding:utf-8 -*

# Permet la comparaison entre les chaines à trou (stringh) et les mots
# Ben quoi ? Je connais pas encore les regex en Python  
def strhcmp(string, stringh):
  i = 0
  stringh = stringh.lower()
  for Char in string.lower():
    if Char != stringh[i] and stringh[i] != '*':
      return False
    i+=1
  return True

# On lit le fichier
dicoMot = {}
with open("dico.txt", "r") as fichierDico:
  listMot = fichierDico.read().split()


# On classe les mots en fonction de leur taille
for string in listMot:
  if len(string) not in dicoMot.keys():
    dicoMot[len(string)] = []
  dicoMot[len(string)] += [string]

mot = ""
while 1:
  mot = input()
  if mot.lower() in ["quit", "q", "exit"]:
    break
  # On regarde dans la liste correspondant à la taille de mot s'il n'y a pas un mot qui pourrait passez  
  for string in dicoMot[len(mot)]:
    if strhcmp(string, mot):
      print string


Et ensuite j'ai essayer faire seulement l'exercice sans me préoccuper d'autre chose :
# -*-coding:utf-8 -*

mot = "*ache"
# Même fonction que le premier code
def strhcmp(string, stringh):
  i = 0
  stringh = stringh.lower()
  for Char in string.lower():
    if Char != stringh[i] and stringh[i] != '*':
      return False
    i+=1
  return True

dicoMot = {}
with open("dico.txt", "r") as fichierDico:
  listMot = fichierDico.read().split()
# On garde uniquement les mots qui on la même taille que mot
listMot = [string for string in listMot if len(string) == len(mot)]

# Et on regarde si y en a pas un qui passe  
for string in listMot:
  if strhcmp(string, mot):
    print string

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


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

Je précise que je n'ai pas encore fini le tuto (donc que je maitrise pas du tout python). J'essayerais de comprendre vos code dès que j'ai fini le tuto.
Étudiant - Codeur en C | Articles | Mes projets                                                                 ache.one         Copying is an act of love.    -   
30 août 2011 à 20:37:29

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

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


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


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

#ceci
if Char != stringh[i] and stringh[i] != '*':
    #...

# en ceci
if stringh[i] not in (Char, '*'):
30 août 2011 à 20:41:46

Citation : Fayden

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


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

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

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

Merci
Étudiant - Codeur en C | Articles | Mes projets                                                                 ache.one         Copying is an act of love.    -   
2 septembre 2011 à 12:03:04

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

#-*-coding:Latin-1-*

import re

continuer=True
print("***Solveur de mot croisés***\n\n")

with open("dictionnaire.txt") as fichier:
    dictionnaire = str(fichier.read())
dictionnaire = dictionnaire.split("\n")

while continuer==True:
    mot_cache = input("\nEntre un mot (remplace les lettres manquantes par '*': ")
    try:
        if not re.search("^([\*?a-z]){2,}$", mot_cache):
            raise ValueError
    except ValueError:
        mot_cache = input("Mor invalide :\n\
Entre un mot (remplace les lettres manquantes par '*': ")
    expression = "^" + re.sub("\*", "[a-z]", mot_cache) + "$"
    print("Liste des mots correspondants: ")
    for mot in dictionnaire:
        if re.search(expression, mot):
            print(mot)
4 septembre 2011 à 12:23:29

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

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

# -*- coding:utf-8 -*-
# solveur de mots croisés

class Dico(object):
    """La classe pour contenir le dictionnaire des mots
       Les mots sont triés dans des listes en fonction de leur longueur
    """
    def __init__(self):
        self.dico = []
        for i in range(26):
            #liste de 26 listes. Mot le plus long =25lettres
            self.dico.append([])

    def remplissage_dico(self):
        # ouverture du fichier
        self.f = open("chiffres_lettres_dico.txt", "r")

        # boucle pour remplir le dictionnaire

        word = self.f.readline()    #pour sauter la première ligne
        longueur = 0    #pour gérer les listes en fonction du nombre de lettres

        while 1:
            word = self.f.readline().strip('\n')
            if word=='':
                break
            else:
                longueur = len(word)
                self.dico[longueur].append(word)

        # fermeture du fichier
        self.f.close()

        return self.dico


class Application(object):
    """Corps de l'application"""
    def __init__(self):
        self.dico = Dico().remplissage_dico()
        self.mot_trouve = []

    def quel_mot(self):
        mot = input('Veuillez entrer un mot de la forme "t*s*": ').strip("\r")
        # on sélectionne le dico correspondant au nombre de lettres
        dico = self.dico[len(mot)]

        for m in dico:
            d = True
            for i, l in enumerate(mot):
                if l != '*' and l != m[i]:
                    d = False
            if d:
                self.mot_trouve.append(m)

        print("Les mots trouvés sont : {}".format(self.mot_trouve))


if __name__ == '__main__':
    test = Application().quel_mot()

[Exercice] solveur de mots-croisés

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