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).
The
nwordis for looking the number of occurrences of a 'word' in a string. For example: stringbanananahas 4 occurrences of wordnana. Note that occurrence ofananis counted asnana(backward).The
fdiagsstands for 'find all diagonals' of the grid/matrix. It returns a list of all strings representing the diagonals.Finally, the
wsearchuses 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
1 Answer 1
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)