4
\$\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 occurrences 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 occurrences of a 'word' in a string. For example: string bananana has 4 occurrences of word nana. Note that occurrence of anan is counted as nana (backward).

  2. The fdiags stands for 'find all diagonals' of 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 do I 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\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Unused

Since the n variable is not used in the nword function, the following statement can be deleted:

n = len(word);

Simpler

Although Python does not have a built-in method to reverse the characters in a string, the following code:

listed = list(normal)
listed.reverse()
reverse = ''.join(listed)

can be simplified with a single line:

reverse = normal[::-1] # Reverse the input string

This is a string slice, and it is a common idiom in Python. I still think it warrants a comment, though. Refer to: How do I reverse a string in Python?

DRY

The 2 while loops in nword have nearly identical code. You could place the code into a helper function which is called twice (see the code below).

Documentation

The PEP 8 style guide recommends adding docstrings for functions. For example:

def fdiags(grid):
    """
    Find all diagonals of the grid.
    It returns a list of all strings representing the diagonals.
    """

Naming

The function names could be more descriptive.

nword could be num_words_in_string.

fdiags could be find_all_diagonals.

wsearch could be word_search.

Lower-case l is a bad name for a variable because it is easily confused with the number 1, not to mention that it conveys little meaning:

for l,r in zip(Ll, Lr):

Variable names n and m convey little information in the fdiags function. Either rename them or add comments to describe them.

Layout

Lines with multiple statements like this:

idx = 0; start = 0;

should be split up:

idx = 0
start = 0

The black program can be used to automatically split these up for you. black can also be used to apply consistent whitespace around operators.

Here is a simplified version of the nword function:

def nword(string, word):
    def get_count(full_string):
        count = 0
        idx = 0
        start = 0
        while idx >= 0:
            idx = full_string.find(word, start)
            if idx >= 0:
                count += 1
            start = idx + 1
        return count

    reverse = string[::-1] # Reverse the input string

    return get_count(string) + get_count(reverse)
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.