Feature #1: Minimum Moves

Description

The first functionality we need to build will find the minimum number of conversions needed to transform the initial word into the final word. Both of these words will be of the same length.

We’ll be provided with an initial word, a final word, and a word group in the form of a list. Our code needs to pick the shortest sequence of words of the same length from the word group, starting with the initial word and ending at the final word. This sequence should be such that each consecutive word differs from the previous one in one letter only.

Here is an illustration of this process:

Solution

BFS (Breadth-First Search) is known to optimally find the shortest path in an unweighted graph. Before we can apply BFS, we need to build the graph. Additionally, we have to find adjacent nodes in which the corresponding words only differ by one letter. This requires some preprocessing steps.

Using the above example, the word let can have three intermediary states:

1. let -> _et

2. let -> l_t

3. let -> le_

The second state can be mapped to the words lot, lit, etc., because they share the same intermediary state of l_t. Hence, let can have lot and lit as neighboring or adjacent nodes.

Here is how we will implement this feature:

1. Perform the preprocessing steps for each word in our dictionary to find all its intermediary states. Then, create a dictionary statesList. Save these intermediary states as the key and the words that correspond to each state as a list of values.

2. Create a tuple containing the initial word and 0 as (initialWord, 0). The initial word will be the root node at which the BFS will begin, and our root node will always be at level 0. We need to return the level of the final node as that would be the shortest distance from the initial word. Next, push this tuple into a queue.

3. To prevent cycles, we’ll use a dictionary to maintain visited nodes.

4. We will retrieve the latest word from the queue until it’s empty. For each word, say currentWord, check the statesList dictionary and do the following:

   • Find all the word’s intermediary states.

   • For each state found in the above step, check if it is also a state for any other word present in the initial word dictionary.

5. The list of words we obtain from the above step will be the same for the currentWord. All the words on the list will be considered adjacent nodes to the currentWord and, therefore, will be added to our queue.

6. For each new word in the nodes adjacent to the currentWord, compute the tuple (word, level + 1), where level is the level of the currentWord and incrementing this by 1 introduces a new layer on which BFS will run. Append this new tuple into our queue.

7. If the final word is found, the value of level ...