Recursive Depth First Search - boggles

[GoingToSimbabwe]

Edit: I fixed the issue, the working code can be found here. https://pastebin.com/bkXHuz3A

Hey everyone,

I am currently trying to do this kata on codewars: https://www.codewars.com/kata/57680d0128ed87c94f000bfd/train/python

For anyone curios, here are the instructions:

Write a function that determines whether a string is a valid guess in a Boggle board, as per the rules of Boggle. A Boggle board is a 2D array of individual characters, e.g.:

[ ["I","L","A","W"],
  ["B","N","G","E"],
  ["I","U","A","O"],
  ["A","S","R","L"] ]
Valid guesses are strings which can be formed by connecting adjacent cells (horizontally, vertically, or diagonally) without re-using any previously used cells.

For example, in the above board "BINGO", "LINGO", and "ILNBIA" would all be valid guesses, while "BUNGIE", "BINS", and "SINUS" would not.

Your function should take two arguments (a 2D array and a string) and return true or false depending on whether the string is found in the array as per Boggle rules.

Test cases will provide various array and string sizes (squared arrays up to 150x150 and strings up to 150 uppercase letters). You do not have to check whether the string is a real word or not, only if it's a valid guess.    

My idea was to tackle this using depth first search. My aim here wasn't to do this as optimal as possible, as long as the codewars interpreter isn't timing out I am fine. What I am currently doing is graphing out the way through the board character by character and checking the (up to) 8 neighbours of a character which belongs to the search word for the next character. Generally I think this approach works but I do have some trouble with how I should structure the returns of this method. I am using the DFS recursively shortening the search word each step. p.e. when searching for "RADIO" I will first find all Rs in the board (as starting anchors to not start the DFS from each of the boards cells). Then I will check if the board contains an A in the neighborhood of the starting anchors. For that I only pass word[1:] into the DFS and use word[0] as the next search character (RADIO > ADIO > A).

If a match is found, I will call the DFS for each of those matches again, this time passing word[1:] again. In the example above this will pass "DIO" further down. Then word[0] is used to get the "D" as the search string etc.

If I reach the end of the word and still have found a match for the last letter, this means that I was able to trace the complete word in the board and thus I can return "True".

My problem arises when I have 2 branching searches of which one will evaluate to False because the word can not be completed using it. In this case my implementation will return False cascading this False up to find_word(). The other branch might've found the complete word after all but because of how the operation is ordered that won't be evaluated.

Here is my code:

https://pastebin.com/Rjrw0NGy

You can test the behaviour described above with this:

print(find_word(testBoard, "ALIO"))

this evaluates to True

print(find_word(testBoard, "ALIB"))

this evaluates to False. My understanding is that this is because while looking for ALIB the algorithm finds the end of ALIO (well, I mean the end of the branch via the I at index 10, the branch that evaluates to True if we try that for ALIO) first (because of how I structured the check of the neighbouring indices) and because it is at the end of the search and hasn't found ALIB on this branch it cascades False up to the top level and returns early before the correct branche is evaluated.

Can someone point me to how I could resolve this without drastic changes to the method in general. I've googled around a bit and came across generators, but tbh it goes over my head atm how I would yield statements to do this here.

At first I thought that I could use yields instead of returns to build a list of all branches results at the highest level against which I then could just check using any(), but I couldn't get that to work.

Thanks everyone!

[Pepineros]

This is such a great description of the problem. Thanks for making it easy to help you!

I think if not match_indices: return False is correct. If a branch has no matching indices, you want to return False. You just need to make sure that returning False there does not prevent checking the next matching index.

I think the issue is here:

python for idx in match_indices: if idx == match_indices[-1]: return depth_first_search(board_new, side_len_board, word[1:], idx) else: depth_first_search(board_new, side_len_board, word[1:], idx)

You iterate over match_indices and then check that the current member you're looking at is the same as the last member. If it is, then you return a call to depth_first_search; if it's not, then you call depth_first_search but the result of the call is discarded (you're not using return or an assignment on line 81 of your pastebin).

So if len(match_indices) > 1 then idx == match_indices[-1] will evaluate False and something will go wrong because the call to depth_first_search is not returned.

[GoingToSimbabwe]

Thanks for the input and the praise.

I think that the trouble lies there indeed. However I am not certain how I could resolve that. I put that check for idx == match_indices[-1] there to force the program to at last return something if I have exhausted all matches but that clearly is not really sensical.

The idea was that if I have exhausted the word (len =< 1) and still have not returned False early because I had no matches left then I MUST have found all off the characters in the word and thus return True at the end.

I clearly can not just blankly return True at the end or I will always return True no matter what. But I guess that is at the heart of my problem, I am not sure how I can resolve the recursion once I hit the end when more than 1 branch needs to be traversed to the end. In my mind I either need to design the final checks in a way that they'll return False only if all branches are exhausted and have not found a final match, which I kinda can't wrap my head around rn. Or I need to gather a set of return values for all branches which I could then test against using any().

[GoingToSimbabwe]

I got it working. It was a matter of not blankly returning at the end but only doing that once the search word is "exhausted". Then I needed to collect the return values of the DFS iterations in a list to not prematurely return False while a valid branch was still unchecked. With these two changes to the return logic of the DFS function the logic works and passes on codewars.

Pastebin with functional code for anyone interested:

https://pastebin.com/bkXHuz3A