1. 6 points Implement a program to play the word Ladser gamt by completing the f
ID: 3820748 • Letter: 1
Question
1. 6 points Implement a program to play the word Ladser gamt by completing the functions in wordLaddorstartry.oNote: you'll also need these files basicgraphugy.bfsigy, and quesuel210upy since wordLadderStart 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 adom 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: wordsStest.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 corre graph. The graph will have one vertex for cach word, and an edge between nodes whose words differ in exactly letter sponding After building the graph, the program should enter a loop that repeatedly asks the user to provide start and end words. and finds (f 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. Modif your algorithm to try to find long word ladders rather than short ones, Eg. can you find a ladder from black try this that's longerthan steps? Longer than 6 seep? Hint even just "wiching the graph traversal algorithm from bf's to dfs often gives you fairly long ladders it's supereasy toExplanation / Answer
main.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):
wl = []
x = endNode
while x.getParent() and x != startNode:
wl.insert(0, x.getName())
x = x.getParent()
wl.insert(0, x.getName())
return wl
# 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):
counter = 0
for a in word1:
for b in word2:
if a == b:
counter += 1
if word2.index(b) + 1 != len(word2):
word2 = word2[:word2.index(b)] + word2[word2.index(b)+1:]
else:
word2 = word2[:word2.index(b)]
break
if counter < 4:
return False
else:
return True
# return word ladder graph for the given file of five-letter words
#
def buildWordGraph(wordsFile="words5.text"):
d = {}
g = Graph()
wfile = open(wordsFile, 'r')
# create buckets of words that differ by one letter
for line in wfile:
word = line[:-1]
for i in range(len(word)):
if word not in g.nodes:
g.addNode(Node(word))
bucket = word[:i] + '_' + word[i + 1:]
if bucket in d:
d[bucket].append(word)
else:
d[bucket] = [word]
# add vertices and edges for words in the same bucket
for bucket in d.keys():
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2:
if not g.hasEdge(g.getNode(word1), g.getNode(word2)):
g.addEdge(g.getNode(word1), g.getNode(word2))
return g # return list of words representing word ladder from startNode to endWord in wordGraph
#
def findWordLadder(startWord, endWord, wordGraph):
bfs(wordGraph, wordGraph.getNode(startWord))
wl = extractWordLadder(wordGraph.getNode(startWord), wordGraph.getNode(endWord))
return wl
# play the word ladder game using the given file of words
#
def wordLadder(wordsFile="words5.text"):
g = buildWordGraph(wordsFile)
while True:
startWord = input("Enter a start word:")
endWord = input("Enter an end word:")
wl = findWordLadder(startWord, endWord, g)
if wl[0] != startWord:
print("No such sequence exists.")
else:
print(wl)
return
if __name__ == '__main__':
wordLadder()
basicgraph.py
# Class to represent nodes (vertices) of a graph
#
class Node(object):
# name must be a string
def __init__(self, name):
self.parent = None
self.name = name
self.status = 'unseen'
def getName(self):
return self.name
def getStatus(self):
return self.status
def getParent(self):
return self.parent
def setParent(self, parentNode):
self.parent = parentNode
# 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
#
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
bfs.py
from queue1210 import *
from basicgraph import *
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')
node.setParent(currentNode)
queue.enqueue(node)
currentNode.setStatus('processed')
queue1210.py
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]
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()))
print(q.dequeue())
print("Size is now: {}".format(q.size()))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.