(USING PYTHON) Implement a program to play the Word Ladder game by completing the functions in wordLadderStart.py. (Note: you'll also need these files: basicgraph.py, bfs.py, and queue1210.py since wordLadderStart.py imports them) Given a "start" word and "end" word, the Word Ladder game finds a sequence of intermediate words that transforms the start word to end word, with the condition that each word in the sequence differs in exactly one letter (at one position) from the prior and subsequent words. Thus, for "adore" and "scorn" a ladder is: adore adorn acorn scorn And, for "white" to "black" a ladder is: white whine shine swine swing sling cling clink blink blank black For "arise" to "sleep" the shortest ladder has 14 intermediate words! Can you find them? The wordLadder program takes one optional argument, the name of a text file containing the word list to be considered. You may assume all words in the dictionary are five letters long, all lower case. Each word appears on a separate line in the file. A test file with a few thousand five-letter words is here: words5.text. NOTE: Test your code first on a file with just a few words before running your program on words5.text; debugging will be easier! Your program should first read the word list and build a corresponding graph. The graph will have one vertex for each word, and an edge between nodes whose words differ in exactly letter at one position. After building the graph, the program should enter a loop that repeatedly asks the user to provide start and end words, and finds (if one exists) the shortest word ladder from the start word to the end word, printing the sequence of words found (or an appropriate message if no such sequence exists). Note: if you finish this early, here's something extra you can do for fun. Modify your algorithm to try to find long word ladders rather than short ones. E.g. can you find a ladder from black to white that's longer than 100 steps? Longer than 648 steps? (Hint: even just switching the graph traversal algorithm from bfs to dfs often gives you fairly long ladders - it's super easy to try this ...)

code from wordLadderStart.py:

from basicgraph import * from bfs import * # Assumption: breadth first search from startNode has already been executed # # Extract path from startNode to endNode (by working backwards from endNode), # returning it as a list e.g. for 'shell'/'spill' the result might be ['shell', 'spell', 'spill'] # if 'spell' is the parent of 'spill' and 'shell' is the parent of 'spell' # def extractWordLadder(startNode, endNode): return # return True if there should be an edge between nodes for word1 and word2 in the # word graph. Return False otherwise # def shouldHaveEdge(word1, word2): return # return word ladder graph for the given file of five-letter words # def buildWordGraph(wordsFile = "words5.text"): return # return list of words representing word ladder from startNode to endWord in wordGraph # def findWordLadder(startWord, endWord, wordGraph): # 1. do graph traversal starting from node for startWord # 2. extract word ladder from the graph return # play the word ladder game using the given file of words # def wordLadder(wordsFile = "words5.text"): # 1. build word graph for the given file of words # 2. user interaction loop: # repeatedly ask user to enter two words, and then find and print the word ladder for those words return 

code from basicgraph.py:

# Class to represent nodes (vertices) of a graph # class Node(object): # name must be a string def __init__(self, name): self.name = name self.status = 'unseen' def getName(self): return self.name def getStatus(self): return self.status # should be one of 'unseen', 'seen', 'processed' def setStatus(self, status): self.status = status def __repr__(self): return "<{}>".format(self.name) # Class for representing undirected graphs, i.e. graphs in which edges # have no direction - if there is an edge between a and b, # you can "move" from a to b and/or from b to a # class Graph(): #nodes is a list of the nodes in the graph # # edges is a list of two-tuples (n1, n2). If there is an edge between n1 and n2, either (n1, n2) # or (n2, n1) will be in the list of edges # # adjacencyLists is a dictionary with the set of nodes as the set of keys. For each node, n1, # adjacencyLists[n1] is a list of the nodes n2 such that (n1,n2) is an edge. # i.e. it is a list of all nodes to which n1 is connected directly by an edge. # def __init__(self): self.nodes = [] self.edges = [] self.adjacencyLists = {} def addNode(self, node): if node in self.nodes: raise ValueError("node is already in graph. You can't add it again.") else: self.nodes.append(node) self.adjacencyLists[node] = [] # To add an edge between node1 and node2, node1 and node2 must already be in the graph def addEdge(self, node1, node2): if node1 == node2: raise ValueError("edges to self are not allowed in undirected graphs") if not((node1 in self.nodes) and (node2 in self.nodes)): raise ValueError("at least one node of given edge is not in the graph") if node2 in self.adjacencyLists[node1]: raise ValueError("edge is already in graph. You can't add it again.") self.edges.append((node1, node2)) self.adjacencyLists[node1].append(node2) self.adjacencyLists[node2].append(node1) def neighborsOf(self, node): return self.adjacencyLists[node] def getNode(self, name): for node in self.nodes: if node.getName() == name: return node return None def hasNode(self, node): return node in self.nodes def hasEdge(self, node1, node2): return node2 in self.adjacencyLists[node1] def __repr__(self): result = "[Graph with: Nodes:" for node in self.nodes: result = result + " " + str(node) result = result + " Edges: " result = result + ', '.join([(edge[0].getName() + '-' + edge[1].getName()) for edge in self.edges]) + ']' return result def genGraph(): n1 = Node("NYC") n2 = Node("Miami") g = Graph() print(g) g.addNode(n1) g.addNode(n2) print(g) g.addEdge(n1, n2) print(g) return g def genCompleteGraph(n): nodes = [] g = Graph() for i in range(n): g.addNode(Node(str(i))) nodes = g.nodes for n1 in nodes: for n2 in nodes: if (n1 != n2) and (not g.hasEdge(n1, n2)): g.addEdge(n1,n2) return g import random # return a new list with the same elements as input L but randomly rearranged def mixup(L): newL = L[:] length = len(L) for i in range(length): newIndex = random.randint(i,length-1) newL[newIndex], newL[i] = newL[i], newL[newIndex] return(newL) def genRandomGraph(numNodes, numEdges): nodes = [] edges = [] g = Graph() for i in range(numNodes): g.addNode(Node(str(i))) allPairs = [] for i in range(numNodes): for j in range(i+1, numNodes): allPairs.append((str(i),str(j))) allPairs = mixup(allPairs) edgesAdded = 0 while edgesAdded < min(numEdges, len(allPairs)): g.addEdge(g.getNode(allPairs[edgesAdded][0]), g.getNode(allPairs[edgesAdded][1])) edgesAdded = edgesAdded + 1 return g # graph used for bfs demo in class 4/10/17 # def genDemoGraph(): nodes = [Node("A"), Node("B"), Node("C"), Node("D"), Node("E"), Node("F"), Node("G"), Node("H")] edges = [(0,1), # A-B (0,2), # A-C (0,4), # A-E (0,7), # A-H (1,2), # B-C (1,3), # B-D (1,5), # B-F (2,5), # C-F (4,6), # E-G (6,7) # G-H ] g = Graph() for n in nodes: g.addNode(n) for e in edges: g.addEdge(nodes[e[0]], nodes[e[1]]) return g 

code from bfs.py

from queue1210 import * from basicgraph import * ##### # # classic Breadth First Search # # See, e.g., http://en.wikipedia.org/wiki/Breadth-first_search # def bfs(graph, startNode): for n in graph.nodes: n.setStatus('unseen') startNode.setStatus('seen') print("Initializing queue with: ", startNode.name) queue = Queue() queue.enqueue(startNode) while queue.size() != 0: print(queue) currentNode = queue.dequeue() print("removed {} from queue. Processing neighbors".format(currentNode.name)) for node in graph.neighborsOf(currentNode): if node.getStatus() == 'unseen': node.setStatus('seen') queue.enqueue(node) currentNode.setStatus('processed') 

code from queue1210:

class Queue: # We represent an empty queue using an empty list def __init__(self): self.q = [] # Return True if there are no items in the queue. Return False otherwise. def isEmpty(self): return (len(self.q) == 0) # Add an item to the rear of the queue. def enqueue (self, item): self.q.append(item) # If the queue is not empty, remove and return the queue's front item # If the queue is empty, generate an error or print(a message and return None. def dequeue (self): if self.isEmpty(): # students haven't been taught 'raise' so they can just print(error # message in the empty case. raise ValueError("dequeue invoked on empty Queue") else: result = self.q[0] # this is O(n), so use a different data structure if you will # do many dequeues on very big queue! (Use collections.deque) self.q = self.q[1:] return result # Return the number of items currently in the queue def size(self): return(len(self.q)) def __repr__(self): return "queue{front: " + str(self.q)[1:-1] + " :end}" def testQueue(): q = Queue() print("Created an empty Queue") print("Size is now: {}".format(q.size())) print("Enqueue-ing: 3, then 'hi', then 99") q.enqueue(3) q.enqueue("hi") q.enqueue(99) print("Size is now: {}".format(q.size())) print("Dequeue-ing ...") print(q.dequeue()) print("Size is now: {}".format(q.size())) print("Dequeue-ing ...") print(q.dequeue()) print("Size is now: {}".format(q.size())) print("Enqueue-ing: [1,2]") q.enqueue([1,2]) print("Size is now: {}".format(q.size())) print("Dequeue-ing ...") print(q.dequeue()) print("Size is now: {}".format(q.size())) print("Dequeue-ing ...") print(q.dequeue()) print("Size is now: {}".format(q.size()))