Continuing in my recent set of Word Games from Programming Praxis, today we’re tasked with finding all words made from a grid of letters. So for example if we have this grid:
NCB CIO UNE
We want words like
NINE. (There are two additional constraints that each word must have at least 4 letters and must contain the middle letter of the grid–
I in this case.)
To start with, we’re going to need the dictionary library I previously posted.
With that, her is the code to solve a word cube:
; given a gride of letters, find all words of at least length 4 with the center ; ; example: ; NCB ; CIO ; UNE ; I is required (define (word-cube dict letters) ; setup, sort the list descending so we end up in alphabetical order ; assume the 'required' letter is at the midpoint (let ([letters (sort (string->list (string-upcase letters)) char>?)] [required (char-upcase (string-ref letters (quotient (string-length letters) 2)))]) ; return strings (map list->string ; filter out words that are too short or don't contain the middle letter (filter (lambda (word) (and (>= (length word) 4) (member required word))) ; recursively build all words using only the letters given (let loop ([letters letters] [word '()] [node (:dictionary:-value dict)]) (apply append ; loop over the letters (let ([r (for/list ([l (unique letters)] #:when (lookup node l)) (loop (remv l letters) (cons l word) (lookup node l)))]) ; return this word if it's an endpoint (if (lookup node 'word) (cons (list (reverse word)) r) r))))))))
There are a few interesting points, all commented above. Essentially, I’m finding *all* words made from the letters in the puzzle first and only then filtering out words shorter than 4 characters or words that don’t contain the required central letter. The main loop starts with all of the words and the root node and then recurs down every valid tree.
(for/list ([l (unique letters)] #:when (lookup node l)) (loop (remv l letters) (cons l word) (lookup node l)))
This controls the recursion, looping across the letters (I used
unique to avoid duplicates in the final solution) but only on letters that could be next (the
#:when (lookup node k)). Then recur, removing the letter we used, adding it to the word, and recurring down the dictionary.
So does it work?
> (word-cube dict "ncbcioune") '("BENIN" "BOCCI" "BOCCIE" "BONNIE" "BUNION" "CINE" "COIN" "CONCUBINE" "CONIC" "CONNIE" "CUBIC" "CUNNI" "ENNUI" "ICON" "NICE" "NINE" "NUNCIO" "UNION")
Yup. Works great. It’s fun when previous work takes the lion’s share of the workout of a problem. They say that it’s the mark of a successful mathematician when always try to reduce a problem to previous work, but I’d say that it applies to computer science just as well.
|← A Sea of Stars – Ch. 14 – Madeline||All||Dodgson’s Doublets →|
|← Squaring the Bishop||By category||Dodgson’s Doublets →|