DICT = open('/users/jsomers/Documents/Work/Project Euler/TWL06.txt', 'r')
 WORDS = [a.strip() for a in DICT.readlines()]
 
 def board(string):
 	"Takes a string and builds a board, represented by a list of rows."
 
 	upper = string.upper()
 	raw = list(upper)
 
 	# handle a Q
 	try: 
 		i = raw.find('q')
 		raw[i] = 'qu'
 	except: pass
 
 	assert len(raw) == 16, 'Board must be 4x4!'
 
 
 	rows = [raw[i:i + 4] for i in range(0, len(raw), 4)]
 	return rows
 
 def pgroups(board):
 	""" Takes a board and returns, for each letter, a list of its peers.
 	We check all possible surrounding squares, and 'pass' when one would
 	be out of list index range.
 
 	"""
 
 	pgroups = []
 	for i, row in enumerate(board):
 		for j, col in enumerate(row):
 			# The i, j components in a node are for disambiguation, since 
 			# some puzzles have more than one 'A', for instance.
 			peers = [(col, i, j)]
 			checks = [(1, 0), (1, 1), (1, -1), (-1, 0), (-1, 1), (-1, -1),
 					 (0, -1), (0, 1)]
 			for c in checks:
 				try:
 					pr_i, pr_j = i + c[0], j + c[1]
 					if pr_i >= 0 and pr_j >= 0: # No wraparound
 						pr = board[pr_i][pr_j]
 						peers.append((pr, pr_i, pr_j))
 				except:
 					pass
 			pgroups.append(peers)
 	return pgroups
 
 def build_words(board, prefix, node, wordlist, nodepath, words):
 	""" This function does the heavy lifting. It takes a (prefix, node) combo
 	and tries to add letters to it by checking the node's peers. Recursion is
 	okay here since the search space shrinks quickly.
 
 	""" 
 
 	nodepath = nodepath[:len(prefix)] # Hack
 
 	peer_list = [p for p in pgroups(board) if p[0] == node][0]
 	pared_peer_list = [n for n in peer_list if n not in nodepath]
 
 	pared_wordlist = [i for i in wordlist if i.startswith(prefix)]
 
 	for peer in pared_peer_list[1:]: # Exclude self
 		l = peer[0]
 		new = prefix + l
 		if new in pared_wordlist:
 			words.append(new)
 
 		if [i for i in pared_wordlist if i.startswith(new)]:
 			nodepath.append(node)
 			build_words(board, new, peer, pared_wordlist, nodepath, words)
 
 	return words
 
 def length(a, b):
 	return cmp(len(a), len(b))
 
 def solve(string):
 	the_board = board(string)
 
 	words = []
 	for pgroup in pgroups(the_board):
 		node = pgroup[0]
 		words += build_words(the_board, node[0], node, WORDS, [], [])
 
 	solution = sorted([a for a in set(words) if len(a) > 2])
 	solution.sort(length)
 	print solution
 
 solve('coaetbnwurdsineb')