Chopping Words
July 3, 2012
To find all the words that can be formed by chopping a single letter from a word, we simply iterate through the word one letter at a time, keeping only those chopped words that are in the dictionary:
(define (chops str)
(let ((len (string-length str)))
(define (chop n)
(string-append
(substring str 0 n)
(substring str (+ n 1) len)))
(filter word? (map chop (range len)))))
A word is represented as a string w, a chopping chain is represented as a list of words ws, and the collection of all chopping chains that can be formed from a given input is a list of list of words wss. The inner map
takes a single chopping chain and returns all possible extensions to it, the outer mappend
operates over the collection of chopping chains, and the loop
runs until the words are only a single letter.
(define (chop str)
(let loop ((wss (list (list str))))
(if (= (string-length (caar wss)) 1)
(map reverse wss)
(loop (mappend
(lambda (ws)
(map
(lambda (w) (cons w ws))
(chops (car ws))))
wss)))))
Mappend
is like map
, but uses append
instead of cons
to build the output list. We used mappend
instead of map
in order to make the types come out right. We find forty chopping chains for the input planet, and learn some new words:
> (chop "planet")
(("planet" "plant" "pant" "ant" "at" "t")
("planet" "plant" "pant" "ant" "at" "a")
("planet" "plant" "pant" "ant" "an" "n")
("planet" "plant" "pant" "ant" "an" "a")
("planet" "plant" "pant" "pat" "at" "t")
("planet" "plant" "pant" "pat" "at" "a")
("planet" "plant" "pant" "pat" "pt" "t")
("planet" "plant" "pant" "pat" "pt" "p")
("planet" "plant" "pant" "pat" "pa" "a")
("planet" "plant" "pant" "pat" "pa" "p")
("planet" "plant" "pant" "pan" "an" "n")
("planet" "plant" "pant" "pan" "an" "a")
("planet" "plant" "pant" "pan" "pa" "a")
("planet" "plant" "pant" "pan" "pa" "p")
("planet" "plant" "plat" "lat" "at" "t")
("planet" "plant" "plat" "lat" "at" "a")
("planet" "plant" "plat" "lat" "la" "a")
("planet" "plant" "plat" "lat" "la" "l")
("planet" "plant" "plat" "pat" "at" "t")
("planet" "plant" "plat" "pat" "at" "a")
("planet" "plant" "plat" "pat" "pt" "t")
("planet" "plant" "plat" "pat" "pt" "p")
("planet" "plant" "plat" "pat" "pa" "a")
("planet" "plant" "plat" "pat" "pa" "p")
("planet" "plant" "plan" "pan" "an" "n")
("planet" "plant" "plan" "pan" "an" "a")
("planet" "plant" "plan" "pan" "pa" "a")
("planet" "plant" "plan" "pan" "pa" "p")
("planet" "plane" "lane" "ane" "an" "n")
("planet" "plane" "lane" "ane" "an" "a")
("planet" "plane" "pane" "ane" "an" "n")
("planet" "plane" "pane" "ane" "an" "a")
("planet" "plane" "pane" "pan" "an" "n")
("planet" "plane" "pane" "pan" "an" "a")
("planet" "plane" "pane" "pan" "pa" "a")
("planet" "plane" "pane" "pan" "pa" "p")
("planet" "plane" "plan" "pan" "an" "n")
("planet" "plane" "plan" "pan" "an" "a")
("planet" "plane" "plan" "pan" "pa" "a")
("planet" "plane" "plan" "pan" "pa" "p"))
We used range
, mappend
, and read-line
from the Standard Prelude, and wrote functions read-words
to read all the words into a dictionary and word?
to look up words in the dictionary. Our dictionary is simply a list of words; our program could be faster if we used a hash table or trie to store the dictionary, but a list is sufficient for exploratory programming like this. You can run the program at http://programmingpraxis.codepad.org/7kB3lbiz, where you can also see all the auxiliary code.
[…] today’s Programming Praxis exercise, our goal is to reduce a word one letter at a time, where each step […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/03/programming-praxis-chopping-words/ for a version with comments):
Not terribly pretty, but it does the job. I end up with more chopping chains than the above, only because of my using
/usr/share/dict/words
.Builds a tree of possible chops, then “flattens” it to obtain a list of all possible paths from root to nodes.
This would of course benefit a lot from memoization, since we’re doing again and again the same chops recursively.
Python:
‘chain()’ returns a generator that returns each chain, one at a time.
Use a tree to map all the words in dictionary
http://codepad.org/XBwJufSS
[…] One more challenge from Programming Praxis’ Word Games today (there are only a few left!). This time we have the challenge of cutting off bits of words, one letter at a time, such that each step is still a word. […]
Here’s my solution in Racket: Chopping Words
I went a step beyond what the problem strictly asked and returned a nested tree-like structure with all possible chains of chopped words. Using the recursive solution that I was, it really wasn’t much harder than just returning a single solution and it still runs rather quickly.
Here’s a sample run for
PLANET
: