NWRUG Quiz: Word Chains Kata

Given two words of equal length, write a program that can build a chain of words connecting the first to the second. Each word in the chain must be in this word list and every step along the chain changes only one letter from the previous word.

For example, given the start word "cat" and the end word "dog", a valid chain would be:

"cat", "cot", "cog", "dog".

Another example "duck" to "ruby" would have a valid word chain:

"duck", "ruck", "rusk", "ruse", "rube", "ruby"

If you get your code working, try timing it. Does it take less than a second for the above examples? And is the timing the same forwards and backwards? Does your code find the shortest possible valid word chain?

The challenge

See if you can find the shortest possible word chain that goes from the word "ruby" to the word "crew".

SPOILER ALERT

There is a walkthrough of the kata over on The Programatic Bookshelf Blog. It's written in Haskell, but the discussion of the problem and how to break it down may be helpful if you are struggling to solve the problem.