Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The fastest solution you're going to get will probably involve storing your dictionary in a <a href="http://en.wikipedia.org/wiki/Trie" rel="noreferrer">trie</a>. Then, create a queue of triplets (<em>x</em>, <em>y</em>, <em>s</em>), where each element in the queue corresponds to a prefix <em>s</em> of a word which can be spelled in the grid, ending at location (<em>x</em>, <em>y</em>). Initialize the queue with <em>N</em> x <em>N</em> elements (where <em>N</em> is the size of your grid), one element for each square in the grid. Then, the algorithm proceeds as follows:</p> <pre> While the queue is not empty: Dequeue a triple (x, y, s) For each square (x', y') with letter c adjacent to (x, y): If s+c is a word, output s+c If s+c is a prefix of a word, insert (x', y', s+c) into the queue </pre> <p>If you store your dictionary in a trie, testing if <em>s</em>+<em>c</em> is a word or a prefix of a word can be done in constant time (provided you also keep some extra metadata in each queue datum, such as a pointer to the current node in the trie), so the running time of this algorithm is O(number of words that can be spelled).</p> <p><strong>[Edit]</strong> Here's an implementation in Python that I just coded up:</p> <pre><code>#!/usr/bin/python class TrieNode: def __init__(self, parent, value): self.parent = parent self.children = [None] * 26 self.isWord = False if parent is not None: parent.children[ord(value) - 97] = self def MakeTrie(dictfile): dict = open(dictfile) root = TrieNode(None, '') for word in dict: curNode = root for letter in word.lower(): if 97 &lt;= ord(letter) &lt; 123: nextNode = curNode.children[ord(letter) - 97] if nextNode is None: nextNode = TrieNode(curNode, letter) curNode = nextNode curNode.isWord = True return root def BoggleWords(grid, dict): rows = len(grid) cols = len(grid[0]) queue = [] words = [] for y in range(cols): for x in range(rows): c = grid[y][x] node = dict.children[ord(c) - 97] if node is not None: queue.append((x, y, c, node)) while queue: x, y, s, node = queue[0] del queue[0] for dx, dy in ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)): x2, y2 = x + dx, y + dy if 0 &lt;= x2 &lt; cols and 0 &lt;= y2 &lt; rows: s2 = s + grid[y2][x2] node2 = node.children[ord(grid[y2][x2]) - 97] if node2 is not None: if node2.isWord: words.append(s2) queue.append((x2, y2, s2, node2)) return words </code></pre> <p>Example usage:</p> <pre><code>d = MakeTrie('/usr/share/dict/words') print(BoggleWords(['fxie','amlo','ewbx','astu'], d)) </code></pre> <p>Output:</p> <blockquote> <p>['fa', 'xi', 'ie', 'io', 'el', 'am', 'ax', 'ae', 'aw', 'mi', 'ma', 'me', 'lo', 'li', 'oe', 'ox', 'em', 'ea', 'ea', 'es', 'wa', 'we', 'wa', 'bo', 'bu', 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'eli', 'elm', 'elb', 'ami', 'ama', 'ame', 'aes', 'awl', 'awa', 'awe', 'awa', 'mix', 'mim', 'mil', 'mam', 'max', 'mae', 'maw', 'mew', 'mem', 'mes', 'lob', 'lox', 'lei', 'leo', 'lie', 'lim', 'oil', 'olm', 'ewe', 'eme', 'wax', 'waf', 'wae', 'waw', 'wem', 'wea', 'wea', 'was', 'waw', 'wae', 'bob', 'blo', 'bub', 'but', 'ast', 'ase', 'asa', 'awl', 'awa', 'awe', 'awa', 'aes', 'swa', 'swa', 'sew', 'sea', 'sea', 'saw', 'tux', 'tub', 'tut', 'twa', 'twa', 'tst', 'utu', 'fama', 'fame', 'ixil', 'imam', 'amli', 'amil', 'ambo', 'axil', 'axle', 'mimi', 'mima', 'mime', 'milo', 'mile', 'mewl', 'mese', 'mesa', 'lolo', 'lobo', 'lima', 'lime', 'limb', 'lile', 'oime', 'oleo', 'olio', 'oboe', 'obol', 'emim', 'emil', 'east', 'ease', 'wame', 'wawa', 'wawa', 'weam', 'west', 'wese', 'wast', 'wase', 'wawa', 'wawa', 'boil', 'bolo', 'bole', 'bobo', 'blob', 'bleo', 'bubo', 'asem', 'stub', 'stut', 'swam', 'semi', 'seme', 'seam', 'seax', 'sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', 'twae', 'ilima', 'amble', 'axile', 'awest', 'mamie', 'mambo', 'maxim', 'mease', 'mesem', 'limax', 'limes', 'limbo', 'limbu', 'obole', 'emesa', 'embox', 'awest', 'swami', 'famble', 'mimble', 'maxima', 'embolo', 'embole', 'wamble', 'semese', 'semble', 'sawbwa', 'sawbwa']</p> </blockquote> <p>Notes: This program doesn't output 1-letter words, or filter by word length at all. That's easy to add but not really relevant to the problem. It also outputs some words multiple times if they can be spelled in multiple ways. If a given word can be spelled in many different ways (worst case: every letter in the grid is the same (e.g. 'A') and a word like 'aaaaaaaaaa' is in your dictionary), then the running time will get horribly exponential. Filtering out duplicates and sorting is trivial to due after the algorithm has finished.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAdam Rosenfield
    1. USAdam Rosenfield
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONice. I also implemented a Boggle solver using tries.
      singulars
      1. PO
      1. USFogleBird
    2. COOoo. I'm glad someone stepped up to the plate. Although this works, it doesn't "remember" the letter it has already used, and comes up with words that would require using the same letter twice which is not allowed. As I'm an idiot, how would I go about fixing that?
      singulars
      1. PO
      1. USPaolo Bergantino
    3. COTrue, it doesn't remember what letters have been visited, but that wasn't specified in your spec =). To fix that, you'd have to add to each queue datum a list of all the visited locations, and then check that list before adding the next character.
      singulars
      1. PO
      1. USAdam Rosenfield
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload