Kata Nineteen - Word Chains

Write a program that solves word-chain puzzles.

There’s a type of puzzle where the challenge is to build a chain of words, starting with one particular word and ending with another. Successive entries in the chain must all be real words, and each can differ from the previous word by just one letter. For example, you can get from "cat" to "dog" using the following chain.

  cat
  cot
  cog
  dog

The objective of this kata is to write a program that accepts start and end words and, using words from the dictionary, builds a word chain between them. For added programming fun, return the shortest word chain that solves each puzzle. For example, my Powerbook running Ruby can turn "lead" into "gold" in four steps (lead, load, goad, gold), taking about 20 seconds. Turning "ruby" into "code" takes six steps (ruby, rubs, robs, rods, rode, code) and 90 seconds, while turning "code" into "ruby" (again in six steps) takes about an hour. Go figure…

Update: It turns out that my original algorithm was pretty dumb: a better approach greatly speeds up search and makes it symetrical. It now does all the above examples in between 0.5s and 1s.

Comments

[Amit]

So does the word conversion always happen between words of similar length?

[Dave Thomas]

Yes

[Matt Howells]

Dave is incorrect. The word list provided on this site contains many words which cannot be transformed to all the other words of the same length in the list. e.g. ebb, Abba, Aaron, etc.

*spoiler alert*
The technique I used to solve this Kata was to do a breadth-first search of the tree of possible chains from a particular word, generating the tree as I went. This technique gives the shortest possible chain of words from one word to another (if it exists). In order to make the algorithm efficient I used a ternary search tree to store a dictionary of words of the given length. As each word was added to the tree of chains, it was removed from the dictionary, preventing it from being considered again. I haven't done any rigorous benchmarking but it runs in well under a second for any given two words (in C#).

i would be interested to hear of other successful approaches.

[Dave Thomas]

I don't believe I'm incorrect: given a word of length four, it must always transform to another word of length four.

However, such transformations are not always possible.

[Michael Davies]

Hi Dave,
Isn't #('ruby' 'rube' 'rude' 'rode' 'code') the shortest path from ruby to code?

[Dave Thomas]

If your wordlist has 'rube'... Mine doesn't. :)

[Johannes Spielmann]

Your word list link seems to have died. Maybe you could put up another file or link to some generic word list like http://wordlist.sourceforge.net/