Scrabble word generator

Question

After watching my brother cheating in an iphone game like scrabble I was wondering what was the algotithm behing it.

Given some letters: A B C T E E

And SQL table full of correct words.

How would I create all combinations of letters for making afterwars a select like: Select * from words where word IN ('A','AT',...), just to take from those combinations the ones that are correct ?¿

Another possible way could be a SQL table with every letter in a column for each word. But afterwards the system should verify that any word form the select has more time the same letter given.

Ex:

c1 c2 c3 c4 t e e a i r

This question is just for feeding curiosity, and learning witch algorithm it might be used in for creating all those combinations (with full and partial given letters) to check afterwards if they exist.

Thanks!

font: http://icon.cat/worder/wordsfinder

possible duplicate of [Algorithm to get a list of all words that are anagrams of all substrings (scrabble)?](http://stackoverflow.com/questions/880559/algorithm-to-get-a-list-of-all-words-that-are-anagrams-of-all-substrings-scrabb). See also http://stackoverflow.com/questions/tagged/scrabble — JJJ, Apr 21 '12 at 13:21
Well the simplest algorithm (but also the most inefficient) would be to simply check all possible combinations and query the database. I'm also interested to know what would come up here. — Madara's Ghost, Apr 21 '12 at 13:22

score 2 · Answer 1 · answered Apr 21 '12 at 14:13

To find all possible valid word this are the following steps

Find all possible combination
Find each permutation for each word in the combination
Search Database for the words
List the words

Script

$tiles  = array( "A", "B", "C", "T", "E", "E") ;
$words = array();
$set = powerSet($tiles,2);

$mysql = new mysqli("localhost","root","","word");
$sql = "SELECT id from dic WHERE word = '%s'" ;

foreach ($set as $key => $value)
{
    $word = implode("", $value);
    $wordPermutation = permute($word);

    foreach($wordPermutation as $keyWord)
    {
        if(!in_array($keyWord, $words))
        {
            //if($result = $mysql->query(sprintf($sql,$keyWord)))
            //{
                //var_dump(sprintf($sql,$keyWord));
                //if($result->num_rows > 0)
                //{
                    $words[] = $keyWord ;
                //}
            //}
        }
    }
}


print_r($words);

Functions

function powerSet($in, $minLength = 1, $max = 10) {
    $count = count ( $in );
    $members = pow ( 2, $count );
    $return = array ();
    for($i = 0; $i < $members; $i ++) {
        $b = sprintf ( "%0" . $count . "b", $i );
        $out = array ();
        for($j = 0; $j < $count; $j ++) {
            if ($b {$j} == '1')
                $out [] = $in [$j];
        }
        if (count ( $out ) >= $minLength && count ( $out ) <= $max) {
            $return [] = $out;
        }

    }
    return $return;
}


function permute($str) {
    if (strlen($str) < 2) {
        return array($str);
    }
    $permutations = array();
    $tail = substr($str, 1);
    foreach (permute($tail) as $permutation) {
        $length = strlen($permutation);
        for ($i = 0; $i <= $length; $i++) {
            $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }
    return $permutations;
}

Please note that i commented out the database verification section so that the demo can work

See Demo

http://codepad.viper-7.com/oG6E6w

score 1 · Answer 2 · answered Apr 21 '12 at 13:23

1

I would try something like

WHERE (word like '%A%' and not word like '%A%A%')
  AND (word like '%B%' and not word like '%B%B%')

and so on. But I'm sure there must be more professional solutions!

answered Apr 21 '12 at 13:23

Mr Lister

45,515
15
108
150

1

This won't work when you have the same letter multiple times. – Guillaume Poussel Apr 21 '12 at 13:26
Well, it does need to be a more clever algorithm, but for letters that you have double you can write `((word like '%E%' or word like '%E%E%') and not word like '%E%E%E%')`. If I sat down and seriously thought about it, I'm sure I could make it work! – Mr Lister Apr 21 '12 at 13:29
I thought about that too, but with all those AND you would just get the largest words, not the ones that just use 3 of 5 letters given. Maybe using this, there should be a select for each combination of letters and using a "Length". But using all that can't be fast. – Xfoguet Apr 22 '12 at 09:58
You're right, it isn't a good solution. And it doesn't filter on letters that you don't have at all, so, never mind. – Mr Lister Apr 22 '12 at 10:23

score 1 · Answer 3 · answered May 01 '12 at 17:17

I finally got it working.

If someone is ever interested on making a self word generator, this is how I made it.

MySQL, a table with:

[id] , [Word]

a view for each length:

V1 = Select Word from TABLE where LENGTH(Word) = 1
V2 = Select Word from TABLE where LENGTH(Word) = 2
[...]

php side:

Using the functions of baba, I made an array where: array[2] are the combinations of letters that have a length of 2, and so on.

Finally all i had to do is a Select for each array to the view like

Select Word from V3 where Word like ('asd','dsa',....);

There must be a faster way, but with a less than a second (localhost) and word diccionary of 700K made its way.

score 1 · Answer 4 · edited Oct 11 '13 at 04:45

A better way to achieve unscrambling is to use anagrams. So instead of having a library of all the possible words, use an associative array using the letters that make up the words as the index.

anagram['aer'] = ['are', 'ear', 'era']

To implement this, loop through all of your dictionary words and push each one into an array where the index is the letters of the word in alphabetical order.

for(var i = 0; i < dictionary.length; i++) {
//Loop through dictionary array
    var str = words[i].split('').sort().join('');
    //break apart the word and sort it alphabetically
    if(!anagram[str]) {
        //check if there is already an index with that same anagram
        anagram[str] = [];
    }

    anagram[str].push(words[i]);
    //Add the word to the anagram array

}

This way allows you to quickly index the library without going through thousands of possible permutations.

An example of this method in javascript: Word Unscrambler

score 0 · Answer 5 · answered Apr 21 '12 at 13:22

0

Here is great article about World fastest scrabble program

You just should have some knowledge in Descrete Math(Word Automats). Hope it will help you :)

answered Apr 21 '12 at 13:22

Zhivko Draganov

1,213
2
10
16

Scrabble word generator

5 Answers5