StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My answer works like the others here, but I'll post it because it looks a bit faster than the other Python solutions, from setting up the dictionary faster. (I checked this against John Fouhy's solution.) After setup, the time to solve is down in the noise.</p> <pre class="lang-python prettyprint-override"><code>grid = "fxie amlo ewbx astu".split() nrows, ncols = len(grid), len(grid[0]) # A dictionary word that could be a solution must use only the grid's # letters and have length >= 3. (With a case-insensitive match.) import re alphabet = ''.join(set(''.join(grid))) bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).match words = set(word.rstrip('\n') for word in open('words') if bogglable(word)) prefixes = set(word[:i] for word in words for i in range(2, len(word)+1)) def solve(): for y, row in enumerate(grid): for x, letter in enumerate(row): for result in extending(letter, ((x, y),)): yield result def extending(prefix, path): if prefix in words: yield (prefix, path) for (nx, ny) in neighbors(path[-1]): if (nx, ny) not in path: prefix1 = prefix + grid[ny][nx] if prefix1 in prefixes: for result in extending(prefix1, path + ((nx, ny),)): yield result def neighbors((x, y)): for nx in range(max(0, x-1), min(x+2, ncols)): for ny in range(max(0, y-1), min(y+2, nrows)): yield (nx, ny) </code></pre> <p>Sample usage:</p> <pre><code># Print a maximal-length word and its path: print max(solve(), key=lambda (word, path): len(word)) </code></pre> <p><strong>Edit:</strong> Filter out words less than 3 letters long.</p> <p><strong>Edit 2:</strong> I was curious why Kent Fredric's Perl solution was faster; it turns out to use regular-expression matching instead of a set of characters. Doing the same in Python about doubles the speed.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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