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.

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...

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.

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"
]

"""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...
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
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')