[Use Wagner-Fischer algorithm to find aloof words] #algorithms #python3

Aloof.py

#!/usr/bin/python3
# Aloof.py
# Created by Matthew Cole on 3/1/15.

"""
A word is ALOOF if and only if it has no words which differ from it by only one letter.
"""

def LDistance(str1, str2):
	"""
	Uses the Wagner-Fischer algorithm for computing edit distance.
	Has efficient run time but inefficient space usage for large strings.
	INPUT: strings str1 and str2 - two strings to be compared, with length m and n respectively
	#OUTPUT: integer ld - the Levenshtein distance between str1 and str2
	"""
		
	m = len(str1)
	n = len(str2)
		
	#Build table d, initialize with 0 values
	d = list()
	d = [[0 for x in range(0,m+1)] for x in range(0,n+1)]
		
	#Fill source prefixes
	for i in range(0,m+1):
		d[0][i] = i
		
	#Fill target prefixes
	for j in range(0,n+1):
		d[j][0] = j

	#Calculate ld at table position[i][j]
	for j in range(1,n+1):
		for i in range(1,m+1):
			#If characters match at each position, no operation is required
			if str1[i-1] == str2[j-1]:
				d[j][i] = d[j-1][i-1]
			#Otherwise, calculate minimum cost for each operation
			else:
				d[j][i] = min(
				d[j][i-1] + 1,	#deletion
				d[j-1][i] + 1,	#insertion
				d[j-1][i-1] + 1	#substitution
				)
			#DEBUG: show final table
			#for row in d:
			#	print(row)
			#print()
				
	#Return Levenshtein Distance
	return(d[n][m])

def LDSet(word, wordset, ld=1):
	"""
	Returns a subset of words from wordset with a given Levenshtein Distance to a given word.
	INPUT: <word>, a string. <wordset> an iterable of all words in a superset, <ld>, an integer length.
	OUTPUT: a subset of <wordset> with a specified LD.
	"""
	return set(word2 for word2 in wordset if LDistance(word, word2) == ld and word != word2)

def AloofOutputs(word, wordlist):
	"""
	Checks an aloof word-guess.
	"""
	#Build a set from the fetched dictionary
	words = set(word for word in wordlist if len(word)==len(guess))
	
	#Check for aloofness
	for guess in guesses:
		#Reject made-up words
		if guess not in words:
			print("Guess: %s." %guess, "Word not in dictionary.")
		#Print the results of the guess
		else:
			neighbors = set(w for w in LDSet(guess, words) if len(w) == len(guess))
			if neighbors == set():
				print("Guess: %s." %guess, "Aloof!")
			else:
				print("Guess: %s." %guess, "Not aloof. Neighbors: %s " % " ".join(neighbors))

#Build a text file header.
print("Content-type: text/plain")
print()

#Fetch a dictionary
from urllib.request import Request, urlopen
from urllib.error import  URLError
req = Request('http://www.puzzlers.org/pub/wordlists/web2.txt')

try:
	response = urlopen(req)
	wordlist = set(word.decode("utf-8").lower() for word in response.readlines())
	print("Loaded the dictionary.")
except HTTPError as e:
	print('The dictionary server couldn\'t fulfill the request.')
	print('Error code: ', e.code)
except URLError as e:
	print('Couldn\'t reach the dictionary server.')
	print('Reason: ', e.reason)
except Exception as e:
	print('Something else went wrong.')
	print('Message: ', e)

#Get CGI field data
from string import whitespace
from cgi import FieldStorage
import cgitb
params = FieldStorage()

#Process the word guess,
#Or create a form to receive a word guess
if 'word' in params:
	word = params.getvalue('word')
	AloofOutputs(word, wordlist)
else:
	print("I didn't receive a word to check.")