Essays/Boggle
Boggle is a word game, where players search for words on a grid of letters by finding them in sequences of adjacent squares.
Search
The board is given as a character matrix. Paths are lists of indices into the raveled string. The equivalent graph indicating adjacent indices in the flattened string is used to expand paths. Paths that return to the same index, or don't fill out a prefix according to the dictionary are dropped as the search churns along.
Eventually, no more prefixes are available or all the squares have been visited and the search terminates via fixpoint ^: a:. Then, the exact words are selected, nubbed, sorted lexicographically, and sorted length-wise.
The lookups are done by binary search on sorted arrays (I.). This turns out to be good enough, though not blazing fast.
Program
NB. requires at least j-902-beta-i due to direct definitions
WL =: (<_1{.a.),~<;._2@(1!:1)@<
W =: = WS {~ (WS=: WL'collins-words.txt')&I.
P =: = PS {~ (PS=: WL'collins-prefixes.txt')&I.
G =: [: <@-.&_1"1 @ |: [: ;"_1 (<:3 3#:4-.~i.9)&(|.!._1)
QU =: {{ 'U' (1+I.b)} y #~ 1+b=. 'Q'=y }} ^: ('Q'&e.)
Q =: QU :. (#~ [: -. _1 |. 'QU'&E.)
L =: {{ <@Q"1 @: ({&u) }}
A =: [ ,"_ 0/ [ -.~ ] {::~ {:@[
E =: {{ ([: (#~ P @: (u L)) [: ; <@(A&v)"1) ^: (0<#) &. > }}
S =: {{ (,y) E (G i.$y) ^: a: <,.i.#,y }}
B =: {{ (\:#&>) /:~ ~. (#~ W) ; (,y) L"1 &.> S y }}
Comments
Brief remarks about each definition:
- WL is used to read files that contain word lists. WS is a list of words from the collins dictionary and PS is a sorted list of unique prefixes therefrom.
- W and P query the word lists and given a list of boxed strings return 1 for each exact match or prefix match resp. The reason _1{.a. is appended to the word list is to prevent index errors when querying say <'ZZZ'.
- G takes a grid and computes an adjacency list of indices into the raveled version.
- Q is used to expand Q tiles to QU and back. I found it to be more efficient to first check if a Q is in the path, thence the power conjunction.
- L takes path in board u and gives the letters.
- A expands path x according to adjacency list y ensuring vertices are pathwise unique.
- E expands paths, if any are left, according to adjacency list v, selecting only those that form valid prefixes on the board u
- S iteratively expands paths according to the shape of the board y starting with one path of length 1 at each index. All intermediate matches are kept to select the exact matches.
- B ties it all together and solves the board.