Hamming Distance using a dictionary

Question

First time poster. I'm currently programming a hamming distance program using a dictionary.

So if we start with the word "cat" and we want to transform it into "dog", the sequence is cat-->cot-->dot-->dog, and "full" to "tree" is full-->fuel-->feel-->teel-->tyee-->tree. All intermediates must exist in a dictionary. I've implemented that part and it works quite well. My question is about the fringe cases. Some words have no transformations, such as dragon and cosmo. But that's fine, I implemented a quick check.

The real problem is there are lots of paths in which transformations are impossible and I can't seem to find a way to check whether they are impossible. For example, heist to flame is heist-->feist-->feast-->feaseX --> flame. Getting to the end point is impossible and an infinite loop occurs.

My possible options are that after around 20 transformations, I stop the calculation and throw an error, which is fine. Or, there might be way to detect a dead path before the program is ran, this is the best option, I'm not optimistic this is possible.

Answer 1

You can solve this with a standard breadth-first search, with the addition of also storing the path taken to a node whenever you enqueue it in the to search queue. BFS algorithms avoid loops by keeping a visited or discovered set. Because they use a queue instead of a stack, they are not normally implemented using recursion, unless the implementation uses immutable data structures.

If you reach a point in the algorithm where you have nothing remaining in the to search queue, you know there is no possible path. Note at this point, the visited set contains all the nodes reachable from the given starting point. You can take advantage of that to precalculate and store all the sets of connected words, by just skipping the part where you check if you reached the goal word. However, it's simpler and may often work out faster to just run the BFS.

Answer 2

It seems that what you're really trying to do is figure out if two nodes in a graph are in the same connected component. Specifically the graph is an undirected one in which the words of your dictionary are nodes, and two nodes are connected to each other by a vertex when they differ by exactly one letter, and are the same length. The root of the problem is that this graph is not be totally connected. It may be a disconnected graph of mutually unreachable connected components. In fact, it seems from your description that any words with a different number of letters would have to be in separate components.

The italicized keywords above are too technical to explain completely in an answer here, but you will find them on Wikipeida, or in any computer science text that covers graph algorithms. The algorithms you should consider for solving your problem are reachability algorithms for disconnected, undirected graphs.

Answer 3

To solve the question you pose, you must understand complete search, and for that you have to understand recursive algorithms. This simply means that you must reduce e.g. the problem of reaching "tree" from "full" to the problem of reaching "free" from "full", and handle the intermediate data correctly.

Answer 4

I assume you are using recursion for this. Every transformation is a unit of work to be done, hopefully it is handled in one method, or group of methods.

When you jump to next word, keep track of all the words that you have already been at during this specific path and check the available options against the list of those words to exclude the ones that you already visited.

Example:

heist-(1)->feist-(2)->feast-(3)->feaseX -(4)-> flame

* Numbers signify the execution cycle of the same method. Simplified version for demonstration purposes.

public string[] previouslyUsedWords = new String[]();

public string transformNext(string currentWord) {
    var possibleOptions = _optionsProvider.GetOptions(currentWord);

    foreach(var word in possibleOptions) {
        if(!previouslyUsedWords.Contains(word)) {
            previouslyUsedWords.Add(word);
            return word;
        }
    }

    throw new Exception("No options left, this is a dead end!");
}

Combine this with a tree-traversal algorithm(some paths are dead ends and that's why you need to go back and try other paths) and you should accomplish this task in no time.

Answer 5

I think you should probably use a union-find algorithm to find all connected groups of n-letter words that can transform into each other. Preprocess you dictionary with it, and before you start searching see if the two end words are in the same connected group. The preprocessing will only take time proportional to the number of valid word-to-word transitions, so you could get away with doing it every time you load your dictionary. You would need to store the group id of every word, so that would take a little more space.