Déchiffrer le mot Python désembrouilleur

Question

J'essaye actuellement de creuser profondément dans python et j'ai trouvé un défi sur (hackthissite.org) que j'essaye de casser. Je dois déchiffrer 10 mots qui se trouvent dans la liste de mots fournie.

def permutation(s): 
    if s == "": 
     return [s] 
    else: 
     ans = [] 
     for an in permutation(s[1:]): 
      for pos in range(len(an)+1): 
       ans.append(an[:pos]+s[0]+an[pos:]) 
     return ans 

def dictionary(wordlist): 
    dict = {} 
    infile = open(wordlist, "r") 
    for line in infile: 
     word = line.split("\n")[0] 
     # all words in lower case!!! 
     word = word.lower() 
     dict[word] = 1 
    infile.close() 
    return dict 

def main(): 
    diction = dictionary("wordlist.txt") 
    # enter all the words that fit on a line or limit the number 
    anagram = raw_input("Please enter space separated words you need to unscramble: ") 
    wordLst = anagram.split(None) 

    for word in wordLst: 
     anaLst = permutation(word) 
     for ana in anaLst: 
      if diction.has_key(ana): 
       diction[ana] = word 
       #print "The solution to the jumble is" , ana 
    solutionLst = [] 
    for k, v in diction.iteritems(): 
     if v != 1: 
      solutionLst.append(k) 
      print "%s unscrambled = %s" % (v, k) 
    print solutionLst 

main() 

La permutation de fonction semble être le bloc de code qui effectue le déchiffrement. Pouvez-vous m'aider à comprendre comment cela résout ce problème par programme?

Answer 1

Le pseudo-code pour cela ressemble à quelque chose comme:

Load the word list (dictionary) 
Input the words to unscramble 
For each word: 
    Find every permutation of letters in that word (permutation) 
    For each permutation: 
    Add this permutation to the solution list if it exists in the dictionary 
Print the solutions that were found. 

La fonction dictionnaire() est alimenter votre liste de mots à partir d'un fichier.

La fonction permutation() renvoie toutes les permutations de lettres dans un mot donné.

---

La fonction de permutation() est la manière suivante:

for an in permutation(s[1:]): 

s [1:] renvoie la chaîne avec le premier caractère tronqué. Vous verrez qu'il utilise la récursivité pour appeler à nouveau permutation() jusqu'à ce qu'il n'y ait plus de caractères à tronquer du front. Vous devez connaître la récursivité pour comprendre cette ligne. L'utilisation de la récursivité permet à cet algorithme de couvrir tout nombre de lettres tout en restant élégant.

for pos in range(len(an)+1): 

Pour chaque position de lettre restante.

ans.append(an[:pos]+s[0]+an[pos:]) 

Generate la permutation en déplaçant la première lettre (qui nous tronqués précédemment) à chacune des positions entre toutes les autres lettres.

---

Donc, prenez le mot "watch" par exemple. Après récursion, il y aura une boucle qui génère les mots suivants:

awtch atwch atcwh atchw

Tout ce que je l'ai fait pour générer ces mots était de prendre la première lettre et déplacer sa position. Continuez cela, combiné avec la troncature des lettres, et vous créerez toutes les permutations.

(wow, ce doit être ma plus longue encore de réponse)

Answer 2

Il y a une solution beaucoup mieux. Ce code est très inefficace s'il y a beaucoup de mots longs. Une meilleure idée est de trier lexicographiquement tous les mots du dictionnaire, de sorte que «dieu» devienne «dgo» et fasse de même pour les mots brouillés. Alors c'est O (nlogn) pour chaque mot au lieu de O (n!)

Answer 3

J'ai aussi écrit ce code pour ce site. code de travail ci-dessous:

def import_dictionary(): 
    dictionary = [] 
    try: 
     file = open("C:\\Users\\Mason\\Desktop\\diction.txt", "r")#location of your dictionary or provided wordlist 
     fileContents = file.readlines() #read text file and store each new line as a string 
    finally: 
     file.close() 
    for i in range(len(fileContents)): 
     dictionary.extend(fileContents[i].split()) #changes the list by removing \n's from line breaks in text file 
    return dictionary 

def import_scrambled_words(): 
    scrambledWords = [] 
    try: 
     file = open("C:\\Users\\Mason\\Desktop\\scrambled.txt", "r") #location of your scrambled word file 
     fileContents = file.readlines() #read text file and store each new line as a string 
    finally: 
     file.close() 
    for i in range(len(fileContents)): 
     scrambledWords.extend(fileContents[i].split()) #changes the list by removing \n's from line breaks in text file 
    return scrambledWords 

def unscramble_word(scrambledWord): 
    countToMatch = len(scrambledWord) 
    matchedWords = [] 
    string = "" 

    for word in dictionary: 
     count = 0 
     for x in scrambledWord: 
      if x in word: 
       count += 1 
      if count == countToMatch: 
       matchedWords.append(word) 
       break 
    for matchedWord in matchedWords: 
     if len(matchedWord) == len(scrambledWord): 
      print(matchedWord) 
      string = matchedWord 
      break #this returns only one unscrambles word 
    return string 

if __name__ == '__main__': 
    finalString = "" 
    try: 
     scrambled = import_scrambled_words() 
     print(scrambled) 
     dictionary = import_dictionary() 
     for x in scrambled: 
      finalString += unscramble_word(x) 
      finalString +=", " 
     len(finalString) 

     print(finalString) 

    except Exception as e: 
     print(e) 

Ce code lu à partir d'un fichier enregistré des mots brouillés et vérifier contre une liste de mots (je un dictionnaire dans mon cas juste pour être en sus). Pour battre le défi dans les 30 secondes allouées, j'ai copié collé à partir de hackThissite et collé à mon fichier de mots brouillés. enregistré. a couru le programme et copié collé la sortie de ma console python.