Mar
15
I've been evaluating a piece of software at work recently. Do get it up and running I needed to install Windows, database engine and the application which is itself quite heavy and takes ages to install.
Instead of staring at the installation progress bar all day long, I take a look at Dave Thomas' Code Kata. I always wanted to practice some of those. Since it seems I will be installing different stuff for the rest of the day, I fired up the editor and got into coding.
I took Code Kata no 19 - Word Chains. First attempt failed miserably. It was a depth-first search and though it was reasonably fast, it was giving unreasonable results (like 60-word chain for 'cat-dog').
Then I tried breadth-first approach. It was much better. The algorithm guaranties finding shortest solution but I was not satisfied with its speed. It took 5 minutes to find the 'ruby-code' chain.
Instead of searching for a better algorithm, I tried to optimize what I had. Five minutes was enough to find a trick (tweak?). Having implemented it, I was able to get each of Dave's examples in less than 0.5 seconds (Python on ThinkPad T42).
The problem basically reduces itself to search in a tree. The trick I used boils down to choosing smart which branches to explore. I simply choose only those which are closer to the target word (in terms of number of different letters). There might be a problem with this solution: since I am aggressive in optimizing, I might not be able to find a solution should it require taking sub-optimal branch at some moment.
Thanks Dave, this is a great kata. I had so much fun coming with the solution. I definitely am going to take some more exercises.