This is Python You are to implement the Word Ladder problem. Step 1) Create an u

Question

This is Python

You are to implement the Word Ladder problem.  

Step 1) Create an undirected graph for the Word List shown in Figure 1. You need to use a Python dictionary Figure 1. Word List

Step 2) Modify bfs() function in allow the user to enter 'startWord' and 'endWord'. The function should return 'True' if a transformation sequence exists. Return 'False' if there is no such transformation sequence. Notice that you don't need to find the number of transformations. It searches the tree using BFS algorithm to see if a transformation sequence exists.

Sample run C:Users estDesktop>hw11.py enter startWord : hot enter endtWord : dog True C:Users estDesktop>hw11.py enter startWord : hot enter endtWord : cog True C:Users estDesktop>hw11.py enter startWord : hit enter endtWord : ddd False

Explanation / Answer

CODE : MAIN.PY

from collections import defaultdict
from collections import deque
from itertools import product
import os
import sys

def build_graph(words):
    buckets = defaultdict(list)
    graph = defaultdict(set)

    for word in words:
        for i in range(len(word)):
            bucket = '{}_{}'.format(word[:i], word[i + 1:])
            buckets[bucket].append(word)

    # add vertices and edges for words in the same bucket
    for bucket, mutual_neighbors in buckets.items():
        for word1, word2 in product(mutual_neighbors, repeat=2):
            if word1 != word2:
                graph[word1].add(word2)
                graph[word2].add(word1)

    return graph

#def get_words(vocabulary_file):
#    for line in open(vocabulary_file, 'r'):
#        yield line[:-1] # remove newline character

def get_words():
       wordList = ["FOOL","FOOD","FOLD","SOLD","SOLE","SALE","SAGE","CAGE"]
       for word in wordList:
            yield word

def traverse(graph, starting_vertex):
    visited = set()
    queue = deque([[starting_vertex]])
    while queue:
        path = queue.popleft()
        vertex = path[-1]
        yield vertex, path
        for neighbor in graph[vertex] - visited:
            visited.add(neighbor)
            queue.append(path + [neighbor])

def bfs(word_graph,word1,word2):
    for vertex, path in traverse(word_graph, word1):
        if vertex == word2:
            print ' -> '.join(path)
            return True
    
    return False
        
    
            # FOOL -> FOOD -> FOLD -> SOLD -> SOLE -> SALE -> SAGE

if __name__ == '__main__':
    #print "This is the name of the script: ", sys.argv[0]
    #print "Number of arguments: ", len(sys.argv)
    #print "The arguments are: " , str(sys.argv)
    if len(sys.argv) < 3:
        print("Please provide two words to search in command line")
    else:
        word1 = sys.argv[1]
        word2 = sys.argv[2]
        print(' building graph ..')
        word_graph = build_graph(get_words())
        print ' initiating bfs search for ', word1, ' and ', word2
        status=bfs(word_graph, word1, word2)
        print ' .. BFS SEARCH RESULT :' , status

OUTPUT :

0
>>> import os
>>> os.system('python main.py')
Please provide two words to search in command line
0
>>> os.system('python main.py FOOL')
Please provide two words to search in command line
0
>>> os.system('python main.py FOOL CAGE')
building graph ..
initiating bfs search for FOOL and CAGE
FOOL -> FOOD -> FOLD -> SOLD -> SOLE -> SALE -> SAGE -> CAGE
.. BFS SEARCH RESULT : True
0
>>> os.system('python main.py FOOT CAGE')
building graph ..
initiating bfs search for FOOT and CAGE
.. BFS SEARCH RESULT : False
0
>>> os.system('python main.py FOOL SOLD')
building graph ..
initiating bfs search for FOOL and SOLD
FOOL -> FOOD -> FOLD -> SOLD
.. BFS SEARCH RESULT : True
0
>>>

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.