Word Sequence

A Microsoft Coding Competition Problem

Posted by Matthew Roach on October 14, 2016

Halfway through the Microsoft Coding Competition Problems! This is the fourth problem and the first 2-point problem of the ones I've completed. Let's get into it.

The Problem

Your friends are playing a game called "Word Sequence". In this game you are given a dictionary of words D and two words A and B (both words are in the dictionary), and you have to find the minimum number of changes needed to turn A into B.

A change is defined as replacing only one character from the current string with another, such that the new string is also in D.

Let's first consider D = [abc, abb, acc, ccc, bbb] and:
* abc -> abb (this is a valid single change).
* abc -> bbc -> bbb (this is NOT valid because bbc is NOT in `D`).
* abc -> ccc (this is NOT a valid change because there are two replacements in one change).

Your task is to write a program that can find the minimum number of changes required for a given set of (A,B) pairs.

Input definition

The first line of the input gives the number of the words in the dictionary L (2 <= L <= 100)and the number of queries to solve Q (1 <= Q <= 10). The next L lines each contain a single word in the dictionary. The dictionary can contain words of varying length. The final Q lines of input each contain an A and B pair to evaluate.

It is guaranteed that all of the given words in the input only contain lower case characters and that the maximum length of any word is 10 characters.

Output definition

For each query in the input, your output should contain a single line that has the minimum number of changes required to turn string A into B. If there is no possible solution print "-1" instead (without the quotes).

To add clarity, let's now consider the specific input file given on this page.

For the first query, the number of changes is 2 as you can transform 'abc' to 'acc' and then to 'ccc'.
For the second query, you can transform acc to ccc in 1 change.
For the third query, there is no way to transform abc to bbb; therefore, the output is -1.

Example input

5 3
abc ccc
acc ccc
abc bbb

Example output


The Solution

I'm going to keep the solution to this problem short and sweet, so if you have comments leave them below. To solve this problem I have divided the work into the following functions:


This function takes a word as a parameter and returns a list of words that differ from the parameter by only one letter and that is also in the dictionary. It is used to hold a list of possible next moves.


This function finds the shortest path between two words. It takes a starting word(initial), an end word(goal), and the amount of steps to solve the problem in. The function returns the solution in the form of a list.


Pretty self explanatory... this function returns True or False if a word is in the dictionary.


This function returns the number of steps in a solution. After the sequence function has returned a list of words, this function returns the length - 1 of the list. Minus 1 because a sequence of three words requires two changes.

As you can see this code could be quite easily expanded to solve problems with a larger alphabet and dictionary.


Word Sequence
A Problem from Microsoft's Coding Competition

By: Matthew Roach
October 14, 2016

def oneLetterDiff(word):
    letterList = ['a','b','c']
    wordList = []
    index1 = 0
    index2 = 1
    while index2 != len(word)+1:
        for i in letterList:
            newWord = word[0:index1]+i+word[index2:]
            #If the new word is in the dictionary and is 
			#not the parameter add it to the word list.
            if lookup(word) == True and newWord != word:
                if lookup(newWord) == True:
        index1 += 1
        index2 += 1
    return wordList

def sequence(initial, goal, steps):
    if steps < 0:
        return None
    if steps == 0 and initial != goal:
        return None
    if initial == goal:
        return [initial]
    #loop through list of one letter differences 
    for i in oneLetterDiff(initial):    
        wordPath = sequence(i,goal,steps-1)
        if wordPath != None:
            return [initial] + wordPath
def lookup(word):
    return word in D

def sizeOfSolution(lis):
    if lis == None:
        return -1
        return len(lis) - 1
D = dict()
#p4.txt is the input file
with open('p4.txt') as infile:
    for line in infile:
        data.append(line.strip().split(' '))
    L = int(data[0][0]) #L = # of words in dictionary 
    Q = int(data[0][1]) #Q = # of problems to solve
    words = []
    for i in range(1,L+1):
    for word in words:
        D[word] = None

    for i in range(L + 1, L + Q + 1):
        initial = str(data[i][0])
        goal = str(data[i][1])

        #Steps (third param.) is set to the length of 
		#initial/goal because it is the max number of 
		#steps for an N letter word
        N = len(initial)
        sol = sequence(initial, goal, N)
        print sizeOfSolution(sol)