Friday, May 20, 2011

Scrabble Algorithms

If you are playing scrabble and you have n letters, what are all the possible words that you can make from these n letters?
It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler.
Below are the possible words for letters 'abc'. I have highlighted the patterns in them.
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
For n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations of each letter which is O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). The time complexity is quite high.

All possible words for n letters can be obtained by using the permutations algorithm of n letters with a very simple mod. The changes are in blue.

permutation(char[] in){
//initially, used[] set to false and depth is 0
permuteWords(in, out, used, 0)
}

permuteWords(char[] in, buffer out, bool[] used, int depth){
print out
if depth = in.length:
print out
return
for (int i = 0; i < in.length; i++):
if used[i] = true:
continue
used[i] = true
out.append(in[i])

permuteWords(in, used, out, depth +1)

out.length = out.length -1
used[i] = false
}


Time complexity is the same as that of permutations O(n^n) O(n!) [update n! not n^n].
A better way is to have each word added to a list (the list would be created in permutation method and passed as parameter to permuteWords method) for extensions of the problem. 
Possible extensions to this scrabble problem are:


  • Find the longest word. 
  • Find the word with maximum points given a map of points to each letter.
  • You have a dictionary, how would you use it to get the valid words? For this, I would assume that the dictionary has a function like boolean isValidWord(String s) which would indicate if a particular word is valid or not. Here is another interesting thought with the dictionary extension which requires a trie structure. I could use a dictionary, to see if I can bust out of permuting further as mostly not all permutations are going to be valid words. For example, if you have a dictionary implemented as a trie with a function boolean hasPrefix(String s) or hasPrefix(char c) and letters 'aabc' and suppose that the dictionary does not have a trieNode structure a-a, you do not have to permute further for the unused characters 'bc'. Below is the changed code that I came up with (not tested). 

Set getValidWordsPermutation(char[] in){
Set validWords = new HashSet();
//initially, used[] set to false and depth is 0
permuteWords(in, out, used, 0, validWords);
return validWords;
}
permuteWords(char[] in, buffer out, bool[] used, int depth, Set validWords){
// if the current prefix is not present in the dictionary, then do not permute further with the rest of the unused letters
if !dict.hasPrefix(out): //or dict.hasPrefix(out[out.length()])
return

//if current prefix is a word, add to the set
if dict.isValidWord(out):
validWords.add(out)

if depth = in.length:
return

for (int i = 0; i < in.length; i++):
if used[i] = true:
continue
used[i] = true
out.append(in[i])

permuteWords(in, used, out, depth +1, validWords)

out.length = out.length -1
used[i] = false
}


Using the dictionary, only those trieNodes forming valid words possible from the n letters are traversed in the dictionary trie [O(|V|+|E|) time] and not all permutations [O(n^n) time]. If all permutations are valid words OR if there is no such hasPrefix(String s) function for trie, then it takes O(n^n) time - which is better than O(nCn * n^n) + O(nCn-1 * n-1^n-1) + ... O(nC1 * 1^1). 

0 comments:

Post a Comment