Word Search

[wotthe2000]

Is there any way of finding words in a 10 x 10 grid, going horizontally and vertically? For example, if i had a text file with the following in:

xxxplanexx
xrxxxxxxxx
xexxxxxyxx
xdxxxxxexx
xxxxxxxlxx
xxxxxxxlxx
xxxxxxxoxx
xxxxxxxwxx
xkingxxxxx
xxxxxxxxxx

how would you be able to find the words red and yellow which are both displayed vertically as well as plane and king?

im assuming you start by importing the file and reading it using:

file = open('filename.txt')
text = file.read()

[jlm699]

Here's a few pointers on possible ways to help you achieve this task:

f = open( 'filename.txt' )
lines = f.readlines()
f.close()
# File contents are now contained in lines,
#  a list of each line as a separate element

for each_line in lines:
    # Now here we iterate over each line

By using slicing you will be able to find specific letters, so in your example, red would be contained on the second column ( index 1 ), meaning it would be located like this:

>>> f
['xxxplanexx', 'xrxxxxxxxx', 'xexxxxxyxx', 'xdxxxxxexx', 'xxxxxxxlxx', 'xxxxxxxlxx', 'xxxxxxxoxx', 'xxxxxxxwxx', 'xkingxxxxx', 'xxxxxxxxxx']
>>> f[1][1]
'r'
>>> f[2][1]
'e'
>>> f[3][1]
'd'
>>>

The rest of the code depends on your objective for this script

[Murtan]

Will the grid really contain 'x' where it doesn't have a word?

Is it defined that all words will start at the left and go right, or start at the top and go down?

If there are going to be other letters in the grid, it would help to have a list of the words you are expected to find.

As a place to start, how would you go about solving the problem manually. If YOU had to search the grid to find the words, describe how you would you go about it.

Can you think of how to make the computer do the same thing you would do?

[wotthe2000]

No the grid will contain random letters, both capital and not. The list of words is defined on which you have to find. At the moment I'm just trying to find words that go from left to right and top to bottom. When I have this completed I will look into looking at right to left words and bottom to top words.

I have been trying to use a binary search to find the words, but it can't find the words within the row, for example it can't find plane in xxxplanexxx, but works fine if I have just plane.

My code is:

import bisect
thelist = ["plane", "king", "red", "yellow"]
thelist.sort()
item_insert_point = bisect.bisect(thelist, "plane")
is_present = thelist[item_insert_point-1:item_insert_point]==["plane"]
v=is_present
item_insert_point = bisect.bisect(thelist, "king")
is_present = thelist[item_insert_point-1:item_insert_point]==["king"]
w=is_present
item_insert_point = bisect.bisect(thelist, "blue")
is_present = thelist[item_insert_point-1:item_insert_point]==["blue"]
x=is_present
item_insert_point = bisect.bisect(thelist, "yellow")
is_present = thelist[item_insert_point-1:item_insert_point]==["yellow"]
y=is_present
item_insert_point = bisect.bisect(thelist, "red")
is_present = thelist[item_insert_point-1:item_insert_point]==["red"]
z=is_present
print v, w, x, y, z

This returns True True False True True as expected. However when I change the list to:

thelist = ["xxplanexx", "xxkingxx", "xxredxx", "xxyellowxx"]

it returns False False False False False.

How can I make it find the words here?

Also is there a way of rotating the grid so the rows become columns and columns become row, i.e:

xxxplanexx
xrxxxxxxxx
xexxxxxyxx
xdxxxxxexx
xxxxxxxlxx
xxxxxxxlxx
xxxxxxxoxx
xxxxxxxwxx
xkingxxxxx
xxxxxxxxxx

becomes

xxxxxxxxxx
xredxxxxxx
xxxxxxxxxx
pxxxxxxxxx
lxxxxxxxxx
axxxxxxxxx
nxxxxxxxxx
exyellowxx
xxxxxxxxxx
xxxxxxxxxx

[wotthe2000]

Right I have now worked out how to transpose the grid using the code:

arr=[]
def firstword(line): arr.append(line.split()[0])
file=open('file_name')
scanner(file, firstword)
print arr
newarr=[[r[col] for r in arr] for col in range(len(arr[0]))]
print newarr

where file_name is the name of the file where the text grid is stored. Basically the code takes the first word from each line in the file, and since each line is only one word it. The result it outputs is:

[['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'], ['d', 'e', 'k', 'r', 'x', 'x', 'x', 'x', 'x', 'x'], ['x', 'x', 'i', 'x', 'x', 'x', 'x', 'x', 'x', 'x'], ['x', 'x', 'n', 'x', 'p', 'x', 'x', 'x', 'x', 'x'], ['x', 'x', 'g', 'x', 'l', 'x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'a', 'x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'n', 'x', 'x', 'x', 'x', 'x'], ['e', 'y', 'x', 'x', 'e', 'l', 'l', 'o', 'w', 'x'], ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x'], ['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x']]

The problem I have now is that each letter from the original grid is a separate string in the new grid, i.e. the column
x
r
e
d
x
x
x
x
k
x
now becomes . Is there any way of transposing it so that it becomes ?

[Murtan]

Well there is the join function...

''.join(['a','b','c'])
# returns 'abc'

does that help?

[Murtan]

I like your concept of transforming the original grid, so you can always search 'left-to-right' (its not how I thought about the problem).

Will you need to be able to search for diagonal words?

If so, can you make that transform as well?

For looking for a given word (on a given line of a given transform) you can use the find function.

'xxredxxx'.find('red')
# returns 2
'xxredxxx'.find('blue')
#returns -1

[Gribouillis]

To transpose, use zip(*L) where L is a list of tuples, like this

theList = ['xxxplanexx', 'xrxxxxxxxx', 'xexxxxxyxx', 'xdxxxxxexx', 'xxxxxxxlxx', 'xxxxxxxlxx', 'xxxxxxxoxx', 'xxxxxxxwxx', 'xkingxxxxx', 'xxxxxxxxxx']
tranposed = ["".join(t) for t in zip(*[tuple(w) for w in theList])]

#my output ---->
#['xxxxxxxxxx', 'xredxxxxkx', 'xxxxxxxxix', 'pxxxxxxxnx', 'lxxxxxxxgx', 'axxxxxxxxx', 'nxxxxxxxxx', 'exyellowxx', 'xxxxxxxxxx', 'xxxxxxxxxx']

[Murtan]

Why would your implementation using zip be better than the OP's implementation?

Would zip better support any of the other transforms that are coming? (To search for words that are right-to-left or bottom-to-top in the original grid.)

Would zip even support a diagonal transform? (The documentation seems to indicate that it favors rectangular transforms.)

OP's transform using join:

[''.join([r[col] for r in grid1]) for col in range(len(grid1[0]))]

[Gribouillis]

I'm not saying it's better. In fact I discussed this in another thread some weeks ago, so I remembered this http://www.daniweb.com/forums/post711940-6.html

[Murtan]

I apologize, when I read the first line of your original post "To transpose, use zip(*L) where L is a list of tuples, like this", I read it as 'this is the way you should do it' rather than 'another way you could do it'. So I wanted to understand why it was the 'way it should be done'.

As an alternative to the OP's method it makes perfect sense.

[wotthe2000]

Thanks for all the help so far guys. I now have this as my code:

from scanner import scanner
import array

arr=[]
def firstword(line): arr.append(line.split()[0])
file=open('grid.txt')
scanner(file, firstword)

print '\nSearching horizontal rows\n'
found = i = 0
while not found and i < len(arr):
    if 'plane' in arr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'plane found in horizontal row', i+1
else:
    print 'plane not found horizontally'

found = i = 0
while not found and i < len(arr):
    if 'red' in arr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'red found in horizontal row', i+1
else:
    print 'red not found horizontally'

found = i = 0
while not found and i < len(arr):
    if 'king' in arr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'king found in horizontal row', i+1
else:
    print 'king not found horizontally'

found = i = 0
while not found and i < len(arr):
    if 'yellow' in arr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'yellow found in horizontal row', i+1
else:
    print 'yellow not found horizontally'

newarr=[''.join([r[col] for r in arr]) for col in range(len(arr[0]))]

print '\nNow searching vertical rows\n'
found = i = 0
while not found and i < len(newarr):
    if 'plane' in newarr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'plane found in vertical column', i+1
else:
    print 'plane not found vertically'

found = i = 0
while not found and i < len(newarr):
    if 'red' in newarr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'red found in vertical column', i+1
else:
    print 'red not found vertically'

found = i = 0
while not found and i < len(newarr):
    if 'king' in newarr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'king found in vertical column', i+1
else:
    print 'king not found vertically'

found = i = 0
while not found and i < len(newarr):
    if 'yellow' in newarr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'yellow found in vertical column', i+1
else:
    print 'yellow not found vertically'

If i put the words that i needed to find in a list, i.e. L=["plane", "red", "yellow", "king"] how would i be able to loop through this list trying to find each word in the grid, rather than using this each time:

print '\nNow searching vertical rows\n'
found = i = 0
while not found and i < len(newarr):
    if 'plane' in newarr[i]:
	found = 1
    else:
	i=i+1

if found:
    print 'plane found in vertical column', i+1
else:
    print 'plane not found vertically'

so what i mean is instead of doing that loop for each of the words in the list, you just have 1 loop which checks all the words in the list one by one to see if they are in the grid.

[Murtan]

If you had the words in a list, you could just iterate over the code you have, something like:

# wordsToFind = ["plane", "red", "yellow", "king"]
# how they got into the list is up to you.

print "\nNow searching horizontal rows\n"
for word in wordsToFind:
    found = i = 0
    while not found and i < len(arr):
        if 'plane' in arr[i]:
            found = 1
        else:
            i=i+1
    if found:
        print word, 'found in horizontal row', i+1
    else:
        print word, 'not found horizontally'

#put the array transform here:

print "\nNow searching vertical columns\n"
for word in wordsToFind:
    found = i = 0
    while not found and i < len(newarr):
        if 'plane' in newarr[i]:
            found = 1
        else:
            i=i+1

    if found:
        print word, 'found in vertical column', i+1
    else:
        print word, 'not found vertically'

But even that example almost has enough repeated code to ask for a function. Have you already covered functions, could you break some of this up into one?