Puzzle

Ezra and I took 30 minutes this evening and wrote a word find puzzle solver in Python. This uses a little bit of pre-processing, sets, dictionaries, tuples, and other (less efficient) techniques to fairly quickly find the answers.


	board = '''
	m a i n v f
	a n a f d d
	s m i t h a
	i r o n r v
	e m o z a i
	a e e t a d
	'''

	words = '''
	ezra
	david
	sam
	smith
	iron
	fire
	'''

	# use this to get a dictionary involved.
	#words = open('dictionary.txt', 'rt').read()

	BOARD = {}

	x = 0
	y = 0
	for line in board.strip().split('\n'):
	y += 1
	x = 0
	for char in line:
	char = char.lower()
	if char in 'abcdefghijklmnopqrstuvwxyz':
	x += 1
	BOARD[x,y] = char

	WORDS = set()

	for line in words.strip().split('\n'):
	word = line.strip().lower()
	if len(word) >= 3:
	WORDS.add(word)

	DIREC = (
	(0,-1),
	(1,-1),
	(1,0),
	(1,1),
	(0,1),
	(-1,1),
	(-1,0),
	(-1,-1),
	)

	PREFX = set()

	FOUND = set()

	for word in WORDS:
	prefix = ''
	for c in word[:-1]:
	prefix += c
	PREFX.add(prefix)

	# For each position on the board
	for x,y in BOARD:

	# For each direction of 8
	for xx,yy in DIREC:
	x1 = x #cur pos
	y1 = y #cur pos
	word = '' #cur word

	while True:

	# Check if off board
	if (x1,y1) not in BOARD:
	break

	# Get character at current pos
	word += BOARD[x1,y1]

	# If it is a word, add it
	if word in WORDS:
	FOUND.add(word)

	# If this is not a prefix, then bail out
	if word not in PREFX:
	break

	# Increment current position based on direction
	x1 += xx
	y1 += yy

	print(FOUND)