Draw something cheat
Draw something
Draw something is one game I really enjoy playing and don’t feel guilty wasting my time with. That said, occasionally, I have no clues what my friends drew for me which drives me insane. To be honest, I had to visit a cheat site a couple of times. I know it defeats the purpose of the game not to mention it’s not honest but I needed coins to buy more colors, desperately :).
Cheat
Cheat sites ask you to provide two things:
Letters
The number of letters that make up the answer
and generates all possible combinations of the given letters that can form an English word.
Permutations and word validation
You need to do two things.
Generate all possible permutations
Filter out permutations that are not English words
String permutation in javascript
Below is a Javascript I wrote to generate all possible permutations within the given length. It took me a while to get this right (and I am still a rookie in javascript world).
results is an array to store permutations
input is a string from which you pick letters
output is an array that stores a single permutation
used is an array that stores flags to mark used letters
size is integer to pass the length of the word. i.e. size is 4 of the word jean
level is an integer to track the permutation is complete
var permutate = (function() { var results = []; function doPermute(input, output, used, size, level) { if (size == level) { var word = output.join(''); results.push(word); return; } level++; for (var i = 0; i < input.length; i++) { if (used[i]) { continue; } used[i] = true; output.push(input[i]); doPermute(input, output, used, size, level); used[i] = false; output.pop(); } } return { getPermutations: function(input, size) { var chars = input.split(''); var output = []; var used = new Array(chars.length); doPermute(chars, output, used, size, 0); return results; } } })();
Here is the working example on jsfiddle http://jsfiddle.net/jinwolf/Ek4N5/29/
Here are some patterns I used in the example
Singleton pattern
I used the typical Javascript singleton pattern.
Immediate instantiation
by putting parenthesis around the function, the function gets executed immediately and the permutate variable gets instantiated without an extra explicit invokation of the function.
Closures
The permute object still has access to the private variable results andthe private method doPermute even though it’s been already returned from the main function. It’s called closure in Javascript
Visualize how it works
There is no tree style data structure in this algorithm but if you look at how it builds a permutation, it looks very similar to how Preorder Traversal works in a tree data structure. In other words, it starts from the element itself and moves down to the most left descendant. It keeps drilling down the path until it hits the bottom. Once it reaches the end of the tree, it moves to the right sibling at the same level. After all siblings are visited, it moves up one level and moves to the right sibling. And it keeps doing it until every element in the tree is visited
it starts from ‘a’ (level 1)
it moves one level down and visits ‘b’, skipping ‘a’ since it’s already taken (level 2)
it move one level down and visit ‘c’ skipping ‘a’ and ‘b’ (level 3)
‘c’ is the bottom of the tree and there is no siblings left at that level (level 3)
it moves up one level (level 2)
it visit ‘c’ which is the next sibling of ‘b’ (level 2)
it move one level down and visit ‘b’ skipping ‘a’ and ‘c’ since they are taken (level 3)
no siblings left on level 3 so it moves up one level (level 2)
Again, there is no siblings left on level 2 so it moves up one level (level 1)
Moves to the next sibling ‘b’ on level 1 which is not shown here (level 1)
Repeats the same process
the output and used variables are passed down to the next level using recursion