{"id":60,"date":"2015-05-09T01:24:06","date_gmt":"2015-05-09T06:24:06","guid":{"rendered":"http:\/\/www.playwithlua.com\/?p=60"},"modified":"2020-05-22T13:51:00","modified_gmt":"2020-05-22T18:51:00","slug":"telegrams","status":"publish","type":"post","link":"http:\/\/www.playwithlua.com\/?p=60","title":{"rendered":"Telegrams"},"content":{"rendered":"

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<\/a>:<\/p>\n\n

parse_telegram(<\/span>"turkeytrotstowaterwhereistaskforcethirtyfourtheworldwonders"<\/span>)<\/span>\n-- turkey trots to water where is task force thirty four the world wonders<\/span><\/pre><\/div><\/div><\/div>\n\n
I wrote a solution last night.<\/p>\n
<\/p>\n
The dictionary<\/h2>\n
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<\/code>. If not, I recommend Googling for the OSPD, the Official Scrabble Player’s Dictionary.<\/p>\n
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).<\/p>\n
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:”<\/p>\n\n
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).<\/p>\n
So, here’s a function that reads a dictionary file, filters out the words we don’t want, and inserts them into a trie:<\/p>\n\n
function<\/span> load_dictionary(<\/span>filename)<\/span>\n    local<\/span> dictionary =<\/span> {<\/span>}<\/span>\n \n    for<\/span> line in<\/span> io.lines<\/span>(<\/span>filename)<\/span> do<\/span>\n        if<\/span> line:<\/span>match(<\/span>"^%l%l+$"<\/span>)<\/span> then<\/span>\n            insert(<\/span>dictionary,<\/span> line ..<\/span> "$"<\/span>)<\/span>\n        end<\/span>\n    end<\/span>\n \n    -- We're cutting all single-letter words, but<\/span>\n    -- two of them are real words<\/span>\n    insert(<\/span>dictionary,<\/span> "a$"<\/span>)<\/span>\n    insert(<\/span>dictionary,<\/span> "i$"<\/span>)<\/span>\n \n    return<\/span> dictionary\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
And here’s the corresponding insert<\/code> function, to actually put them in the trie:<\/p>\n\n
function<\/span> insert(<\/span>dictionary,<\/span> word)<\/span>\n    local<\/span> first =<\/span> word:<\/span>sub(<\/span>1<\/span>,<\/span>1<\/span>)<\/span>\n    dictionary[<\/span>first]<\/span> =<\/span> dictionary[<\/span>first]<\/span> or<\/span> {<\/span>}<\/span>\n    if<\/span> first ~=<\/span> "$"<\/span> then<\/span>\n        insert(<\/span>dictionary[<\/span>first]<\/span>,<\/span> word:<\/span>sub(<\/span>2<\/span>)<\/span>)<\/span>\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Finding all possible words<\/h2>\n
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:<\/p>\n
\r\nhellothere\r\nhe\r\nhell\r\nhello\r\n-ell\r\n---lo\r\n---lot\r\n---loth\r\n----other\r\n-----the\r\n-----there\r\n------he\r\n------her\r\n------here\r\n-------ere\r\n--------re\r\n<\/pre>\n
(Your list may be slightly different using the OSPD instead of Ubuntu’s dictionary like I am.)<\/p>\n
find_words<\/code> takes a telegram and a trie and returns a list of {position, word}<\/code> 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.<\/p>\n\n
function<\/span> find_words(<\/span>telegram,<\/span> dictionary)<\/span>\n    local<\/span> words =<\/span> {<\/span>}<\/span> -- list of tuples, {start, word}<\/span>\n \n    for<\/span> start =<\/span> 1<\/span>,<\/span> #<\/span>telegram do<\/span>\n        local<\/span> current_index =<\/span> start\n        local<\/span> current_letter =<\/span> telegram:<\/span>sub(<\/span>start,<\/span> start)<\/span>\n        local<\/span> current_node =<\/span> dictionary\n \n        while<\/span> current_node[<\/span> current_letter ]<\/span> do<\/span>\n            current_node =<\/span> current_node[<\/span> current_letter ]<\/span>\n            if<\/span> current_node[<\/span>'$'<\/span>]<\/span> then<\/span>\n                table.insert<\/span>(<\/span>words,<\/span> {<\/span>start,<\/span> telegram:<\/span>sub(<\/span>start,<\/span> current_index)<\/span>}<\/span>)<\/span>\n            end<\/span>\n \n            current_index =<\/span> current_index +<\/span> 1<\/span>\n            current_letter =<\/span> telegram:<\/span>sub(<\/span>current_index,<\/span> current_index)<\/span>\n        end<\/span>\n    end<\/span>\n \n    return<\/span> words\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Culling the word list<\/h2>\n
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.<\/p>\n
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<\/em> words without a neighbor. So we need to keep culling the list until there’s nothing left that can be removed.<\/p>\n
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.<\/p>\n\n
function<\/span> cull_words(<\/span>words,<\/span> telegram_length)<\/span>\n    -- Map from start \/ end position, to word count<\/span>\n    local<\/span> by_start =<\/span> setmetatable<\/span>(<\/span> {<\/span>}<\/span>,<\/span> {<\/span>__index=<\/span>function<\/span>(<\/span>)<\/span> return<\/span> 0<\/span> end<\/span>}<\/span> )<\/span>\n    local<\/span> by_end =<\/span> setmetatable<\/span>(<\/span> {<\/span>}<\/span>,<\/span> {<\/span>__index=<\/span>function<\/span>(<\/span>)<\/span> return<\/span> 0<\/span> end<\/span>}<\/span> )<\/span>\n \n    -- Initialize these counts<\/span>\n    for<\/span> _,<\/span> w in<\/span> ipairs<\/span>(<\/span>words)<\/span> do<\/span>\n        local<\/span> l =<\/span> w[<\/span>1<\/span>]<\/span>\n        local<\/span> r =<\/span> w[<\/span>1<\/span>]<\/span> +<\/span> #<\/span>(<\/span>w[<\/span>2<\/span>]<\/span>)<\/span> -<\/span> 1<\/span>\n \n        by_start[<\/span>l]<\/span> =<\/span> by_start[<\/span>l]<\/span> +<\/span> 1<\/span>\n        by_end[<\/span>r]<\/span> =<\/span> by_end[<\/span>r]<\/span> +<\/span> 1<\/span>\n    end<\/span>\n \n    -- Loop until we run out of things to remove<\/span>\n    while<\/span> true<\/span> do<\/span>\n        local<\/span> new_words =<\/span> {<\/span>}<\/span>\n \n        for<\/span> i,<\/span> w in<\/span> ipairs<\/span>(<\/span>words)<\/span> do<\/span>\n            local<\/span> left =<\/span> w[<\/span>1<\/span>]<\/span>\n            local<\/span> right =<\/span> w[<\/span>1<\/span>]<\/span> +<\/span> #<\/span>(<\/span>w[<\/span>2<\/span>]<\/span>)<\/span> -<\/span> 1<\/span>\n \n            local<\/span> left_neighbor =<\/span> (<\/span>left ==<\/span> 1<\/span>)<\/span> or<\/span> (<\/span>by_end[<\/span>left-<\/span>1<\/span>]<\/span> ><\/span> 0<\/span>)<\/span>\n            local<\/span> right_neighbor =<\/span> (<\/span>right ==<\/span> telegram_length)<\/span> or<\/span> (<\/span>by_start[<\/span>right+<\/span>1<\/span>]<\/span> ><\/span> 0<\/span>)<\/span>\n \n            if<\/span> left_neighbor and<\/span> right_neighbor then<\/span>\n                table.insert<\/span>(<\/span>new_words,<\/span> w)<\/span>\n            else<\/span>\n                by_start[<\/span>left]<\/span> =<\/span> by_start[<\/span>left]<\/span> -<\/span> 1<\/span>\n                by_end[<\/span>right]<\/span> =<\/span> by_end[<\/span>right]<\/span> -<\/span> 1<\/span>\n            end<\/span>\n        end<\/span>\n \n        if<\/span> #<\/span>new_words ==<\/span> #<\/span>words then<\/span> break<\/span> end<\/span>\n        words =<\/span> new_words\n    end<\/span>\n \n    return<\/span> words\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Enumerating the solutions<\/h2>\n
At this point, everything in our word list can be part of a solution. We can organize our words into a tree, like so:<\/p>\n
\r\niamatelegram\r\ni\r\n-a\r\n-am\r\n--ma\r\n--mate\r\n---a\r\n---ate\r\n----telegram\r\n------leg\r\n---------ram\r\n<\/pre>\n\n
Here’s a simple function to do that:<\/p>\n\n
function<\/span> build_word_tree(<\/span>words)<\/span>\n    local<\/span> function<\/span> find_by_start(<\/span>start)<\/span>\n        local<\/span> arr =<\/span> {<\/span>}<\/span>\n        for<\/span> _,<\/span>w in<\/span> ipairs<\/span>(<\/span>words)<\/span> do<\/span>\n            if<\/span> w[<\/span>1<\/span>]<\/span> ==<\/span> start then<\/span> table.insert<\/span>(<\/span>arr,<\/span> w[<\/span>2<\/span>]<\/span>)<\/span> end<\/span>\n        end<\/span>\n        return<\/span> arr\n    end<\/span>\n \n    local<\/span> function<\/span> tree_for_start(<\/span>start)<\/span>\n        local<\/span> tree =<\/span> {<\/span>}<\/span>\n        for<\/span> _,<\/span> w in<\/span> ipairs<\/span>(<\/span>find_by_start(<\/span>start)<\/span>)<\/span> do<\/span>\n            tree[<\/span>w]<\/span> =<\/span> tree_for_start(<\/span> start +<\/span> #<\/span>w )<\/span>\n        end<\/span>\n        return<\/span> tree\n    end<\/span>\n \n    return<\/span> tree_for_start(<\/span>1<\/span>)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
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:<\/p>\n\n
function<\/span> print_tree(<\/span>word_tree)<\/span>\n    local<\/span> strings =<\/span> {<\/span>}<\/span> -- The paths through the tree<\/span>\n \n    local<\/span> function<\/span> dft(<\/span>path,<\/span> current_node)<\/span>\n        for<\/span> word,<\/span> children in<\/span> pairs<\/span>(<\/span>current_node)<\/span> do<\/span>\n            local<\/span> new_path =<\/span> path and<\/span> path ..<\/span> " "<\/span> ..<\/span> word or<\/span> word\n \n            if<\/span> not<\/span> next<\/span>(<\/span>children)<\/span> then<\/span>\n                table.insert<\/span>(<\/span>strings,<\/span> new_path)<\/span>\n            else<\/span>\n                dft(<\/span>new_path,<\/span> children)<\/span>\n            end<\/span>\n        end<\/span>\n    end<\/span>\n \n    dft(<\/span>nil<\/span>,<\/span> word_tree)<\/span>\n \n    for<\/span> _,<\/span> s in<\/span> ipairs<\/span>(<\/span>strings)<\/span> do<\/span>\n        print<\/span>(<\/span>s)<\/span>\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Putting it together<\/h2>\n
Now that we have all the tools, we just run them all together:<\/p>\n\n
function<\/span> parse_telegram(<\/span>telegram)<\/span>\n    local<\/span> words =<\/span> find_words(<\/span>telegram,<\/span> dictionary)<\/span>\n    local<\/span> culled =<\/span> cull_words(<\/span>words,<\/span> #<\/span>telegram)<\/span>\n    local<\/span> tree =<\/span> build_word_tree(<\/span>culled)<\/span>\n \n    print_tree(<\/span>tree)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Let’s test it out:<\/p>\n\n
parse_telegram(<\/span>"turkeytrotstowaterwhereistaskforcethirtyfourtheworldwonders"<\/span>)<\/span>\n-- turkey trots to water where is task force thirty four the world wonders<\/span><\/pre><\/div><\/div><\/div>\n\n
Again, you may get more possible solutions if you use a different dictionary.<\/p>\n
Code, next steps<\/h2>\n
As always, the complete code is on Github<\/a>. If you want to play with it, try messing around with the print_tree<\/code> function: look for the path through the tree with the highest average word length (hint: the total word length will always be constant).<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts\/60"}],"collection":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=60"}],"version-history":[{"count":0,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts\/60\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=60"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=60"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=60"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}