Trie
function Trie(dictionary) { var trie = {}; function insert(word, trie) { var word_length = word.length; if (word_length) { var next = trie; for (var i = 0; i < word_length; i++) { var char = word[i]; if (char in next) { next = next[char]; } else { var child = {}; next[char] = child; next = child; } } next['|'] = null; } } for (var i = 0, length = dictionary.length; i < length; i++) { insert(dictionary[i], trie); } // returns true for a word, null for a segment and false otherwise this.test = function(str) { var next = trie; for (var i = 0, str_length = str.length; i < str_length; i++) { var char = str[i]; if (char in next) { next = next[char]; } else { return null; } } return '|' in next; }; }
Boggle Search
// main workhorse, depth first function start_search(start_x, start_y, length_x, length_y, segment, trie, board, visited, results) { var min_y = Math.max(0, start_y - 1), min_x = Math.max(0, start_x - 1), max_y = Math.min(length_y - 1, start_y + 1), max_x = Math.min(length_x - 1, start_x + 1); for (var y = min_y; y <= max_y; y++) { var visited_y = visited[y], board_y = board[y]; for (var x = min_x; x <= max_x; x++) { if (!visited_y[x]) { var segment_new = segment + board_y[x], test = trie.test(segment_new); if (test === true) { results[segment_new] = true; } if (test !== null) { visited_y[x] = true; start_search(x, y, length_x, length_y, segment_new, trie, board, visited, results); visited_y[x] = false; } } } } } function search(trie, board) { var length_y = board.length, length_x = board[0].length; var visited = []; for (var y = 0; y < length_y; y++) { visited[y] = []; for (var x = 0; x < length_x; x++) { visited[y][x] = false; } } var results = {}; for (var y = 0; y < length_y; y++) { var visited_y = visited[y], board_y = board[y]; for (var x = 0; x < length_x; x++) { visited_y[x] = true; start_search(x, y, length_x, length_y, board_y[x], trie, board, visited, results); visited_y[x] = false; } } var result_array = []; for (var word in results) { if (results.hasOwnProperty(word)) { result_array.push(word); } } result_array.sort(); return result_array; }
Example Execution
function solve_boggle(dictionary) { var board = [ ["d", "g", "f", "k"], ["o", "z", "a", "c"], ["b", "w", "k", "e"], ["b", "w", "k", "e"] ], trie = new Trie(dictionary), results = search(trie, board); $(".results").text(results.join(", ")); } if (window.localStorage !== null && window.localStorage.dictionary) { solve_boggle(window.localStorage.dictionary.split(","), callback); } else { function dictionary_load(data) { if (window.localStorage !== null) { window.localStorage.dictionary = data.join(","); } solve_boggle(data, callback); } $.getScript("http://goo.gl/8EhgZ"); }