Home > Uncategorized > Word chains: Generalizing the chaining rules

Word chains: Generalizing the chaining rules

The word chain puzzle presented at codekata.com gives defines the following rule.

Successive entries in the chain must all be real words, and each can differ from the previous word by just one letter

Which I intepreted, from their samples, that substituion of one character at each step was allowed. At wordchains.com they define rules that allow more transitions:

A word chain is a simple word game, the object of which is to change one word into another through the smallest possible number of steps. At each step a player may perform one of four specific actions upon the word in play – either add a letter, remove a letter or change a letter without switching the order of the letters in play, or create an anagram of the current word.

It is quite easy to modify the haskell implementation to use this different ruleset instead. The only thing that is needed is another implementation of the neighbours function:

neighbours :: Word -> Word -> Bool
neighbours xs ys = 
   case length xs - length ys of
     0  -> chardiff xs ys == 1 || anagram xs ys
     1  -> elem ys (substrings xs)
     -1 -> elem xs (substrings ys)
     _  -> False
 where
   anagram xs ys = xs /= ys && sort xs == sort ys
   chardiff xs ys = length $ filter (\(a,b) -> a /= b) $ zip xs ys
   substrings xs = unfoldr generate ([],xs)
     where
       generate (_,[]) = Nothing
       generate (xs,(y:ys)) = Just (xs++ys, (xs++[y],ys))

Source code is stored at github.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: