How can I make my recursive function go back to continue recursing other cells

Viewed 145

I am making a word finder using Pygame. The program loops through each cell in a grid, on each cell, it runs a recursive function on it to see if it belong in a series of cells to form a word.

So far my program works only half way. Say the grid looks like this:

enter image description here

My program will print FOUND three times, so it seems fine.
But if the grid looks like this:

enter image description here

It will only print FOUND once. The reason is because once the program finds an adjacent cell that can carry on the series of cells, it ditches other possibilties adjacent to that cell.

How can I make the program go back to the other adjacent cells after the recursion completes one of them?

Here is how I defined my recursive function:

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

And here is how I called it:

                for cell in grid.cells:
                    lst = [cell]
                    grid.adj(cell, 1, lst, word)
                    if ''.join([c.text for c in lst]) == word:
                        print("FOUND")

My code:

import pygame
pygame.font.init()

wn = pygame.display.set_mode((600, 600))


class Cell():
    def __init__(self, x, y, s, color=(0, 0, 0)):
        self.input_box = pygame.Rect(x, y, s, s)
        self.x = x
        self.y = y
        self.s = s
        self.color_inactive = color
        self.color_active = pygame.Color('purple')
        self.color = self.color_inactive
        self.text = ' '
        self.active = False
        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, char):
        if self.active:
            if char and char.lower() in 'abcdefghijklmnopqrstuvwxyz ':
                self.text = char

    def draw(self):
        txt = self.font.render(self.text, True, self.color)
        x, y = self.x+(self.s-txt.get_width())//2, 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, cols, rows, size, color=(0, 0, 0)):
        self.grid = [[Cell(i*size+x, j*size+y, size) for i in range(cols)] for j in range(rows)]
        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, char):
        for cell in self.cells:
            cell.type(char)

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


    def draw(self):
        for cell in self.cells:
            cell.draw()


grid = Grid(50, 50, 10, 10, 32)
word = 'CAT'

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)
        elif event.type == pygame.KEYDOWN:
            grid.type(event.unicode)
            if event.key == pygame.K_RETURN:
                for cell in grid.cells:
                    lst = [cell]
                    grid.adj(cell, 1, lst, word)
                    if ''.join([c.text for c in lst]) == word:
                        print("FOUND")

                        
    wn.fill((255, 255, 200))
    grid.draw()
    pygame.display.flip()

1 Answers

The actual problem is you only have one list. If you want to find more than one word you need a list of lists:

if event.key == pygame.K_RETURN:
    for cell in grid.cells:
        lstlst = [[cell]]
        grid.adj(cell, 1, lstlst, word)
        for lst in lstlst:
            if ''.join([c.text for c in lst]) == word:
                print("FOUND")

When a new character is identified, you need to copy the last list of the list of lists:

taillst = lstlst[-1]
lst = taillst[:]

Append the new cell to the copy and add the copy to the end of the list of lists:

lst.append(cell)
lstlst.append(lst)

Do not increment idx, but pass idx + 1 to the next recursion level:

self.adj(cell, idx+1, lstlst, wrd)

Complete method adj:

class Grid():
    # [...]

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

The following pattern

returns the following 6 lists with 3 matches:

['C']
['C', 'A']
['C', 'A', 'T']
['C', 'A', 'T']
['C', 'A']
['C', 'A', 'T']
Related