Given a board where in each cell there is a letter, check if word is in it. We could start anywhere, but we could move only horizontally and vertically. Each cell could be used only once. More details on the
The board is fixed, and looks like this:
ABCE
SFCS
ADEE
I have converted the examples provided in the problem in a python test case:
class TestCodeEval(unittest.TestCase):
def test_provided_1(self):
self.assertEqual(False, solution('ASADB'))
def test_provided_2(self):
self.assertEqual(True, solution('ABCCED'))
def test_provided_3(self):
self.assertEqual(False, solution('ABCF'))
For instance, it should be easy to see that we can't follow ASADB on the board. After ASAD there is a 'F' that block the way to the final 'B'.
I have converted the board in a couple of dictionaries:
WHERE = {'A': {(0, 0), (2, 0)},
'B': {(0, 1)},
'C': {(0, 2), (1, 2)},
'D': {(2, 1)},
'E': {(0, 3), (2, 2), (2, 3)},
'F': {(1, 1)},
'S': {(1, 0), (1, 3)}}
NEIGHBORS = {
(0, 0): {(0, 1), (1, 0)},
(0, 1): {(0, 0), (1, 1), (0, 2)},
(0, 2): {(0, 1), (1, 2), (0, 3)},
(0, 3): {(0, 2), (1, 3)},
(1, 0): {(0, 0), (1, 1), (2, 0)},
(1, 1): {(1, 0), (0, 1), (2, 1), (1, 2)},
(1, 2): {(1, 1), (1, 3), (0, 2), (2, 2)},
(1, 3): {(1, 2), (0, 3), (2, 3)},
(2, 0): {(1, 0), (2, 1)},
(2, 1): {(2, 0), (2, 2), (1, 1)},
(2, 2): {(2, 1), (1, 2), (2, 3)},
(2, 3): {(2, 2), (1, 3)}
}
The first one, WHERE, is a pure utility, that let me easily find where each letter is on board.
The second one, NEIGHBORS, is a plain adjacency list, and should hint that I have seen in this problem description a graph. Given the rules of adjacency in this board it is not strictly a necessity, but it helped me to better think to the solving algorithm.
My solution is based on a graph search algorithm, adapted to the peculiarity of the problem. For each letter in the word, I check for the possible continuation, backtracking when I don't find a good way, until the word is consumed or I can't find any way to continue the search.
After some startup code, I only need a recursive function that moves from one step to the next one:
def find(node, visited, letters): # 1
if not letters: # 2
return True
letter = letters.popleft() # 3
nodes = WHERE[letter] & NEIGHBORS[node] # 4
for node in nodes:
if node not in visited: # 5
visited.add(node)
if find(node, visited, letters): # 6
return True
visited.remove(node)
letters.appendleft(letter) # 7
return False
1. I pass to the function the current position on board, then a set of already visited nodes, and finally a deque containing the letters that should be still to be found.
2. No letter pending means I have already found the word. Job done.
3. Extract the first letter I have to find from the deque.
4. The intersection between the sets where the letter is present and the nodes adjacent to the current ones give me the set of nodes where I have to look for the next step.
5. But only the nodes that I have not already visited are good candidates.
6. Recursive call.
7. If this branch is not satisfactory, I push back the letter in the deque and return False.
Full code, both test and actual python script, is on GitHub.
