Telegrams
A few days ago at work, a friend of mine came up with this problem. I call it the “telegram” problem: you get a string consisting of words run together without spaces, and figure out where spaces can go to separate out the words. For example, a famous misunderstanding:
parse_telegram("turkeytrotstowaterwhereistaskforcethirtyfourtheworldwonders") -- turkey trots to water where is task force thirty four the world wonders
I wrote a solution last night.
The dictionary
First things first, we’re going to need a dictionary of words. If you’re on a Mac or most Linux distros you already have one, at /usr/share/dict/words. If not, I recommend Googling for the OSPD, the Official Scrabble Player’s Dictionary.
The dictionary comes to us as a text file with one word per line. Mine, at least, contains a bunch of proper nouns, words with apostrophes, and single-letter words, which I filtered out (adding back “i” and “a,” the only two single-letter words that really exist).
We need to turn this into some kind of data structure we can easily query. Specifically, we want to quickly find out if there are any words that begin with a certain substring, for example, there are words that begin with “appl” but none that begin with “appq.” The data structure we’ll use for this is called a trie. It’s a tree with each node representing a letter, and the edges leading out of the node representing letters that could follow this one. So, for example, here’s a trie containing the words “an,” “ant,” “app,” “apple,” and “pear:”
A “$” node represents the end of a word, so, if a node has a “$” as a child, that means that letter can complete a word (but doesn’t have to, if there are other children).
So, here’s a function that reads a dictionary file, filters out the words we don’t want, and inserts them into a trie:
function load_dictionary(filename) local dictionary = {} for line in io.lines(filename) do if line:match("^%l%l+$") then insert(dictionary, line .. "$") end end -- We're cutting all single-letter words, but -- two of them are real words insert(dictionary, "a$") insert(dictionary, "i$") return dictionary end
And here’s the corresponding insert function, to actually put them in the trie:
function insert(dictionary, word) local first = word:sub(1,1) dictionary[first] = dictionary[first] or {} if first ~= "$" then insert(dictionary[first], word:sub(2)) end end
Finding all possible words
The first step to my solution is to find all the possible words in the telegram, matched to their place in the string. So, for the telegram “hellothere” we will make a list of words like this:
hellothere he hell hello -ell ---lo ---lot ---loth ----other -----the -----there ------he ------her ------here -------ere --------re
(Your list may be slightly different using the OSPD instead of Ubuntu’s dictionary like I am.)
find_words takes a telegram and a trie and returns a list of {position, word} tuples for each word. The way it works is pretty straightforward: for each letter in the telegram, search the trie for words that start with that letter. So, we look for a “$” node under the first “h,” if we don’t find one we move down to “e” and then look for a “$” node, if we find one we insert “he” and then move down to “l,” and so on, until we reach a point where the current trie node doesn’t have a child for the next letter in the telegram. Then we stop and try again with the next starting letter.
function find_words(telegram, dictionary) local words = {} -- list of tuples, {start, word} for start = 1, #telegram do local current_index = start local current_letter = telegram:sub(start, start) local current_node = dictionary while current_node[ current_letter ] do current_node = current_node[ current_letter ] if current_node['$'] then table.insert(words, {start, telegram:sub(start, current_index)}) end current_index = current_index + 1 current_letter = telegram:sub(current_index, current_index) end end return words end
Culling the word list
Looking at our list of words, it should be clear that some of these can’t be part of any solution. For example, look at the word “lot” starting at position 4: any solution that contains “lot” must also contain a word that ends at position 3, as well as one that begins with position 7 (the left and right neighbors of “lot”). “Here” begins at 7, so we have a right neighbor, but nothing ends at 3, so, “lot” cannot be part of a solution.
We need to go through the list of tuples and remove any words that don’t have left and right neighbors. Of course, those words we remove might themselves be the neighbors of other words, meaning that removing them might leave those words without a neighbor. So we need to keep culling the list until there’s nothing left that can be removed.
We’ll make this fast by keeping a count of all the words that start and end at each position, and checking each word to ensure that that count is positive for each of them.
function cull_words(words, telegram_length) -- Map from start / end position, to word count local by_start = setmetatable( {}, {__index=function() return 0 end} ) local by_end = setmetatable( {}, {__index=function() return 0 end} ) -- Initialize these counts for _, w in ipairs(words) do local l = w[1] local r = w[1] + #(w[2]) - 1 by_start[l] = by_start[l] + 1 by_end[r] = by_end[r] + 1 end -- Loop until we run out of things to remove while true do local new_words = {} for i, w in ipairs(words) do local left = w[1] local right = w[1] + #(w[2]) - 1 local left_neighbor = (left == 1) or (by_end[left-1] > 0) local right_neighbor = (right == telegram_length) or (by_start[right+1] > 0) if left_neighbor and right_neighbor then table.insert(new_words, w) else by_start[left] = by_start[left] - 1 by_end[right] = by_end[right] - 1 end end if #new_words == #words then break end words = new_words end return words end
Enumerating the solutions
At this point, everything in our word list can be part of a solution. We can organize our words into a tree, like so:
iamatelegram i -a -am --ma --mate ---a ---ate ----telegram ------leg ---------ram
Here’s a simple function to do that:
function build_word_tree(words) local function find_by_start(start) local arr = {} for _,w in ipairs(words) do if w[1] == start then table.insert(arr, w[2]) end end return arr end local function tree_for_start(start) local tree = {} for _, w in ipairs(find_by_start(start)) do tree[w] = tree_for_start( start + #w ) end return tree end return tree_for_start(1) end
Now, every path through this tree is a possible solution. So, we simply do a depth-first traversal of the tree and list out all the paths:
function print_tree(word_tree) local strings = {} -- The paths through the tree local function dft(path, current_node) for word, children in pairs(current_node) do local new_path = path and path .. " " .. word or word if not next(children) then table.insert(strings, new_path) else dft(new_path, children) end end end dft(nil, word_tree) for _, s in ipairs(strings) do print(s) end end
Putting it together
Now that we have all the tools, we just run them all together:
function parse_telegram(telegram) local words = find_words(telegram, dictionary) local culled = cull_words(words, #telegram) local tree = build_word_tree(culled) print_tree(tree) end
Let’s test it out:
parse_telegram("turkeytrotstowaterwhereistaskforcethirtyfourtheworldwonders") -- turkey trots to water where is task force thirty four the world wonders
Again, you may get more possible solutions if you use a different dictionary.
Code, next steps
As always, the complete code is on Github. If you want to play with it, try messing around with the print_tree function: look for the path through the tree with the highest average word length (hint: the total word length will always be constant).