Printing out all the possibilites of ambiguous Morse code

Question

I've been tasked with a problem for school and it's left me stumped. What I have to do is read in an ambiguous Morse Code string (i.e. without any spaces to state what is a letter and what is not) and print out what all the possible valid english translations for that Morse Code could be. I've seen an algorithm to solve this exact problem somewhere on the internet but have no idea how to convert it to Python 3 and can not find it for the life of me.

Some helpful things:

• I have a list of words which the program considers valid: Download

• The program does not need to output gramatically correct sentences, only sentences that form words that are valid and in words.txt.

• Some extra things that define if a sentence is valid or not is that the sentence cannot have two identical words; all words must be unique, and there cannot be more than one 1-letter word and one 2-letter word in the sentence.

• My code, which at the moment is incomplete but sorts all the words into their corresponding Morse Code definitions:

  # 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: ')
  

An example test case of how this would work is:

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

To complete the program, you need to use a recursive algorithm as there are so many possible combinations of words.

I have changed your variable names so that they are easy to understand what data they hold.

The decode function is used as a recursive algorithm. The first line checks if the Morse is empty so no need to run the function as it is a finishing point, it prints the output of that branch.

The rest of the function will check if a word is possible to make out of the first i letters. i starts at 1 as this is the shortest letter and the max length is the max Morse length in the file. The while loop also checks that an out of bound error does not occur by checking that i is not greater than the length of Morse.

The code can't change the function's arguments as other word could be found in the same functions causing a clash so new variable are created for the changed English and Morse. Checks that if the length of possible word has been repeated and allowed.

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)

I hope that my comments make some sense.

I am sure that the code could be made better and shorter but I did it in under an hour.

It prints

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