CODEWITHSUNDEEP
puzzlemorse-code
giodamelio
giodamelio

Reputation: 5605

Translating Morse code with no spaces

I have some Morse code that has lost the spaces in between the letters, my challenge is to find out what the message says. So far I have been kinda lost because of the sheer amount of combinations there might be.

Here is all the info on the messages I have.

Does anyone have a clever solution?

Upvotes: 6

Views: 20778

Answers (3)

user97370
user97370

Reputation:

This is not an easy problem, because as ruakh suggested there are many viable sentences to a given message. For example 'JACK AND JILL WENT UP THE HILL' has the same encoding as 'JACK AND JILL WALK CHISELED'. Since these are both grammatical sentences and the words in each are common, it's not obvious how to pick one or the other (or any other of the 40141055989476564163599 different sequences of English words that have the same encoding as this message) without delving into natural language processing.

Anyway, here's a dynamic programming solution to the problem of finding the shortest sentence (with the fewest characters if there's a tie). It can also count the total number of sentences that have the same encoding as the given message. It needs a dictionary of English words in a file.

The next enhancements should be a better measure of how likely a sentence is: perhaps word frequencies, false-positive rates in morse (eg, "I" is a common word, but it appears often as part of other sequences of morse code sequences). The tricky part will be formulating a good score function that can be expressed in a way that it can be computed using dynamic programming.

MORSE = dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [
    '.-', '-...', '-.-.', '-..', '.', '..-.', '--.', '....',
    '..', '.---', '-.-', '.-..', '--', '-.', '---', '.--.',
    '--.-', '.-.', '...', '-', '..-', '...-', '.--', '-..-',
    '-.--', '--..'
]))

# Read a file containing A-Z only English words, one per line.
WORDS = set(word.strip().upper() for word in open('dict.en').readlines())
# A set of all possible prefixes of English words.
PREFIXES = set(word[:j+1] for word in WORDS for j in xrange(len(word)))

def translate(msg, c_sep=' ', w_sep=' / '):
    """Turn a message (all-caps space-separated words) into morse code."""
    return w_sep.join(c_sep.join(MORSE[c] for c in word)
                      for word in msg.split(' '))

def encode(msg):
    """Turn a message into timing-less morse code."""
    return translate(msg, '', '')

def c_trans(morse):
    """Construct a map of char transitions.

    The return value is a dict, mapping indexes into the morse code stream
    to a dict of possible characters at that location to where they would go
    in the stream. Transitions that lead to dead-ends are omitted.
    """
    result = [{} for i in xrange(len(morse))]
    for i_ in xrange(len(morse)):
        i = len(morse) - i_ - 1
        for c, m in MORSE.iteritems():
            if i + len(m) < len(morse) and not result[i + len(m)]:
                continue
            if morse[i:i+len(m)] != m: continue
            result[i][c] = i + len(m)
    return result

def find_words(ctr, i, prefix=''):
    """Find all legal words starting from position i.

    We generate all possible words starting from position i in the
    morse code stream, assuming we already have the given prefix.
    ctr is a char transition dict, as produced by c_trans.
    """
    if prefix in WORDS:
        yield prefix, i
    if i == len(ctr): return
    for c, j in ctr[i].iteritems():
        if prefix + c in PREFIXES:
            for w, j2 in find_words(ctr, j, prefix + c):
                yield w, j2

def w_trans(ctr):
    """Like c_trans, but produce a word transition map."""
    result = [{} for i in xrange(len(ctr))]
    for i_ in xrange(len(ctr)):
        i = len(ctr) - i_ - 1
        for w, j in find_words(ctr, i):
            if j < len(result) and not result[j]:
                continue
            result[i][w] = j
    return result

def shortest_sentence(wt):
    """Given a word transition map, find the shortest possible sentence.

    We find the sentence that uses the entire morse code stream, and has
    the fewest number of words. If there are multiple sentences that
    satisfy this, we return the one that uses the smallest number of
    characters.
    """
    result = [-1 for _ in xrange(len(wt))] + [0]
    words = [None] * len(wt)
    for i_ in xrange(len(wt)):
        i = len(wt) - i_ - 1
        for w, j in wt[i].iteritems():
            if result[j] == -1: continue
            if result[i] == -1 or result[j] + 1 + len(w) / 30.0 < result[i]:
                result[i] = result[j] + 1 + len(w) / 30.0
                words[i] = w
    i = 0
    result = []
    while i < len(wt):
        result.append(words[i])
        i = wt[i][words[i]]
    return result

def sentence_count(wt):
    result = [0] * len(wt) + [1]
    for i_ in xrange(len(wt)):
        i = len(wt) - i_ - 1
        for j in wt[i].itervalues():
            result[i] += result[j]
    return result[0]

msg = 'JACK AND JILL WENT UP THE HILL'
print sentence_count(w_trans(c_trans(encode(msg))))
print shortest_sentence(w_trans(c_trans(encode(msg))))

Upvotes: 8

user97370
user97370

Reputation:

Maintain 3 things: a list of words so far S, the current word so far W, and the current symbol C.

  • S should be only good words, eg. 'THE QUICK'
  • W should be a valid prefix of a word, eg. ['BRO']
  • C should be a valid prefix of some letter, eg. '.-'

Now, given a new symbol, let's say '-', we extend C with it (in this case we get '.--'). If C is a complete letter (in this case it is, the letter 'W'), we have a choice to add it to W, or to continue extending the letter further by adding more symbols. If we extend W, we have a choice to add it to S (if it's a valid word), or to continue extending it further.

This is a search, but most paths terminate quickly (as soon as you have W not being a valid prefix of any word you can stop, and as soon as C isn't a prefix of any letter you can stop).

To get it more efficient, you could use dynamic programming to avoid redundant work and use tries to efficiently test prefixes.

What might the code look like? Omitting the functions 'is_word' which tests if a string is an English word, and 'is_word_prefix' which tests if a string is the start of any valid word, something like this:

morse = {
    '.-': 'A',
    '-...': 'B',
    etc.
}

def is_morse_prefix(C):
    return any(k.startswith(C) for k in morse)

def break_words(input, S, W, C):
    while True:
        if not input:
            if W == C == '':
                yield S
            return
        i, input = input[0], input[1:]
        C += i
        if not is_morse_prefix(C):
            return
        ch = morse.get(C, None)
        if ch is None or not is_word_prefix(W + ch):
            continue
        for result in break_words(input, S, W + ch, ''):
            yield result
        if is_word(W + ch):
            for result in break_words(input, S + ' ' + W + ch, '', ''):
                yield result

for S in break_words('....--', [], '', ''):
    print S

Upvotes: 0

ruakh
ruakh

Reputation: 183371

I don't know if this is "clever", but I would try a breadth-first search (as opposed to the depth-first search implicit in BRPocock's regex idea). Suppose your string looks like this:

.---.--.-.-.-.--.-...---...-...-..
J   A C   K  A N D  J   I L   L

You start out in state ('', 0) ('' being what you've decoded so far; 0 being your position in the Morse-code string). Starting from position zero, possible initial characters are . E, .- A, .-- W, .--- J, and .---- 1. So, push states ('E', 1), ('A', 2), ('W', 3), ('J', 4), and ('1', 5) onto your queue. After dequeuing state ('E', 1), you would enqueue states ('ET', 2), ('EM', 3), and ('EO', 4).

Now, your queue of possible states will grow quite quickly — both of { ., - } are letters, as are all of { .., .-, -., -- } and all of { ..., ..-, .-., .--, -.., -.-, --., --- }, so in each pass your number of states will increase by a factor of at least three — so you need to have some mechanism for user feedback. In particular, you need some way to ask your user "Is it plausible that this string starts with EOS3AIOSF?", and if the user says "no", you will need to discard state ("EOS3AIOSF", 26) from your queue. The ideal would be to present the user with a GUI that, every so often, shows all current states and lets him/her select which ones are worth proceeding with. ("The user" will also be you, of course. English has a shortage of pronouns: if "you" refers to the program, then what pronoun refers to the user-programmer?!)

Upvotes: 0

Related Questions