{"id":45,"date":"2013-05-20T19:32:02","date_gmt":"2013-05-21T02:32:02","guid":{"rendered":"https:\/\/www.alexkorn.com\/blog\/?p=45"},"modified":"2013-05-21T12:53:48","modified_gmt":"2013-05-21T19:53:48","slug":"graph-search-algorithmic-optimization-and-word-games-how-to-program-ruzzle","status":"publish","type":"post","link":"https:\/\/www.alexkorn.com\/blog\/2013\/05\/graph-search-algorithmic-optimization-and-word-games-how-to-program-ruzzle\/","title":{"rendered":"Graph search, algorithmic optimization, and word games: How to program Ruzzle"},"content":{"rendered":"

(Disclaimer: I have no affiliation with Ruzzle.)<\/i><\/p>\n

Introduction<\/h3>\n

\nI was recently introduced to the game Ruzzle<\/a>, a word finding game with some Scrabble-like scoring components. If you’re not familiar with it, check out their website and watch the quick introductory video.\n<\/p>\n

\"Ruzzle<\/a>

Ruzzle screenshot<\/p><\/div>\n

\nI was fascinated by how the game calculated all the possible words on each board. So I decided to program it. Check out the Ruzzle demo page<\/a>, which creates a randomized board and finds all possible words.\n<\/p>\n

Overview<\/h3>\n

\nThe way to do this search for all possible words is by viewing the letters as a directed graph<\/a> where the letters are nodes and edges are connections between adjacent letters.\n<\/p>\n

\"Ruzzle<\/a>

Ruzzle graph. This was more of a pain to make than you might expect.<\/p><\/div>\n

\nWith this graph, we can do a Depth-first search (DFS)<\/a> for words starting at each node.\n<\/p>\n

Creating the board<\/h3>\n

First, we need to create a 4×4 board of letters. In order to create reasonable boards for English, we weight the letter distribution to that of their distribution in English<\/a>.<\/p>\n

\nThe following code creates the graph\/board, assigns letters to each node\/tile, and outputs the board. The basic graph objects are shown at the end of this post.\n<\/p>\n

\r\n\/**\r\n * Create graph\/board\r\n *\/\r\n\r\n$timeStart = microtime(true);\r\n\r\n$colCount = 4;\r\n$rowCount = 4;\r\n\r\n$lettersGraph = new Graph_Directed();\r\n\/**\r\n * @var array Map>\r\n *\/\r\n$lettersGraphNode = [];\r\nfor ($colIter = 0; $colIter < $colCount; ++$colIter)\r\n{\r\n    for ($rowIter = 0; $rowIter < $rowCount; ++$rowIter)\r\n    {\r\n        $node = $lettersGraphNode[$colIter][$rowIter] = new Graph_Node($lettersGraph);\r\n    }\r\n}\r\n\r\n\/**\r\n * Attach each node to all adjacent nodes\r\n *\/\r\nfor ($colIter = 0; $colIter < $colCount; ++$colIter)\r\n{\r\n    for ($rowIter = 0; $rowIter < $rowCount; ++$rowIter)\r\n    {\r\n        $node = $lettersGraphNode[$colIter][$rowIter];\r\n        for ($adjacentColIter = max(0, $colIter - 1);\r\n            $adjacentColIter < min($colCount, $colIter + 1 + 1);\r\n            ++$adjacentColIter)\r\n        {\r\n            for ($adjacentRowIter = max(0, $rowIter - 1);\r\n                $adjacentRowIter < min($rowCount, $rowIter + 1 + 1);\r\n                ++$adjacentRowIter)\r\n            {\r\n                \/\/ don't connect letters to themselves\r\n                if ($colIter == $adjacentColIter &&\r\n                        $rowIter == $adjacentRowIter)\r\n                {\r\n                    continue;\r\n                }\r\n                $node->connectFlowFrom(\r\n                        $lettersGraphNode[$adjacentColIter][$adjacentRowIter]);\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\n\/**\r\n * @see http:\/\/en.wikipedia.org\/wiki\/Letter_frequency#Relative_frequencies_of_letters_in_the_English_language\r\n *\/\r\n$letterFrequency = [\r\n    'A' => 0.08167,\r\n    'B' => 0.01492,\r\n    'C' => 0.02782,\r\n    'D' => 0.04253,\r\n    'E' => 0.12702,\r\n    'F' => 0.02228,\r\n    'G' => 0.02015,\r\n    'H' => 0.06094,\r\n    'I' => 0.06966,\r\n    'J' => 0.00153,\r\n    'K' => 0.00772,\r\n    'L' => 0.04025,\r\n    'M' => 0.02406,\r\n    'N' => 0.06749,\r\n    'O' => 0.07507,\r\n    'P' => 0.01929,\r\n    'Q' => 0.00095,\r\n    'R' => 0.05987,\r\n    'S' => 0.06327,\r\n    'T' => 0.09056,\r\n    'U' => 0.02758,\r\n    'V' => 0.00978,\r\n    'W' => 0.02360,\r\n    'X' => 0.00150,\r\n    'Y' => 0.01974,\r\n    'Z' => 0.00074 + 0.00001, \/\/ there's some rounding in Wikipedia's list\r\n];\r\n$letterToMaxCumulativeFrequency = [];\r\n$cumulativeFrequency = 0;\r\nforeach ($letterFrequency as $letter => $frequency)\r\n{\r\n    $cumulativeFrequency += $frequency;\r\n    $letterToMaxCumulativeFrequency[$letter] = $cumulativeFrequency;\r\n}\r\n\r\nforeach ($lettersGraph->getNodes() as $node)\r\n{\r\n    $val = mt_rand(0, mt_getrandmax()) \/ mt_getrandmax();\r\n    foreach ($letterToMaxCumulativeFrequency as $letter => $maxFrequency)\r\n    {\r\n        if ($val < $maxFrequency)\r\n        {\r\n            $node->letter = $letter;\r\n            break;\r\n        }\r\n    }\r\n}\r\n\r\n\/**\r\n * @param array $lettersGraphNode\r\n * @return string\/HC\r\n *\/\r\nfunction printTileLetters(array $lettersGraphNode)\r\n{\r\n    $result = '';\r\n    foreach ($lettersGraphNode as $colData)\r\n    {\r\n        $result .= '';\r\n        foreach ($colData as $rowData)\r\n        {\r\n            $result .= '
' . $rowData->letter . '<\/td>';\r\n        }\r\n        $result .= '<\/tr>';\r\n    }\r\n    $result .= '<\/tbody><\/table>';\r\n    return $result;\r\n}\r\n\r\necho printTileLetters($lettersGraphNode);\r\n<\/pre>\n
Graph search, algorithmic complexity, and optimization<\/h3>\n
\nFirst, we need to load and parse the dictionary. I’ve found this dictionary<\/a> works well.\n<\/p>\n
\r\n\/**\r\n * Load\/parse dictionary\r\n *\/\r\n\r\n$dictionaryList = file(dirname(dirname(__FILE__)) . '\/data\/dictionary.txt');\r\n$dictionaryMap = [];\r\nforeach ($dictionaryList as $word)\r\n{\r\n    $dictionaryMap[strtoupper(trim($word))] = true;\r\n}\r\n\r\n\/**\r\n * Set up first letters array, which helps us optimize the otherwise-slow\r\n * DFS for words.\r\n *\/\r\n\r\n$dictionaryFirstNLetters = [];\r\ndefine('MIN_FIRST_LETTERS_LENGTH', 4);\r\ndefine('MAX_FIRST_LETTERS_LENGTH', 10);\r\n\r\nforeach ($dictionaryList as $word)\r\n{\r\n    $word = strtoupper(trim($word));\r\n    for ($length = MIN_FIRST_LETTERS_LENGTH; $length < MAX_FIRST_LETTERS_LENGTH; ++$length)\r\n    {\r\n        $firstNLetters = substr($word, 0, $length);\r\n        if ($firstNLetters != $word)\r\n        {\r\n            $dictionaryFirstNLetters[$firstNLetters] = true;\r\n        }\r\n        else\r\n        {\r\n            break;\r\n        }\r\n    }\r\n}\r\n\r\necho \"Dictionary loaded\/parsed in \" . number_format(microtime(true) - $timeStart, 3) . \"s

\\n\";\r\n<\/pre>\n
\nNote the variable $dictionaryFirstNLetters<\/code>. We use this to optimize our DFS by allowing us to “bail out” early in our search if we see that there are no words that start with our $currentResult<\/code>. If you try taking out this code, you’ll see that this algorithm can take an incredibly long time to run – even with a $maxDepth<\/code> of 6 characters (only find words with up to 6 characters), the runtime can easily reach a minute. It increases quickly as $maxDepth<\/code> is increased.\n<\/p>\n
\nBelow is our optimized depth-first search.\n<\/p>\n
\r\n\/**\r\n * @param Zeal_Graph_Node $source\r\n * @param int $maxDepth\r\n * @param array $dictionaryMap\r\n * @param array $dictionaryFirstNLetters\r\n * @param array $previouslyVisitedNodeIds\r\n * @param string $currentResult\r\n * @param array $results (By reference)\r\n * @return array\r\n *\/\r\nfunction depthFirstSearch(Zeal_Graph_Node $source, $maxDepth,\r\n        array $dictionaryMap, array $dictionaryFirstNLetters,\r\n        $previouslyVisitedNodeIds = [], $currentResult = '', array &$results = [])\r\n{\r\n    if (strlen($currentResult) >= $maxDepth)\r\n    {\r\n        return [];\r\n    }\r\n    $currentResult .= $source->letter;\r\n    if (isset($dictionaryMap[$currentResult]))\r\n    {\r\n        $results[] = $currentResult;\r\n    }\r\n    \/\/ bail out if there are no words that start with these letters\r\n    if (strlen($currentResult) >= MIN_FIRST_LETTERS_LENGTH &&\r\n        strlen($currentResult) <= MAX_FIRST_LETTERS_LENGTH &&\r\n            !isset($dictionaryFirstNLetters[$currentResult]))\r\n    {\r\n        return [];\r\n    }\r\n    $previouslyVisitedNodeIds[] = $source->id();\r\n    foreach ($source->outgoingEdges as $edge)\r\n    {\r\n        $destination = $edge->getNodeTo();\r\n        \/\/ can't repeat letters\r\n        if (in_array($destination->id(), $previouslyVisitedNodeIds))\r\n        {\r\n            continue;\r\n        }\r\n        $results += depthFirstSearch($destination, $maxDepth,\r\n                $dictionaryMap, $dictionaryFirstNLetters, $previouslyVisitedNodeIds, $currentResult, $results);\r\n    }\r\n    return $results;\r\n}\r\n\r\n\/**\r\n * Iterate over each tile and find all words starting with that letter\r\n *\/\r\n$results = [];\r\nfor ($colIter = 0; $colIter < $colCount; ++$colIter)\r\n{\r\n    for ($rowIter = 0; $rowIter < $rowCount; ++$rowIter)\r\n    {\r\n        $results = array_merge(\r\n            $results,\r\n            depthFirstSearch(\r\n                $lettersGraphNode[$colIter][$rowIter], $colCount * $rowCount,\r\n                $dictionaryMap, $dictionaryFirstNLetters)\r\n        );\r\n    }\r\n}\r\n\r\necho \"
Stats\\n