{"id":5622,"date":"2019-03-31T13:00:01","date_gmt":"2019-03-31T13:00:01","guid":{"rendered":"http:\/\/writeasync.net\/?p=5622"},"modified":"2019-03-30T18:05:44","modified_gmt":"2019-03-30T18:05:44","slug":"letter-boxed-an-algorithmic-solution","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5622","title":{"rendered":"Letter Boxed: an algorithmic solution"},"content":{"rendered":"

Previously, I introduced the Letter Boxed puzzle<\/a> and a StringTrie<\/code> data structure to help determine valid moves. Today, I will go over one possible algorithm to solve it.<\/p>\n

We first consider the Letter Box as a graph<\/a> with numbered vertices like so:<\/p>\n

\r\n     0 1 2\r\n   - * * * -\r\n11 *       * 3\r\n10 *       * 4\r\n 9 *       * 5\r\n   - * * * -\r\n     8 7 6\r\n<\/pre>\n
There are 12 x 9 = 108 edges in this graph, one for every valid two step movement. For example, the entire set of edges with 0 as the starting vertex would be { (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11) }<\/code> — in other words, all possible combinations excluding vertices on the starting side.<\/p>\n
Now let’s relabel the Letter Box with English letters:<\/p>\n
\r\n     A B C\r\n   - * * * -\r\n L *       * D\r\n K *       * E\r\n J *       * F\r\n   - * * * -\r\n     I H G\r\n<\/pre>\n
Using our StringTrie<\/code>, we start from a given vertex and select the trie node corresponding to it. Let’s say we start with vertex 0 which is letter A. We do a lookup node = trie['A']<\/code> to get the first node. Now from this node, we select a valid adjacent vertex, let’s say 6 \/ ‘G’ and do a lookup node = node['G']<\/code> to go one level deeper. We continue this until we reach a nonexistent node; e.g. if we pick 10 \/ ‘K’, we would end up with a null node since there are no English words with a prefix “AGK.” If at any point the node has a valid value (e.g. “AGE” with vertices 0-6-4), we report this as a found word but otherwise continue the algorithm in the hopes of finding longer matches.<\/p>\n
What I’m describing is classic depth-first search<\/a> which naturally lends itself to a recursive implementation. In pseudocode, it might look like this:<\/p>\n
\r\nprocedure findWords(trie, box, found):\r\n  for all vertices v1 in box do:\r\n    c1 = box[v1]\r\n    visited1 = { v1 }\r\n    nextSearch(trie[c1], box, v1, visited1, found)\r\n\r\nprocedure nextSearch(node, box, v1, visited1, found):\r\n  if node is not null then\r\n    if node has a valid value then call found(node.value, visited1)\r\n    for all vertices v2 in box.adjacent(v1) do:\r\n      c2 = box[v2]\r\n      visited2 = visited1 union with { v2 }\r\n      nextSearch(node[c2], box, v2, visited2, found)\r\n<\/pre>\n
We can be assured the algorithm will terminate eventually because even though the box graph has cycles (“ADADADAD…”), the trie does not. There is, after all, a finite limit on the number of English words up to a certain length. Note that the algorithm uses a visited<\/code> vertex set and reports this to the found<\/code> callback along with the word value; this will become important in the second part of the solution.<\/p>\n
So now we’ve found all the words hidden in the box. Next we must find pairs of these words (w1, w2)<\/code> such that the last letter of w1<\/code> is the first letter of w2<\/code> and<\/em> which together contain all letters in the box at least once (aka a set cover<\/a> over the Letter Box). In pseudocode:<\/p>\n
\r\nprocedure findSolutions(allWords, found):\r\n  for all words w1 in allWords do:\r\n    for all words w2 in allWords.startingWith(w1.last) do:\r\n      visited = w1.visited union with w2.visited\r\n      if visited is complete set then call found(w1, w2)\r\n<\/pre>\n
Now that we have a basic sketch of the solution, we can start implementing the pieces necessary to build it. First, the LetterBox<\/code>, which is just a thin wrapper around a string. It also needs to provide a Vertices<\/code> set, implemented here as a bit field<\/a>; the user can query for valid next Vertices given a starting vertex, and also combine two sets. Our implementation so far: LetterBox.cs<\/a><\/p>\n
Next, we need the word search algorithm. A new LetterBoxSearch<\/code> class will do nicely, with inputs for the trie and letter box. A user-specified Action<string, LetterBox.Vertices><\/code> will represent the found callback. Here is where we are now: LetterBoxSearch.cs<\/a><\/p>\n
Finally, we need a structure to collect words and implement the two-word solution search logic. We will call it LetterBoxWords<\/code>. Internally it will have a dictionary which maps initial letters to hash sets of matching words with their vertex sets. After those changes (plus a new property IsComplete<\/code> for LetterBox.Vertices<\/code>) we have: LetterBoxWords.cs<\/a><\/p>\n
All that’s left is to write a solver application. It will just need a letter box string and a word list file as inputs. The OSPD4<\/a> word list should suffice; I found a copy here<\/a> which I processed by stripping the definitions and sorting the words: words.txt<\/a><\/p>\n
The app sets up the letter box, reads the word list, loads each entry into the trie, and constructs the LetterBoxSearch<\/code> and LetterBoxWords<\/code> instances. The search callback adds words to the collection and the find solution callback prints out each two-word solution. Et voil\u00e0: Solver.cs<\/a><\/p>\n
Now we just need to compile it in Release mode and see it in action. Let’s solve the March 28, 2019 Letter Boxed puzzle:<\/p>\n
\r\n> LetterBoxedSolver.exe RMEWCLTGKAPI words.txt\r\n[000.000] Loading trie...\r\n[000.211] Loaded 162309 words.\r\n[000.212] Finding valid words...\r\n[000.219] Found 754 valid words.\r\n[000.219] Finding solutions...\r\nMARKETPLACE-EARWIG\r\nWIGWAM-MARKETPLACE\r\nPRAGMATIC-CAKEWALK\r\n[000.226] Done.\r\n<\/pre>\n
Amazing! In less than 1\/4 of a second, we have a list of valid solutions. The vast majority of the time is spent loading the trie — the search algorithms themselves only take about 7 ms each.<\/p>\n
As fast as this is, we can probably do better. We’ll explore performance optimization next time.<\/p>\n","protected":false},"excerpt":{"rendered":"
Previously, I introduced the Letter Boxed puzzle and a StringTrie data structure to help determine valid moves. Today, I will go over one possible algorithm to solve it. We first consider the Letter Box as a graph with numbered vertices… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[105],"tags":[],"class_list":["post-5622","post","type-post","status-publish","format-standard","hentry","category-games"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5622","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5622"}],"version-history":[{"count":1,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5622\/revisions"}],"predecessor-version":[{"id":5623,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5622\/revisions\/5623"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5622"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5622"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5622"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}