Facebook has a game called Word Challenge (on Yahoo it is known as Text Twist). The idea of the game is to form as many words as possible (of minimum length 3) given a set of 6 characters. It is the type of problem that can be easily solved with k or q.
My first attempt is basically brute-force:
w:w@=#:'w:?_0:`$words / read words & group by length
p:{[n;r]r(,/{y,/:&~x in y}[!n]')/,()} / nPr; permute r items from !n
f:{[r;s],/a@'(a:w r)(&:in)'s@p[#s]'r} / find words; r:lengths s:chars
The first line reads in a list of possible English words from a file and groups them by length. The second line is used to create the permutation (nPr) indices. The last line checks whether the words in the file appear in the list of permutations of the given characters.
While it works well for 6 or less characters, the performance is poor for longer strings since nPr is huge for large n and r. My second solution is better:
v:v@={x@<x}'v:?_0:`$words / read words, sort & group
c:{[n;r]r(,/{_[y-1+#z;!*z,x],\:z}[n;r]')/,()} / nCr; choose r items from !n
g:{[r;s]a@&0<#:'a:,/v@?,/(s@<s)@c[#s]'r} / find words;
The first line reads in the words, sorts each word lexicographically (think of it as reducing each word to a canonical form) and groups them according to that canonical form. The second line creates the combination (nCr) indices. The last line takes the characters, creates a list of all canonical forms obtainable from combinations of the characters and retrieves all the words associated with each canonical form. The performance is much faster because nCr is smaller and the pre-processing of v helps a lot.
Here’s a sample output for the characters “qwertyzxcvbi” and a list of 98,569 English words (/etc/dictionaries-common/words in Ubuntu). It took only 49 ms to compute.
brevity cervix verity zyrtec bizet brice bryce civet evict ritzy rivet tiber tribe trice twice write bert bevy bier bite bret brew brie brit byte cite city crew crib eric exit ibex rice rite ritz rive teri tier tire trey tyre verb very vibe vice view weir wire wiry wite wive writ yeti bet bic bit bye cry ice icy ire ivy rev rex rib rte rye tex tic tie try vet vex vic vie web wei wet wit wry yet yew zit
The code is here: fbwc.k.
