I was recently pondering algorithms for solving word chain puzzles. Just for fun, I decided to implement a couple of these algorithms as SQL Server stored procedures. I know that this is a rather silly idea. I could have easily written something in C that would run much faster. I chose SQL Server for two reasons. First, I wanted a challenge. Second, I wanted to use this as an experiment to learn how to make stored procedures that run efficiently.
I did my best work with these procedures. However, it is quite likely that there is something that I could have done better. Here's what I am asking for. I want you to show me what I could have done better. If you can make these procedures run faster, please teach me how.
For those who are not familiar with word chains, here's an explaination. The puzzle consists of a starting word and an ending word. The solution (which the stored procedures attempt to discover) is a list of words, each differing by a single letter from the previous word, which creates an unbroken chain from the starting word to the ending word. For example, if the chain were to start with "bread" and end with "toast," the chain might be "bread break bleak bleat blest blast boast toast." The procedures rely on the existence of a dictionary. Each word in the chain must belong to the dictionary (i.e. nonsense words are not allowed).
I created procedures for two variations of this game. The first one, named FindChain1, requires that each word in the chain be of uniform length. The second one, FindChain2, is slightly more complicated. It allows three types of chain links. When a new word is added to the chain, it can be formed by substituting one letter for another, deleting a letter, or adding a letter. For example, if the chain were to start with "bread" and end with "toast," the chain might be "bread bead beat boat boast toast."
Oh yeah, I should also mention that the procedures need to find the shortest possible chain that solves the puzzle. If there are multiple chains which are all the shortest length, only one needs to be discovered.
This project has been a fun diversion for me and I hope that it proves equally rewarding for you as well.
I create two scripts. Well, okay, Enterprise Manager create them. The first of the two scripts, Create Tables.sql, should create the tables that the procedures use. The second script, Stored Procedures.sql, should create the stored procedures. The scripts can be found at http://myweb.cableone.net/mrog/
. You will need to supply a dictionary. I downloaded one from wordlist.sourceforge.net. Insert the dictionary words into the dictionary table. Then run the stored procedures PopulateLookupTable1 and PopulateLookupTable2. These will convert the dictionary into the form that FindChain1 and FindChain2 require. The FindChain procedures take three parameters: a starting word, and ending word, and a variable to accept the return value.
Feel free to work on this over the next few days. I am not in a big hurry. Thank you. Have fun!