2009 108

def makewordlist ():
	ret = []
	for line in open("words.txt"):
		word = line.strip()
		ret.append(word)
	return ret

allwords = makewordlist()

# find word pairs
# FOR EVERY WORD
# FLIP THE WORD
# CHECK IF FLIPPED WORD IS IN WORDLIST

def find_bisect (wordlist, seekword):
	bot = 0
	top = len(wordlist)
	count = 0
	lastword = None
	while True:
		count += 1
		mid = bot + ((top - bot) / 2)
		curword = wordlist[mid]
		#print "checking item[", mid, "] = ", curword
		if (curword == seekword):
			#print "found in", count, "iterations"
			return True
		elif (curword < seekword):
			bot = mid
		else:
			top = mid
		
		if curword == lastword:
			return False
		lastword = wordlist[mid]
	
	# if you're checking what you just checked,
	# time to stop
	
	# if it takes more than 18 times stop


#word = "geeblosx"
#print word, find_bisect(allwords, word)
#word = "tomato"
#print word, find_bisect(allwords, word)


#import sys
#sys.exit()

for word in allwords:
	# flip the word
#	print "checking", word
	flip = word[::-1]
	# is flip a word
	# if flip in allwords:
	if find_bisect(allwords, flip):
		print "found a word pair", word, flip
	
	#for w in allwords:
##		print "  checking", w
		#if w == flip:
			#print "found a word pair", word, flip
			#break