Posts Tagged ‘chop’

Programming Praxis – Chopping Words

July 3, 2012

In today’s Programming Praxis exercise, our goal is to reduce a word one letter at a time, where each step must be a new valid word. Let’s get started, shall we?

Some imports:

import Data.Char
import Data.List

First we need a function to determine all the valid words that are one letter shorter.

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

Next, we apply this function recursively as long as the remaining word consists of two or more letters. We keep a list of the steps we took.

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

To test if everything is working properly, we load a dictionary (making sure to convert it to lowercase) and print the results for the word “planet”.

main :: IO ()
main = do dict <- fmap (lines . map toLower) $ readFile "74550com.mon"
          mapM_ print $ chain dict "planet"

We get 44 results instead of the 40 Phil got, which seems to be due to the presence of the word “ne” in my word list.