3
\$\begingroup\$

I have a Word Search algorithm, the main function (wsearch) takes a grid of letters as an input and a 'word' to search for. The output is the number of occurence of the 'word' in the grid.

First, I break down the problem into three functions (including wsearch).

  1. The nword is for looking the number of occurence of a 'word' in a string. For example: string bananana has 4 occurence of word nana. Note that occurence of anan is counted as nana (backward).

  2. The fdiags stands for 'find all diagonals' or the grid/matrix. It returns a list of all strings representing the diagonals.

  3. Finally, the wsearch uses the 2 functions above.

Example:

grid = [list(input()) for j in range(5)]
word = input()
wsearch(grid, word)

input:

gogog
ooooo
godog
ooooo
gogog
dog

The output will be 8 (horizontal, vertical, and diagonal form of dog).

How to make it more readable and efficient?


The functions:

def nword(string, word):
    normal = string
    listed = list(normal)
    listed.reverse()
    reverse = ''.join(listed)

    n = len(word); count = 0;

    idx = 0; start = 0;
    while idx >= 0:
        idx = normal.find(word, start)
        if idx >= 0:
            count+=1
        start=idx+1
    idx = 0; start = 0;
    while idx >= 0:
        idx = reverse.find(word, start)
        if idx >= 0:
            count+=1
        start=idx+1

    return count

def fdiags(grid):
    n = len(grid[0])
    m = len(grid)

    diags = []
    Ll = [(1, n-1)] + [(0, i+1) for i in range(n-1)]
    Lr = [(1, 0)] + [(0, i) for i in range(n-1)]
    for l,r in zip(Ll, Lr):
        diags.append(''.join([ grid[l[0]+j][l[1]-k] for j, k in zip(range(m-l[0]), range(l[1]+1)) ]))
        diags.append(''.join([ grid[r[0]+j][r[1]+k] for j, k in zip(range(m-r[0]), range(n-r[1])) ]))

    return diags

def wsearch(grid, word):

    n = len(grid[0])
    m = len(grid)
    if n == 1:
        from_cols = sum([nword(''.join(i), word) for i in zip(*grid)])
        return from_cols
    if m == 1:
        from_rows = sum([nword(''.join(i), word) for i in grid])
        return from_rows
    from_diags = sum([nword(i, word) for i in fdiags(grid)])
    from_cols = sum([nword(''.join(i), word) for i in zip(*grid)])
    from_rows = sum([nword(''.join(i), word) for i in grid])
    return from_diags+from_cols+from_rows
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.