How To Find Words In A Matrix - Python

I've made a function to search horizontally for a word in a matrix full of letters. Now I'm trying to reuse this code in order to find any word in matrix. I need to read the matrix

Solution 1:

def in_matrix(matrix, target):

    for my_list in matrix:
        my_str = ''.join(my_list)

        if target in my_str:
            return True 

...

def search_matrix(matrix, targets):
    found = []

    for row in matrix:
        my_str = ''.join(row)

        for target in targets:
            try:
                my_str.index(target)  #Throws ValueError if target not in my_str
                found.append(target)  #This line skipped if ValueError
            except ValueError:
                pass

    return found



targets = ['pen', 'dog', 'horse']

matrix = [
    ['p','x','e','n'],
    ['g','d','o','g'],
    ['p','e','n','d']
]

print search_matrix(matrix, targets)

--output:--
['dog', 'pen']

...

import itertools as it

def word_in_permutations(target_word, permutations):
    for permutation in permutations:
        my_str = ''.join(permutation)

        try:
            my_str.index(target_word)
            return True
        except ValueError:
            pass

    return False



def search_matrix(matrix, target_words):
    all_found = []

    for row in matrix:
        row_found = []

        for target_word in target_words:
            my_iter = it.permutations(row)

            if(word_in_permutations(target_word, my_iter)):
                row_found.append(target_word)

        all_found.append(row_found)

    return all_found



targets = ['pen', 'dog', 'pig']

matrix = [
    ['n','e','d','g','o','p'],
    ['g','o','d','g','i','p'],
]

print search_matrix(matrix, targets)

--output:--
[['pen', 'dog'], ['dog', 'pig']]

There are certain things you can do with all sequence types. These operations include indexing, slicing, adding, multiplying, and checking for membership. In addition, Python has built-in functions for finding the length of a sequence and for finding its largest and smallest elements.

Python Lists: The list is a most versatile datatype available in Python which can be written as a list of comma-separated values (items) between square brackets. Good thing about a list is that items in a list need not all have the same type.

http://www.tutorialspoint.com/python/python_lists.htm

Solution 2:

In general I'd suggest that you look for ways to transpose the matrix into other matrices such that you can re-use your scanning code on each of them. For example you want to take your matrix:

a p e n
g h j k
e r l d

(rendered here without punctuation for brevity) ... and transpose it thus:

a g e
p h r
e j l
n k d

... column-wise. You can then scan that with your code. This is effectively the same as writing a new function to scan each column "downwards" for your target word(s).

You can also reverse each line of the original matrix and of this transposed matrix to scan "backwards" and "upwards" respectively.

I would re-write your search() function to take two arguments --- a matrix and a target. Then you can call it with the initial matrix, and the transposed matrix. I'd also modify the search() function to search each row forwards and backwards (and I might make that last part optional).

So my search() function would look like this:

#!/usr/bin/python
def search(matrix, target, rev=True):
    for each in matrix:
        if target in ''.join(each):
            return True
        if rev and target in ''.join(reversed(each)):
            return True
    return False

And I need a transpose() function which, as it happens, can be trivially simple:

#!/usr/bin/python
def transpose(matrix):
    return zip(*matrix)

Now my main code path would look something like:

#!/usr/bin/python
if search(matrix, target) or search(transpose(matrix), target):
    print "%s found in matrix" % target