Расшифровка Python слово расшифровывать

Question

В настоящее время я пытаюсь углубиться в python и нашел (hackthissite.org) проблему, которую я пытаюсь взломать Я должен расшифровать 10 слов, которые находятся в предоставленном списке слов.

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()

Перестановка функций выглядит так, как будто это блок кода, который фактически выполняет дешифрование. Можете ли вы помочь мне понять, как это программно решает эту проблему?

Answer 1

Псевдокод для этого выглядит примерно так:

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.

Функция dictionary () заполняет ваш список слов из файла.

Функция permutation () возвращает каждую перестановку букв в данном слове.

---

Функция permutation () выполняет следующие действия:

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

s [1:] возвращает строку с усеченным первым символом. Вы увидите, что он использует рекурсию для повторного вызова permutation () до тех пор, пока не останется символов для усечения спереди. Вы должны знать рекурсию, чтобы понять эту строку. Использование рекурсии позволяет этому алгоритму охватывать любое количество букв и при этом быть элегантным.

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

Для каждой оставшейся буквенной позиции.

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

Создайте перестановку, переместив первую букву (которую мы урезали ранее) в каждую позицию между каждой другой буквой.

---

Итак, возьмем, к примеру, слово «часы». После рекурсии будет цикл, который генерирует следующие слова:

awtch atwch atcwh atchw

Все, что я сделал, чтобы сгенерировать эти слова, это взять первую букву и изменить ее положение. Продолжайте это в сочетании с усечением букв, и вы будете создавать каждую перестановку.

(вау, это, наверное, мой самый длинный ответ)

Answer 2

Я написал этот код и для этого сайта. рабочий код ниже:

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)

Этот код будет считывать из сохраненного файла зашифрованных слов и проверять его по словарному списку (в моем случае я использовал словарь только для дополнительной информации). Чтобы справиться с задачей за отведенные 30 секунд, я скопировал копию из hackThissite и вставил в мой зашифрованный файл слов. сохранены. запустил программу и скопировал вставил вывод из моей консоли Python.

Answer 3

Существует гораздо лучшее решение. Этот код крайне неэффективен, если в нем много длинных слов. Лучшая идея состоит в том, чтобы отсортировать лексикографически все каждое слово в словаре так, чтобы «бог» стал «дго» и делал то же самое для зашифрованного слова. Тогда это O (nlogn) для каждого слова вместо O (n!)