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

[Squanderingtime]

We just did this Kata the other night at the Chicago Ruby meetup. I played with it afterward and came up with a (semi?) simple Hadoop MapReduce implementation that works in fully-distributed mode. Definitely not as fast as a simple Ruby implementation, but watching an entire cluster solve it in parallel quickly is pretty snazzy :-).

http://github.com/cchandler/codekata19-mapreduce

[jon]

Any chance of getting the dictionary reposted, or even an indication of the number of words would be helpful.

I am using the 360k Moby word list. Is anyone else?

[Loren]

I'd be interested to see how long it takes people to get from "the" to "end". That particular beast takes the longest for me, about 2.2s. Everything else is under .5s.

I'm not sure about all the particulars of how Matt did it (ternary search tree?!). I went ahead and made a customized object that would store its relative path, and retrieve all words that a) weren't in its path and b) were one-off in terms of letters.

cat-dog takes 49ms, ruby-code 13ms, lead-gold 33ms, the-end !2240ms!

Is everyone else's searches slow for the-end?

[Luke]

I took a look at this in C# - and so far have a nice solution that is very fast. However my first implementation will only complete if the new letter appears in the final word.

However this fits in with the 3 cases above:
cat-cot-cog-dog
ruby-rube-rude-rode-code

however at the moment if there was no rube it would need to find
a replacment for U B or Y that was either O D or E in the correct place.

So its great for finding the shortest path in under 0.5s however i might need to review it for longer chains. Any recommended word sets?

[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/

[Dave Thomas]

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

[Michael Davies]

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

[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.

[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]

Yes

[Amit]

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