Looking for a final word...

[hometown]

From a certain English word, I would like to know how many steps, which is the minimum number of elementary operations, I will have to make so as to come to the last word which has been predefined. Each time I make a move, there is only one character in the sequence being allowed to change. To be more concrete, for instance, I have a term called cooler, first I will have to try changing it into fooler, and then foller, again feller, one more time fellor, and finally fellow which is the final word I am looking for, and I have already made five moves after all.
Could you give me your ideas, advice, comments etc, on how to accomplish this ? Please help...

Thank you very much...
Nina.

[mwilliamson]

just see what letters are different?

[PaulWendt]

I don't know exactly what a "move" entails, but from how you
described it, I'd be inclined to agree with mwilliamson.


cooler
fellow


There are 5 letters that are different so that's how many moves
it took you.

--Paul

[Bassman]

If this is the same game that I've played before, the word after each single letter has changed still has to be a valid English word.

In which case, it gets a whole lot more fun!

Personally, I might be tempted to solve this using graph methods - by taking a huge dictionary of words (from dictionary.com?) and creating a connectivity graph between the words where a single letter change makes a different valid word. So, if each word is a vertex, then there is an edge between two vertices iff a single letter can be changed to make the other word.

Then you end up with a nice collection of connected graphs for each word length (4-letter words, 5-letter words graph.)

Take the two vertices in the graph which correspond to the words you're trying to find, and then... use your favourite shortest path algorithm to find the path between them.

Check out the Dijkstra [spelling?] algorithm. Never let me down!

The worst part will be writing the program to pre-compute the graph between the words - it'll take a long, long time to run and you'll want some super computing power for that. But once that's done, you can just use the graph for every subsequent run of the program, and the actual computation itself will be pretty snappy!

If you really want to get fancy, you can add words to the graph as users enter them if they're not already in the master dictionary.

...unless the words don't have to be valid English, in which case none of this is necessary after all!

Wheeee!

Regards,
Bassman

[hometown]

I am studying about "classic" sorting, searching, this is my assignment, I have to hand it in on 15th of August. Quite long from now on...but I think it is not an easy problem for me,so I now make questions and try to search for some explanations about it....
My professor said there was two problems for me to choose: anagram and this one. I thought if I chose anagram, I would get stuck with database which I have just started learning for around two months...I dont think I can design or program anything related to it...
But now, Bassman's explanation makes me more embarrassed... I am afraid that I willnot be able to make it on time...
Moreover, it is of certain that the words chosen have to be valid in meaning, which is also what my teachers told me again today. I once thought it was fine if those words could turn out wrong in meanings, so I made myself such an example...
Besides using graph theory and Dij algorithm, do you know anything other algorithms that could be of use for me to pull this through ? I am really very worried... Could you help ?

Thank you very much...

Regards,
Nina.