nested for loops to recursion

[ashkea26]

Hi, new to this thread and programming itself. We've got a software project that asks us to make a game of Boggle/Twisted Word Search, which finds words in a given grid of letters, that has no restrictions, except that the next letter of the word should be adjacent to the previous one. I sort of got the gist but I ended up with a messy nested for loops. My problem is it takes too long to run and it is limited to only five-letter words. My question is how can I make it a recursive function that has a flexible limit, depending on the size of the grid. I've been stuck on this rut for a week now, I'm just really desperate at this point. Thank you! As far as I know, there are no restrictions on this project of ours.

def word_searcher(self,position = (0,0)):
        row, col = position
        words = []
        curr_word = self.grid[row][col]
        curr_word_loc = [(row,col)]
        for a in self.adjacent_finder((row,col)):
            curr_word += self.return_letter(a)
            curr_word_loc.append(a)
            for b in self.adjacent_finder(a):
                if b not in curr_word_loc:
                    curr_word += self.return_letter(b)
                    if curr_word in dict_offlist:
                        words.append(curr_word)
                    curr_word_loc.append(b)
                    for c in self.adjacent_finder(b):
                        if c not in curr_word_loc:
                            curr_word+=self.return_letter(c)
                            if curr_word in dict_offlist:
                                words.append(curr_word)
                            for d in self.adjacent_finder(c):
                                if d not in curr_word_loc:
                                    curr_word+=self.return_letter(d)
                                    if curr_word in dict_offlist:
                                        words.append(curr_word)
                                    for e in self.adjacent_finder(d):
                                        if d not in curr_word_loc:
                                            curr_word+=self.return_letter(e)
                                            if curr_word in dict_offlist:
                                                words.append(curr_word)
                                            curr_word = self.grid[row][col]+self.return_letter(a)+self.return_letter(b)+self.return_letter(c)+self.return_letter(d)
                                            curr_word_loc =[(row,col)]
                                            curr_word_loc.append(a)
                                            curr_word_loc.append(b)
                                            curr_word_loc.append(c)
                                            curr_word_loc.append(d)
                                            curr_word = self.grid[row][col]+self.return_letter(a)+self.return_letter(b)+self.return_letter(c)
                                    curr_word_loc =[(row,col)]
                                    curr_word_loc.append(a)
                                    curr_word_loc.append(b)
                                    curr_word_loc.append(c)
                            curr_word = self.grid[row][col]+self.return_letter(a)+self.return_letter(b)
                            curr_word_loc =[(row,col)]
                            curr_word_loc.append(a)
                            curr_word_loc.append(b)
                    curr_word = self.grid[row][col]+self.return_letter(a)
                    curr_word_loc =[(row,col)]
                    curr_word_loc.append(a)
            curr_word = self.grid[row][col]
            curr_word_loc = [(row,col)]
        return words

I screwed insertion of the code part lol

[Larz60+]

could you please specify the rules to your game.
That would be easier than to try and make sense of your code.
too many gears spinning here.

[ichabod801]

You don't need recursion for this, you just need another loop.

start = [x, y]
all_data = []
for direction in [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]:
    data = []
    current = start[:]
    for step in depth:
        data.append(self.grid[current [0]][current [1]]
        current = [current[0] + direction[0], current[1] + direction[1]]
        if not (0 <= current[0] < len(self.grid)) or not (0 <= current[1] < len(self.grid[0])):
            break
    all_data.append(data)

I didn't test the above code, but that's the basic format you want. Loop through the directions. For each direction go back to the start and step in that direction depth times. For each step, record the data at that point and check that you haven't gone off the edge of the grid.

[ashkea26]

could you please specify the rules to your game.
That would be easier than to try and make sense of your code.
too many gears spinning here.

We were asked to create a grid with letters, size varies on the imported file. We must get all the possible words in the grid. Words can be created in any way, as long as the letter following the next letter of the word should be adjacent in the grid (diagonal,horizontal or vertical). Thank you.

---

You don't need recursion for this, you just need another loop.

 start = [x, y] all_data = [] for direction in [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]: data = [] current = start[:] for step in depth: data.append(self.grid[current [0]][current [1]] current = [current[0] + direction[0], current[1] + direction[1]] if not (0 <= current[0] < len(self.grid)) or not (0 <= current[1] < len(self.grid[0])): break all_data.append(data) 

I didn't test the above code, but that's the basic format you want. Loop through the directions. For each direction go back to the start and step in that direction depth times. For each step, record the data at that point and check that you haven't gone off the edge of the grid.

I don't know if I just comprehended it wrong (sorry) but won't that code only go in one direction? Like purely diagonal, horizontal or vertical?
C A T
O D O
C G O
For this grid, the possible words are CAT, DOG, TACO, GOOD, TAD, GOD etc.. Thank you!

[ichabod801]

Oh, you want to be able to change directions. Okay, for that recursion would work better. So you would still loop through the directions, but you would just take one step, and then call the function recursively.

def word_search(x, y, word = [], depth = word_length):
    if depth = 0:
        return [word]
    results = []
    for delta_x, delta_y in directions:
        new_x = x + delta_x
        new_y = y + delta_y
        if not (0 <= new_x < len(grid)) or not (0 <= new_y < len(grid[0])):
            continue
        word.append(grid[x + delta_x][y + delta_y])
        results.extend(word_search(new_x, new_y, word, depth = depth - 1))
    return results

Again, not tested, but the basic format should be something like that.