## Chopping Words

### July 3, 2012

A simple word game starts with a word and repeatedly removes a single letter from the word, forming a new word, until there are no letters left. The act of removing a letter is called chopping and the resulting list of words is a chopping chain. For instance:

planet → plane → plan → pan → an → a

Your task is to write a program that takes a word and returns a list of all possible chopping chains that can be formed from the word, given a suitable dictionary. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 8 Responses to “Chopping Words”

1. […] today’s Programming Praxis exercise, our goal is to reduce a word one letter at a time, where each step […]

```import Data.Char
import Data.List

chop :: Eq a => [[a]] -> [a] -> [[a]]
chop dict xs = filter (`elem` dict) \$ zipWith (++) (inits xs) (tail \$ tails xs)

chain :: Eq a => [[a]] -> [a] -> [[[a]]]
chain dict xs@(_:_:_) = map (xs :) . chain dict =<< chop dict xs
chain _    xs         = [[xs]]

main :: IO ()
main = do dict <- fmap (lines . map toLower) \$ readFile "74550com.mon"
mapM_ print \$ chain dict "planet"
```
3. 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`.

```#!/usr/bin/env python

from itertools import permutations

def tails(xs):
return (xs[i:] for i in xrange(len(xs)))

def chain(word):
r = range(len(word))
return set(tuple(''.join(word[i] for i in set(r).intersection(ix))
for ix in t) for t in map(tails, permutations(r)))

def chop(word, dict_set):
return filter(lambda cs: all(c in dict_set for c in cs), chain(word))

if __name__ == "__main__":
from pprint import pprint
with open("/usr/share/dict/words") as f:
dict_set = set(line.strip() for line in f)
pprint(chop("planet", dict_set))
```
4. Axio said

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.

```import qualified Data.List as L
import qualified Data.Map as M

data ChopTree = Node String [ChopTree] deriving Show

dict = "/usr/share/dict/words"

rems :: [Char] -> [[Char]]
rems [] = []
rems (x:[]) = [""]
rems (x:xs) = xs:(map (x:) (rems xs))

tree2list :: ChopTree -> [[String]]
tree2list t = aux t []
where
aux (Node w []) l = map reverse [w:l]
aux (Node w ll) l = concatMap (\v->aux v (w:l)) ll

chop :: [Char] -> IO ChopTree
chop = chop' dict where
chop' :: FilePath -> [Char] -> IO ChopTree
chop' dic word = do
dic' <- readFile dic >>= (\f -> return \$ M.fromList (map (\x->(x,True)) (words f)))
return \$ chop'' dic' word
chop'' :: M.Map [Char] a -> [Char] -> ChopTree
chop'' dic word =
let subW = rems word in
let validSubW = filter (flip M.member dic) subW in
Node word (L.map (chop'' dic) validSubW)
```
5. Mike said

Python:

‘chain()’ returns a generator that returns each chain, one at a time.

```from itertools import combinations, ifilter

with open("/python27/12dicts/2of12inf.txt", "rt") as f:
wordlist = set(w.strip().lower() for w in f)

wordlist.update('abcdefghijklmnopqrstuvwxyz')

def chain(word, dictionary):
is_word = dictionary.__contains__
join = ''.join

def aux(wds, wlen):
if wlen == 1:
yield wds

else:
for wd in ifilter(is_word, map(join, combinations(wds[-1], wlen - 1))):
for wlist in aux(wds + [wd], wlen - 1 ):
yield wlist

return aux([word], len(word))

for wlist in chain('planet', wordlist):
print wlist

```
6. CaCaEgg said

Use a tree to map all the words in dictionary

7. […] 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. […]

8. JP said

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`:

```> (chopping-words dict "PLANET")
'("PLANET"
("PLANE"
("PLAN" ("PAN" ("PA" ("A")) ("AN" ("A"))))
("PANE" ("PAN" ("PA" ("A")) ("AN" ("A")))))
("PLANT"
("PLAN" ("PAN" ("PA" ("A")) ("AN" ("A"))))
("PLAT" ("PAT" ("PA" ("A")) ("AT" ("A"))))
("PANT"
("PAN" ("PA" ("A")) ("AN" ("A")))
("PAT" ("PA" ("A")) ("AT" ("A")))
("ANT" ("AN" ("A")) ("AT" ("A"))))))
```