打印出模棱两可的摩尔斯电码的所有可能性

Question

我的任务是解决学校的问题，这让我很困惑。我要做的是读入一个模棱两可的摩尔斯电码字符串（即没有任何空格来说明什么是字母，什么不是）并打印出所有可能的 valid 英文翻译莫尔斯电码可能是。我在互联网上的某个地方看到了解决这个确切问题的算法，但不知道如何将其转换为 Python 3，而且我一辈子都找不到它。

一些有用的东西：

我有一个程序认为有效的单词列表：Download
程序不需要输出语法正确的句子，只输出构成有效单词且在words.txt.
定义一个句子是否有效的一些额外的事情是句子不能有两个相同的词；所有单词必须是唯一的，并且句子中不能超过一个单字母单词和一个双字母单词。

我的代码，目前不完整，但将所有单词分类为相应的摩尔斯电码定义：

# Define the mapping from letter to Morse code.
CODES = {
    'A': '.-',
    'B': '-...',
    'C': '-.-.',
    'D': '-..',
    'E': '.',
    'F': '..-.',
    'G': '--.',
    'H': '....',
    'I': '..',
    'J': '.---',
    'K': '-.-',
    'L': '.-..',
    'M': '--',
    'N': '-.',
    'O': '---',
    'P': '.--.',
    'Q': '--.-',
    'R': '.-.',
    'S': '...',
    'T': '-',
    'U': '..-',
    'V': '...-',
    'W': '.--',
    'X': '-..-',
    'Y': '-.--',
    'Z': '--..',
}
words={}

f=open('words.txt').read()
a=f
for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
  a=a.replace(i,CODES[i])
f=f.split('\n')
a=a.split('\n')
for i in f:
      words[i]=a[f.index(i)]
    q=input('Morse: ')

一个示例测试用例是如何工作的：

Morse: .--....-....-.-..-----.
A BED IN DOG
A DID IN DOG
A BLUE DOG
A TEST IF DOG
WEST I IN DOG
WEST EVEN A ON
WEST IF DOG

Answer 1

要完成该程序，您需要使用递归算法，因为单词的可能组合非常多。

我已经更改了您的变量名称，以便于理解它们保存的数据。

decode函数用作递归算法。第一行检查 Morse 是否为空，因此不需要运行函数，因为它是终点，它打印该分支的输出。

函数的其余部分将检查是否可以用前 i 个字母组成单词。 i 从 1 开始，因为这是最短的字母，最大长度是文件中的最大摩尔斯长度。 while 循环还通过检查 i 是否不大于莫尔斯码的长度来检查是否未发生越界错误。

代码无法更改函数的参数，因为在同一函数中可能会发现其他单词导致冲突，因此为更改后的英语和摩尔斯语创建了新变量。检查是否重复并允许可能的单词长度。

from string import ascii_uppercase

#Defines the letter to Morse mapping
code = {
    'A': '.-',
    'B': '-...',
    'C': '-.-.',
    'D': '-..',
    'E': '.',
    'F': '..-.',
    'G': '--.',
    'H': '....',
    'I': '..',
    'J': '.---',
    'K': '-.-',
    'L': '.-..',
    'M': '--',
    'N': '-.',
    'O': '---',
    'P': '.--.',
    'Q': '--.-',
    'R': '.-.',
    'S': '...',
    'T': '-',
    'U': '..-',
    'V': '...-',
    'W': '.--',
    'X': '-..-',
    'Y': '-.--',
    'Z': '--..'
}

#Opens the file and reads all words
file = open("words.txt","r")
words = file.read()
file.close()

morse = words

# Converts all words to morse
for letter in list(ascii_uppercase):
    morse = morse.replace(letter, code[letter])

# Creates list of the morse and english words from strings
morsewords = morse.split("\n")
engwords = words.split("\n")

# Finds the max length of morse words
maxlength = max([len(i)] for i in morsewords)[0]

# Creates a dictionary of {morse words : english words}
words = dict(zip(morsewords, engwords))

# MorseInput = input("Morse code :")
MorseInput = ".--....-....-.-..-----."

# This is the recursive function
def decode(morse, eng="", oneWord=False, twoWord=False):
    # Print the english when finished
    if morse == "":
        print(eng)
    else:
        i = 1
        # While loop allows to go through all possWord where condition met
        while len(morse) >= i and i <= maxlength:
            possWord = morse[:i]
            # Checks if the word is a real word
            if possWord in words.keys():
                # Real word therefore add to english and the morse
                newEng = eng + " " + words[possWord]
                newMorse = morse[i:]
                # Checks if that not more than one, One length word used
                if len(words[possWord]) == 1:
                    if not oneWord:
                        decode(newMorse, newEng, True, twoWord)
                # Checks if that not more than one, Two length word used
                elif len(words[possWord]) == 2:
                    if not twoWord:
                        decode(newMorse, newEng, oneWord, True)
                # Word is greater than two so doesn't matter
                else:
                    decode(newMorse, newEng, oneWord, twoWord)                    
            i += 1


decode(MorseInput)

我希望我的评论有意义。

我确信代码可以做得更好更短，但我在一个小时内就完成了。

它打印

A TEST IF DOG
A DID IN DOG
A BLUE DOG
WEST I IN DOG
WEST IF DOG
WEST EVEN A ON

打印出模棱两可的摩尔斯电码的所有可能性

Printing out all the possibilites of ambiguous Morse code

python

morse-code