a4_2.py

from __future__ import print_function

def check_all_words():
	# Read the dictionary of all words
	f = open("words.txt")
	dictionary = set()
	for line in f:
		dictionary.add(line.strip())
	f.close()
	# Add some missing words in dictionary
	dictionary.add("a")
	dictionary.add("i")
	dictionary.add("")

	# Initialize variables tracking the longest reducible word(s)
	# that we have seen.
	bestWords = []
	bestLength = 0

	# Initialize cache of all reducible words we have seen.
	# The cache (memo) enables us to check each word for
	# reducibility at most once.  This makes the program
	# run faster (fewer checks) at the expense of using more
	# memory (words stored in cache).
	memo = {}
	for word in dictionary:
		# For more efficiency, we should check the words
		# sorted by length, so that the first reducible
		# word is also the longest.

		# If the word is shorter than our best, we do not
		# even bother to check it since it cannot be
		# the word we are looking for.
		if len(word) < bestLength:
			continue

		# If this word is reducible, it must be at least
		# as long as our current best.  If it is the same
		# length, we add it to the "bestWords" list.  If
		# it is longer, we clear out "bestWords" and start
		# over, updating "bestLength" at the same time.
		if reducible(word, dictionary, memo):
			if len(word) > bestLength:
				#print("new best word", word)
				bestLength = len(word)
				bestWords = [ word ]
			elif len(word) == bestLength:
				#print("equal best word", word)
				bestWords.append(word)

	# After looking at all words in the dictionary, print out
	# the results we saved.
	print("Longest reducible word has", bestLength, "characters")
	print("They are:")
	for word in bestWords:
		print_trail(word, memo)
		print()

def reducible(word, dictionary, memo):
	"""Return whether the given "word" is reducible."""

	# Recursion termination condition: either all the letters
	# have been removed, or we have already seen this word and
	# know that it is reducible.
	if len(word) == 0 or word in memo:
		return True

	# Loop through all possible subwords and check whether any
	# of them is reducible.  Because we only need to find one
	# reducible subword, we can return immediately when we do
	# find one.
	# "memo" is the cache where we store the set of reducible
	# words that we have seen.  When we know that "word" is
	# reducible, we add it into the cache.  Note that we do not
	# need to do so for subwords since it will have been added
	# already by the calls to "reducible" with the subwords.
	for subword in shorten(word):
		if subword not in dictionary:
			continue
		if reducible(subword, dictionary, memo):
			memo[word] = True
			return True
	return False

def shorten(word):
	"""Return the set of strings one character shorter than "word"."""

	return set([ word[:i] + word[i + 1:] for i in range(len(word)) ])
	# Above statement is the "list comprehension" version of:
	#
	# words = []
	# for i in range(len(word)):
	# 	words.append(word[:i] + word[i + 1:])
	# return set(words)
	#
	# Of course, we can directly create the set:
	#
	# words = set()
	# for i in range(len(word)):
	# 	words.add(word[:i] + word[i + 1:])
	# return words

def print_trail(word, memo):
	"""Print trail of subwords that make "word" reducible."""

	# Note that "print_trail" is also recursive.
	# We use the memo cache that we built to find a reducible
	# subword and print its trail.

	# Recursion termination condition
	if len(word) == 0:
		return
	print(word, end=' ')
	for subword in shorten(word):
		if subword in memo:
			# Recurse for good subword
			print_trail(subword, memo)
			# We only need one trail, so we can immediately
			# return after printing one.
			return

check_all_words()