Programming Praxis – Chopping Words

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.

Tags: , , , , , , , , ,

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 34 other followers

%d bloggers like this: