Finding words in k

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.

Posted in k&q. Tags: , , . Leave a Comment »