Search code examples
pythondecodemorse-code

Python, find all the possible letter combinations in given morse code

I had to find all the possible letter combinations in a given morse code. The length of the decoded word can be maximum 10 letters. The given file with the letters and the morse code to it looks like this:

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   --..

The given morse code is this:

morse = '-.----.-.-...----.-.-.-.----.-'

My code looks like this:

def morse_file_to_dict(filename):
    with open(filename) as file:
        return dict(line.strip().split() for line in file)


def word_to_morse(s, my_dict):
    return ''.join([my_dict[w] for w in s])


def adding_to_set(given_morse, my_set, my_dict, word='', start=0):
    for char in my_dict:
        if my_dict[char] == given_morse[start:start + len(my_dict[char])] and len(word) < 10:
            start = start + len(my_dict[char])
            word = word + char
            adding_to_set(given_morse, my_set, my_dict, word, start)
            if word_to_morse(word, my_dict) == given_morse:
                my_set.add(word)


words = set()
morse = '-.----.-.-...----.-.-.-.----.-'
pairs = morse_file_to_dict('morse_alphabet.txt')
adding_to_set(morse, words, pairs)
print(len(words))
print(words)

My output is:

5
{'KMCBMQRKMK', 'KMCBMGKRMQ', 'KMCBMGCKMK', 'KMNCEJCCMQ', 'KMCDAMCCMQ'}

BUT, the answer should be: 10571 words, not 5

What should i change to get all of them? Thank you for your time and answer!

Solution

  • I would suggest using recursion and a dictionary to map morse code to letters (not letters to morse code):

    morseFile="""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   --.."""

morse = {code:letter for line in morseFile.split("\n") for letter,code in [line.split()]}

    The function can be built as a generator to avoid storing all the possibilities in a big list:

    def decode(coded,maxLen=10):
    if not maxLen: return
    for size in range(1,min(4,len(coded))+1):
        code = coded[:size]
        if code not in morse: continue
        remaining = coded[size:]
        if not remaining: yield morse[code]
        for rest in decode(remaining,maxLen-1):
            yield morse[code] + rest

    output:

    print(sum(1 for _ in decode("-.----.-.-...----.-.-.-.----.-")))

10571

for string in decode("-.----.-.-...----.-.-.-.----.-"):
    if len(string)<9: print(string)

YQLWGCYQ
YQLWQRYQ
YQLJNCYQ
YQLJKRYQ
YQLJCNYQ
YQLJCKWQ
YQLJCKJK
YQLJCCMQ
YQLJCCOK