Programming Praxis

8 Responses to “Chopping Words”

1. Programming Praxis – Chopping Words « Bonsai Code said

   July 3, 2012 at 10:27 AM

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

   July 3, 2012 at 10:27 AM

   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. Graham Enos said

   July 3, 2012 at 8:56 PM

   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

   July 5, 2012 at 4:55 AM

   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

   July 5, 2012 at 9:53 PM

   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

   July 7, 2012 at 10:32 AM

   Use a tree to map all the words in dictionary

   http://codepad.org/XBwJufSS
7. Chopping words | jverkamp.com said

   October 15, 2012 at 1:04 PM

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

   October 15, 2012 at 11:11 PM

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