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.

About these ads

Tags: , , , , , , , , ,

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 35 other followers

%d bloggers like this: