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.

About these ads

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

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/03/programming-praxis-chopping-words/ for a version with comments):

    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

    http://codepad.org/XBwJufSS

  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"))))))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: