Answer To: a aah aahed aahing aahs aardvark aardvarks aardwolf ab abaci aback abacus abacuses abaft abalone...
Sandeep Kumar answered on May 03 2021
word changes.py
import sys
class Graph:
def __init__(self):
self.vertices = {}
self.numVertices = 0
def addVertex(self, key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertices[key] = newVertex
return newVertex
def getVertex(self, n):
if n in self.vertices:
return self.vertices[n]
else:
return None
def __contains__(self, n):
return n in self.vertices
def addEdge(self, f, t, cost=0):
if f not in self.vertices:
nv = self.addVertex(f)
if t not in self.vertices:
nv = self.addVertex(t)
self.vertices[f].addNeighbor(self.vertices[t], cost)
def getVertices(self):
return list(self.vertices.keys())
def __iter__(self):
return iter(self.vertices.values())
class Vertex:
__slots__ = 'id', 'connectedTo', 'color', 'dist', 'pred', 'disc', 'fin'
def __init__(self, num):
self.id = num
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0
def addNeighbor(self, nbr, weight=0):
self.connectedTo[nbr] = weight
def setColor(self, color):
self.color = color
def setDistance(self, d):
self.dist = d
def setPred(self, p):
self.pred = p
def setDiscovery(self, dtime):
self.disc = dtime
def setFinish(self, ftime):
self.fin = ftime
def getFinish(self):
return self.fin
def getDiscovery(self):
return self.disc
def getPred(self):
return self.pred
def getDistance(self):
return self.dist
def getColor(self):
return self.color
def getConnections(self):
return self.connectedTo.keys()
def getWeight(self, nbr):
return self.connectedTo[nbr]
def __str__(self):
return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(
self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred) + "]\n"
def getId(self):
return self.id
def buildGraph(file):
"""
Creates buckets for each word that differs by one letter
Adds edges to graph from completed buckets
:param wordFile: Dictionary filename
:return: Completed graph
"""
dict = {}
graph = Graph()
wfile = open(file,'r')
for line in wfile:
word = line[:-1]
for i in range(len(word)):
bucket = word[:i] + '_' + word[i+1:]
if bucket in dict:
dict[bucket].append(word)
else:
dict[bucket] = [word]
for bucket in dict.keys():
for word1 in dict[bucket]:
for word2 in dict[bucket]:
if word1 != word2:
graph.addEdge(word1,word2)
return graph
def BFS(start, end):
"""
Traditional BFS using a list as a queue
Searches through all neighbors to build path to target word if one exists
:param start: starting word
:param end: target word
:return: path to target or None
"""
queue = []
queue.append(start)
predecessors = {}
predecessors[start] = None
while len(queue):
current = queue.pop(0)
if current == end:
break
for neighbor in current.getConnections():
if neighbor not in predecessors:
predecessors[neighbor] = current
queue.append(neighbor)
if end in predecessors:
path = []
current = end
while current != start:
path.insert(0, current)
current = predecessors[current]
path.insert(0, start)
return path
else:
return None
def main():
assert len(sys.argv) > 1, 'Usage: length of argv must be > 1'
wordFile = 'words.txt'
g = buildGraph(wordFile)
start = g.getVertex(sys.argv[1])
end = g.getVertex(sys.argv[2])
paths = []
paths.append(BFS(start, end))
paths.append(BFS(g.getVertex('drool'), g.getVertex('drone')))
paths.append(BFS(g.getVertex('brush'), g.getVertex('broke')))
for current in paths:
print('Path: ')
if current is None:
print('No path to word was found.')
else:
for vertex in current:
print(vertex.id)
print()
if __name__ == '__main__':
...