Longest Word Chain

longest_word_chain.py

import string
 
f = open("/usr/share/dict/words")
word_list = set(f.read().split('\n'))
 
def is_word(word):
    return word in word_list
 
candidates_checked = 0
def longest_word_chain(starting_word='', min_length=1):
	""" Ever have someone add one letter to your scrabble word to make
	a new valid word? The asshole that makes points off your hard work?
	This function finds the longest word that you can possibly create by adding
	one letter at a time, where each concatentation would still be a valid word.
 
	@starting_word: the base word we start adding letters to
	@min_length: normally, our dictionary would throw away words like "ea". This
		param sets a min length before our dictionary throws possible words away.
 
	>>> longest_word_chain()
	(8, set(['sheathes', 'prelates', 'flashest', 'relapsed', 'browsers', 'sheathed', 'relapses', 'brashest']))
	>>> longest_word_chain(min_length=2)
	(9, set(['cleansers']))
	>>> longest_word_chain(starting_word='lap')
	(8, set(['relapsed', 'relapses']))
	"""
	global candidates_checked
	candidates_checked += 1
 
	if len(starting_word) > min_length:
		if not is_word(starting_word):
			return 0, set()
 
	prefix_candidates = [(l + starting_word) for l in string.ascii_lowercase]
	suffix_candidates = [(starting_word + l) for l in string.ascii_lowercase]
	candidates = prefix_candidates + suffix_candidates
 
	longest_length = len(starting_word)
	longest_words = set([starting_word])
 
	for candidate in candidates:
		length, words = longest_word_chain(candidate, min_length=min_length)
		if length > longest_length:
			longest_length = length
			longest_words = words
 
		if length == longest_length:
			longest_words |= words
 
	return longest_length, longest_words
 
print longest_word_chain()
print "Checked %s possible words" % candidates_checked