|Perl: the Markov chain saw|
A Better Word Morph Builderby Limbic~Region (Chancellor)
|on Jun 29, 2006 at 15:30 UTC||Need Help??|
Limbic~Region has asked for the
wisdom of the Perl Monks concerning the following question:
In this thread, Ieronim posted a cool script. It finds the shortest bridge between two words where all the words in the bridge can be found in a dictionary and each word differs from its adjacent partners by only one character.
I posted what I believe to be a very fast elegant solution:
The algorithm is simple. First, create a datastructure that relates all words of a given length to all other words of the same length with a Levenshtein Distance of 1. This is a one time up-front cost. Next, simply perform a breadth first search starting from one end and stopping when the other end is encountered.
With the hard work done up front, the task can be accomplished in about 20 lines of code. Is anyone aware of a more efficient (faster run-time) algorithm? As usual, this is just one of my "I want to learn" questions and there is no real-world speed barrier I am trying to break. It just seemed to me that there should be some way to eliminate some paths during the BFS. I think an evolutionary algorithm technique might work. Paths that increase the Levenshtein Distance to the target word would not be allowed to survive. Even if this does work, I am not sure that the reduction in search space is worth the added distance calculation.
I appreciate any ideas on this.* The original did allow for the endpoints not to be dictionary words.
Cheers - L~R