Databases
StackOverflow2013
Postsdbo
POEfficient hunting for words in scrambled letters
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient hunting for words in scrambled letters
    primarykey
    data
    text
    <p>I guess you could classify this as a Scrabble style problem, but it started out due to a friend mentioning the UK TV quiz show Countdown. Various rounds in the show involve the contestants being presented a scrambled set of letters and they have to come up with the longest word they can. The one my friend mentioned was "RAEPKWAEN".</p> <p>In fairly short order I whipped up something in Python to handle this problem, using PyEnchant to handle the dictionary look-ups, however I'm noticing that it really can't scale all that well.</p> <p>Here's what I have currently:</p> <pre><code>#!/usr/bin/python from itertools import permutations import enchant from sys import argv def find_longest(origin): s = enchant.Dict("en_US") for i in range(len(origin),0,-1): print "Checking against words of length %d" % i pool = permutations(origin,i) for comb in pool: word = ''.join(comb) if s.check(word): return word return "" if (__name__)== '__main__': result = find_longest(argv[1]) print result </code></pre> <p>That's fine on a 9 letter example like they use in the show, 9 factorial = 362,880 and 8 factorial = 40,320. On that scale even if it would have to check all possible permutations and word lengths it's not that many.</p> <p>However once you reach 14 characters that's 87,178,291,200 possibly combinations, meaning you're reliant on luck that a 14 character word is quickly found.</p> <p>With the example word above it's taking my machine about 12 1/2 seconds to find "reawaken". With 14 character scrambled words we could be talking on the scale of 23 days just to check all possible 14 character permutations.</p> <p>Is there any more efficient way to handle this?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USkay
    1. USTwirrim
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POEfficient hunting for words in scrambled letters
      1. USkasyc
      1. VTFavorite
    2. VO
      singulars
      1. POEfficient hunting for words in scrambled letters
      1. USPaolo
      1. VTFavorite
    3. VO
      singulars
      1. POEfficient hunting for words in scrambled letters
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI'm not sure how efficient enchant is. But is it possible to find a list with all words that are *n* characters long? If so, you could load that list in memory and do a *in* instead of a enchant.check. I guess it is fast for long words. But the list will be too long for short words.
      singulars
      1. POEfficient hunting for words in scrambled letters
      1. USWillian
    2. CO@Willian, post this comment as an answer in order to vote up your approach: Insteat to catch for permutations in dictionary, check for all dictionary words letters in valid letters.
      singulars
      1. POEfficient hunting for words in scrambled letters
      1. USdani herrera
    3. COFair point @Willian, I had also written this with python-aspell bindings. It does look like Enchant is a bottleneck, the aspell version takes a lot less time (about half), however it's still going to take way too long brute force! Thanks everyone for your answers, some interesting ideas there. I'll try implementing them and see what sort of speed differences we'll see.
      singulars
      1. POEfficient hunting for words in scrambled letters
      1. USTwirrim
 

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