Word finder using pygame

Question

I made a word searching app that allows the user to input words into a text box, and parts of the word grid will be highlighted to show the location of the words. The letters of the grid can be edited while you are using it by clicking on the cell, and pressing the key you want to replace the current letter with.

Here is how it goes:

enter image description here

I made this recursive function to find each word:

 def adj(self, c, idx, lstlst, wrd):
 x, y = self.cells.index(c) % self.cols, self.cells.index(c) // self.cols
 x1, x2 = max(0, x - 1), min(x + 2, self.cols + 2)
 y1, y2 = max(0, y - 1), min(y + 2, self.rows + 2)
 adjs = [cell for row in self.grid[y1:y2] for cell in row[x1:x2] if cell != c]
 taillst = lstlst[-1]
 for cell in adjs:
 if len(wrd) > idx:
 if cell.text == wrd[idx] and cell not in taillst:
 lstlst.append(taillst[:] + [cell])
 self.adj(cell, idx+1, lstlst, wrd)

This is how I called it:

 elif event.type == pygame.KEYDOWN:
 grid.type(event)
 word.type(event)
 for cell in grid.cells:
 cell.color = (0, 0, 0)
 for cell in grid.cells:
 lstlst = [[cell]]
 grid.adj(cell, 1, lstlst, word.text)
 for lst in lstlst:
 if ''.join([c.text for c in lst]) == word.text:
 for c in lst:
 c.color = (255, 0, 0)

I know, it's a mess, but I am trying. Despite that, can you show me how can I improve the efficiency of my word-searching algorithim?

Here is my entire code:

import pygame
pygame.font.init()
wn = pygame.display.set_mode((600, 600))
letters = \
'''
KJDJCIOSDZ
PGRIWOTAID
VETVALCGLS
OFZESGZASW
SOYRBKOADL
FUWTQOXNGE
CILIWMEPAV
NEZCJRVZNL
GXZAOQMFIG
EUPLIESCGP
HORIZONTAL
'''
class Cell():
 def __init__(self, x, y, s, text='', color=(0, 0, 0), cell=True):
 self.input_box = pygame.Rect(x, y, s, s)
 self.x = x
 self.y = y
 self.s = s
 self.w = s
 self.color_inactive = color
 self.color_active = pygame.Color('purple')
 self.color = self.color_inactive
 self.text = text
 self.active = False
 self.pad = 10
 self.cell = cell
 self.font = pygame.font.Font(None, s)
 def check_status(self, pos):
 if self.input_box.collidepoint(pos):
 self.active = not self.active
 else:
 self.active = False
 self.color = self.color_active if self.active else self.color_inactive
 def type(self, event):
 if self.active:
 if self.cell:
 if event.unicode and event.unicode.lower() in 'abcdefghijklmnopqrstuvwxyz ':
 self.text = event.unicode
 else:
 if event.key == pygame.K_BACKSPACE:
 self.text = '' if len(self.text) < 2 else self.text[:-1]
 elif event.unicode and event.unicode.lower() in 'abcdefghijklmnopqrstuvwxyz ':
 self.text += event.unicode 
 
 def draw(self):
 txt = self.font.render(self.text, True, self.color)
 if not self.cell:
 width = max(self.w, txt.get_width())
 self.input_box.w = width + self.pad * 2
 x = self.x + self.pad
 else:
 x = self.x+(self.s-txt.get_width())//2
 y = self.y+(self.s-txt.get_height())*5//7
 wn.blit(txt, (x, y))
 pygame.draw.rect(wn, self.color, self.input_box, 2)
class Grid():
 def __init__(self, x, y, size, letters, color=(0, 0, 0)):
 rows = len(letters)
 cols = len(letters[0])
 self.grid = [[Cell(i*size+x, j*size+y, size, letter) for i, letter in enumerate(row)] for j, row in enumerate(letters)]
 self.cells = [cell for row in self.grid for cell in row]
 self.rows = rows
 self.cols = cols
 def check_status(self, pos):
 for cell in self.cells:
 cell.check_status(pos)
 def type(self, event):
 for cell in self.cells:
 cell.type(event)
 def adj(self, c, idx, lstlst, wrd):
 x, y = self.cells.index(c) % self.cols, self.cells.index(c) // self.cols
 x1, x2 = max(0, x - 1), min(x + 2, self.cols + 2)
 y1, y2 = max(0, y - 1), min(y + 2, self.rows + 2)
 adjs = [cell for row in self.grid[y1:y2] for cell in row[x1:x2] if cell != c]
 taillst = lstlst[-1]
 for cell in adjs:
 if len(wrd) > idx:
 if cell.text == wrd[idx] and cell not in taillst:
 lstlst.append(taillst[:] + [cell])
 self.adj(cell, idx+1, lstlst, wrd)
 def draw(self):
 for cell in self.cells:
 cell.draw()
grid = Grid(50, 70, 32, list(filter(None, letters.split('\n'))))
word = Cell(50, 20, 32, cell=False)
while True:
 for event in pygame.event.get():
 if event.type == pygame.QUIT:
 pygame.quit()
 elif event.type == pygame.MOUSEBUTTONDOWN:
 grid.check_status(event.pos)
 word.check_status(event.pos)
 elif event.type == pygame.KEYDOWN:
 grid.type(event)
 word.type(event)
 for cell in grid.cells:
 cell.color = (0, 0, 0)
 for cell in grid.cells:
 lstlst = [[cell]]
 grid.adj(cell, 1, lstlst, word.text)
 for lst in lstlst:
 if ''.join([c.text for c in lst]) == word.text:
 for c in lst:
 c.color = (255, 0, 0)
 wn.fill((255, 255, 255))
 grid.draw()
 word.draw()
 pygame.display.flip()

Answer 1

Regarding speedups.

Well, the first thing I spotted is this line;

x, y = self.cells.index(c) % self.cols, self.cells.index(c) // self.cols.

I think you can replace it with this to avoid double search of the list

cell_idx = self.cells.index(c)
x, y = cell_idx % self.cols, cell_idx // self.cols

But, I think it is better to get rid of self.cells.index(c) completely. To do that, adj function would require x,y of the cell (also notice the early return, you don't need to iterate adjacent cells if the word is already exhausted).

Here is my version:

 def adj(self, x, y, idx, lstlst, wrd):
 # Return early if the word is already exhausted
 if len(wrd) <= idx:
 return
 x1, x2 = max(0, x - 1), min(x + 1, self.cols - 1)
 y1, y2 = max(0, y - 1), min(y + 1, self.rows - 1)
 taillst = lstlst[-1]
 for adj_y in range(y1, y2 + 1):
 for adj_x in range(x1, x2 + 1):
 # Skip the given cell
 if adj_x == x and adj_y == y:
 continue
 adj_cell = self.grid[adj_y][adj_x]
 if adj_cell.text == wrd[idx] and adj_cell not in taillst:
 lstlst.append(taillst[:] + [adj_cell])
 self.adj(adj_x, adj_y, idx + 1, lstlst, wrd)

And the main loop would become:

while True:
 # no change here ...
 elif event.type == pygame.KEYDOWN:
 grid.type(event)
 word.type(event)
 for cell in grid.cells:
 cell.color = (0, 0, 0)
 for y in range(len(grid.grid)):
 for x in range(len(grid.grid[0])):
 cell = grid.grid[y][x]
 lstlst = [[cell]]
 grid.adj(x, y, 1, lstlst, word.text)
 for lst in lstlst:
 if "".join([c.text for c in lst]) == word.text:
 for c in lst:
 c.color = (255, 0, 0)

Now you can get rid of grid.cells (so reduced memory footprint).

Last but not least, if I'm not wrong you should be able to change this line:

if cell.text == wrd[idx] and cell not in taillst:

with this to avoid search in taillst;

if cell.text == wrd[idx] and cell != taillst[-1]:

Because the matching adjacent should be end of the list (previously added by adj call), but I'm not completely sure about this.

Answer 2

UX

The GUI looks great.

It might be worth posting a message in the GUI that the puzzle is case-sensitive.

Otherwise, here are some minor coding style suggestions.

Documentation

The PEP 8 style guide recommends adding docstrings for classes and functions. They should describe the differences between a Cell and a Grid, for example.

Naming

The function name type is not too descriptive. In addition to a docstring, consider changing the name to be more specific.

The function name adj is a bit brief. That could benefit from a longer name.

In the Cell class, the variables x, y, s and w could use comments to describe what they represent.

Names like lstlst and taillst are a bit cryptic.

DRY

This string is repeated twice:

'abcdefghijklmnopqrstuvwxyz '

You could assign it to a constant:

LOWER_LETTERS = 'abcdefghijklmnopqrstuvwxyz '

Efficiency

You repeatedly execute this expression in the for loop in the adj function:

len(wrd)

You can set it to a variable before the loop:

number_of_words = len(wrd)
for cell in adjs:
 if number_of_words > idx:

• Toby Speight: LOWER_LETTERS = string.ascii_lowercase + ' ', perhaps?