Word search

[kanodi]

Hi guys, I wonder if any of you can help me with my problem....

I am trying to write a script that searches a file that describes a grid of letters, like:

wergfdghytr
bhgiusuwiee
popeldorlfse
funwrdtywa

The script uses another file for a word list, where each line contains a word. Both of these files are passed as arguments to the script as well as the length of the words to search for, like: python word_search.py grid.txt words.txt 5 The words can be in any direction, and can change direction, the only rule is that the next letter must be next to(above, diagonally above, left, etc, etc) the current letter.

I can not tell you how many times I have attempted this script and started again out of frustration :/ lol.

Any help or ideas on how to go about this would be greatly appreciated.

[jlm699]

My thoughts:

Traverse the grid from top-to-bottom, and left-to-right (ie, just like reading a book).
On each character, make a list of *this letter concatenated with every surrounding letter (for this example we'll start at the left or due west position and progress counter-clockwise, ie:

grid = """
ashfghj      0,0 1,0 2,0 3,0 4,0 5,0 6,0
weatyuu      0,1 1,1 2,1 3,1 4,1 5,1 6,1
xctbnmz      0,2 1,2 2,2 3,2 4,2 5,2 6,2
"""

Assume we're looking for hat... we start at position 0,0 and make the list ['as', 'ae', 'aw'] , none of which match 'ha' (from 'hat'). Although since the letter a doesn't match the first character of 'hat', we can move on...

We repeat for s and then h. The character 'h' matches the input_word[0] so we construct the list as above, which reads ['hs', 'he', 'ha', 'ht', 'hf'] and we have a match with 'ha', so we take the indices of the two positions and extrapolate the direction for the length of the desired word (3)...
So 'ha' corresponds to 2,0 and 2,1 ... implying that the final character is at 2,2. After a simple check of 2,0+2,1+2,2 , we have a match and we win.

As such I guess instead of a list of we could use a dictionary keeping track of indices as well... however that wouldn't be necessary since if we know the starting index, along with the position (index) of the two-letter combo in our list, we can guess at which position the second character was (granting that you following the same pattern of adjacent letters every time).

I don't mean to ramble, but it's an interesting challenge and in fact if you search the forum I believe somebody posted a very similar problem a short while back.

I hope something that I've said above can help you get started...

[kanodi]

Thank your for your input Jim, your solution is similar to one of my previous attempts, it is nice to know I am going about it the 'right' way. Perhaps I will have to try it again.

I must have overlooked the other post on the forum, my bad.

[kanodi]

Well I have finally got a working script! thank god and coffee :p

In case anybody else is looking into something similar I thought I would post the code. It probably is not the most efficient way to go about the problem and could be improved, but it works, so I am happy :) ....

#The grid of letters to search through
GRID = [
	"dfghitkloks",
	"tyuiwasftop",
	"zakhvbiutrs",
	"fropunthilk",
	"ckjoiedaspl"
]

def word_can_be_made(word):
	"""Determines if a word can me made from the
		grid of letters."""
	#Check every letter in the grid for the 
	#first letter of the word
	y = 0
	for line in GRID:
		x = 0
		for char in line:
			if char == word[0]:
				found_count = 1 #Keep track of letters found
				cy = y #Current row
				cx = x #Current col
				coords_used = [] #Keep track of letters used
				coords_used.append([y, x]) #Add the first letter, because we just used it
				for letter in word[1:len(word)]: #For all other letters in word...
					found = False #Word not found yet
					for ty in range(cy - 1, cy + 2): #Try all letters surrounding current letter
						if ty < 0 or ty > (len(GRID) - 1):
							break
						for tx in range(cx - 1, cx + 2):
							if tx < 0 or tx > (len(GRID[ty]) - 1):
								break
							if GRID[ty][tx] == letter: #Letter found
								used = False
								for c in coords_used: #Have we already used it?
									if c[0] == ty and c[1] == tx:
										used = True
										break
								if used:
									break
								cy = ty #Update current letter coords
								cx = tx
								found_count += 1
								found = True
								coords_used.append([ty, tx]) #Add letter to used list
							if found:
								break
						if found:
							break
					if not found:
						break
				if found_count == len(word): #Yay word can me made!
					return True
			x += 1
		y += 1
	return False

if __name__ == '__main__':
	found = []
	w_file = open('words.txt'), 'r')
	words = w_file.readlines()
	w_file.close()
	for word in words:
		if word_can_be_made(word):
			found.append(word)
	print "Found %s words:" %len(words)
	for word in found:
		print word

The script checks for every word in a file called words.txt, and trys every possible starting point for the words first letter, then it goes about checking the surrounding letters for the next letter and so on.