Answer To: #!/usr/bin/python3 # Alberto Maria Segre # Based on code provided by Sriram Pemmaraju # Word ladder...
Sandeep Kumar answered on May 07 2021
wordnet.py
#!/usr/bin/python3
# Alberto Maria Segre
# Based on code provided by Sriram Pemmaraju
# Word ladder problem. Uses a dictionary representation of the word
# network and returns the path discovered. Try, e.g., abode/above and
# abode/abort.
from random import randint
# areNeighbors(w1, w2) returns True if the two words given as
# arguments differ in exactly one letter position. Note that this
# function assumes that w1 and w2 are equal length, a condition that
# is met in the context of this assignment.
def areNeighbors(w1, w2):
'''Returns True if w1 and w2 differ in exactly one letter.'''
# Step through words and count mismatched characters. Note early
# termination clause to speed things up just a bit.
count = 0
for i in range(len(w1)):
if w1[i] != w2[i]:
if count == 1:
return(False) # Fail, early termination.
count = count + 1
# Return True if and only if exactly one difference was
# discovered.
return(count == 1)
# readWords(filename) opens the specified file and reads in each line,
# where each line is assumed to contain a single word. After stripping
# whitespace, the words are returned in a list.
def readWords(filename = 'words.dat'):
'''Reads in a file consisting of one word per line; returns list of words.'''
# Open the words.dat file for read.
infile = open(filename, 'r')
# Read in the file and split by whitespace (includes \n).
W = infile.read().split()
# Clean up after yourself.
infile.close()
# Print some useful statistics and return the word list.
print('{} words read.'.format(len(W)))
return(W)
# makeNetwork(wordlist) returns a dictionary representation of the
# word network. The resulting dictionary keys are the elements of
# wordList, and the values are lists of neighbors to that key.
def makeNetwork(wordlist):
'''Returns a dictionary of lists, corresponding to the neighbors
of the key words from wordlist.'''
# Initialize edge count and dictionary.
edges = 0
network = { w:[] for w in wordlist }
# Doubly-nested for loop ensures every pair of words is considered
# exactly once. Note how j relates to i.
for i in range(len(wordlist)):
for j in range(i+1, len(wordlist)):
if areNeighbors(wordlist[i], wordlist[j]):
network[wordlist[i]].append(wordlist[j])
network[wordlist[j]].append(wordlist[i])
edges = edges+1
# Print some useful statistics and return the network.
print('{} words and {} edges in network.'.format(len(wordlist), edges))
return(network)
# findNeighbors(word, network) returns the neighbors of the given
# word.
def findNeighbors (word, network):
'''Returns neighbors of word from network'''
return(network[word])
# Explores the network of starting at src. If the exploration ends
# without reaching dst, then there is no path between the src and dst.
# In this case the function returns an empty list. Otherwise, there is
# a path and the function returns the path from src to dst (a list).
def searchNetwork(src, dst, network):
'''Explore the network from src to dst; return path if found.'''
# Start from dst walk backwards to src by tracing explored. This
# is a private function, usable only from within searchNetwork()/
def findPath(src, dst, explored):
'''Reconstruct path from src to dst.'''
# We'll rebuild the path backwards from dst to src.
path = [dst]
# Walk backwards by tracking the parent pointer in explored.
while dst != src:
# Reset dst to its parent.
dst = explored[dst]
path.append(dst)
# Reverse the path so its presented from src->dst.
path.reverse()
return(path)
# Initialization: pending and explored are dictionaries that will
# help in the exploration. The first, pending, contains all
# neighbors reached in the course of the search (key) along with
# the identity of the node that added them to pending (value). The
# second, explored, contains all reached words (key) whose
# neighbors have also been reached, along with the id of the
# neighbor that added them to pending.
pending = {src:None}
explored = {}
# Repeat until reached set becomes empty or dst is reached
count = 0
while pending:
# Check if dst is in pending; if so, you're done.
if dst in pending:
# Make sure the last hop is in explored.
explored.update({dst:pending[dst]})
# Some more status information.
print('{} nodes explored.'.format(count))
# Reconstruct the path and return it.
return (findPath(src, dst, explored))
# Pick an item in reached and process it; recall itm[0] is the
# node and itm[1] is its parent.
itm = pending.popitem() # returns an arbitrary key-value pair as a tuple
explored[itm[0]] = itm[1]
# Add some trace information.
count = count + 1
#print('Exploring {} ({}:{}).'.format(itm, len(pending), len(explored)))
# Add all neighbors of itm to pending if not already
# explored. Here, we need the explicit check of pending since
# we are comparing only keys, and don't wish to replace the
# value willy nilly when a node is encountered once again.
for n in findNeighbors(itm[0], network):
if n not in explored and n not in pending:
pending[n] = itm[0]
# Terminated while loop without finding a match.
print('{} nodes explored.'.format(count))
return ([])
# Play the game, prompting the user for src and dst words.
def wordladder(filename = 'words.dat'):
'''Play the word ladder game. Repeatedly prompts the user for a word ladder problem
and prints out each ladder found.'''
# Read in the wordlist.
W = readWords(filename)
# Create the word network.
N = makeNetwork(W)
# Play the game.
while True:
# Prompt user for source word.
src = input('Source word (q to quit, r for random)? ')
# Check for user exit or unknown source word.
if src == 'q':
print('Done.')
return
elif src == 'r':
src = W[randint(0,len(W)-1)]
print('The source word is {}'.format(src))
elif src not in W:
continue
# Prompt user for destination word; keep trying until you get
# a legal destination word that differs from the source word.
dst = ''
while dst not in W or src==dst:
dst = input('Destination word (r for random)? ')
if dst == 'r':
dst = W[randint(0,len(W)-1)]
print('The destination word is {}'.format(dst))
# Solve word search. Print output and repeat.
path = searchNetwork(src, dst, N)
if path:
for w in path:
print(' {}'.format(w))
print('{} words in ladder\n'.format(len(path)))
else:
print('No ladder found from {} to {}.\n'.format(src, dst))
# This will be executed when the code is invoked from the command line.
if __name__ == '__main__':
...