Finding locations of words as lists of coordinates in a grid of letters

Given a grid of letters and a list of words, find the location of each word as a list of coordinates. Resulting list can be in any order, but coordinates for individual words must be given in order. Letters cannot be reused across words, and letters. Each given word is guaranteed to be in the grid. Consecutive letters of words are either down or to the right (i.e no reversed words or reversed sections of words, only down or to the right).

For example, given the following grid and set of words,

 [
    ['d', 'r', 'd', 'o', 'r', 's'],
    ['o', 'b', 'i', 'g', 'n', 'c'],
    ['g', 'f', 'n', 'm', 't', 'a'],
    ['x', 's', 'i', 'a', 'n', 't']
]

words1 = [ "dog", "dogma", "cat" ]

output the list of coordinates below:

findWords(grid, words)->
  [ [ (1, 5), (2, 5), (3, 5) ], # cat
    [ (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)], # dogma
    [ (0, 0), (1, 0), (2, 0) ], # dog
  ]

In this example, the “dog” in “dogma” cannot be used for the word “dog” since letters cannot be reused.

Answer

Approach

1. Find paths that spell words. We only continue a path as long as its a prefix of a word.
2. We quickly check if a word is a prefix by using bisect_left to check if it’s found in the list of words (a fast alternative to Trie Tree).
3. We gather the list of paths for each word
4. We reduce the paths to the non-overlapping ones to satisfy the requirement that no two words share a cell letter.

Code

from bisect import bisect_left

def find_words(board, words, x, y, prefix, path):
    ' Find words that can be generated starting at position x, y '
    
    # Base case
    # find if current word prefix is in list of words
    found = bisect_left(words, prefix)  # can use binary search since words are sorted
    if found >= len(words):
        return
   
    if words[found] == prefix:
        yield prefix, path              # Prefix in list of words

    # Give up on path if what we found is not even a prefix
    # (there is no point in going further)
    if len(words[found]) < len(prefix) or words[found][:len(prefix)] != prefix:
        return
    
    # Extend path by one lettter in boarde
    # Since can only go right and down 
    # No need to worry about same cell occurring multiple times in a given path
    for adj_x, adj_y in [(0, 1), (1, 0)]:
        x_new, y_new = x + adj_x, y + adj_y
        if x_new < len(board) and y_new < len(board[0]):
            yield from find_words(board, words, x_new, y_new, 
                                  prefix + board[x_new][y_new], 
                                  path + [(x_new, y_new)])
     
def check_all_starts(board, words):
    ' find all possilble paths through board for generating words '
    # check each starting point in board
    for x in range(len(board)):
        for y in range(len(board[0])):
            yield from find_words(board, words, x, y, board[x][y], [(x, y)])
   
def find_non_overlapping(choices, path):
    ' Find set of choices with non-overlapping paths '
    if not choices:
        # Base case
        yield path
    else:
        word, options = choices[0]

        for option in options:
            set_option = set(option)
            
            if any(set_option.intersection(p) for w, p in path):
                # overlaps with path
                continue
            else:
                yield from find_non_overlapping(choices[1:], path + [(word, option)])
        
    
def solve(board, words):
    ' Solve for path through board to create words '
    words.sort()
    
    # Get choice of paths for each word
    choices = {}
    for word, path in check_all_starts(board, words):
        choices.setdefault(word, []).append(path)
    
    # Find non-intersecting paths (i.e. no two words should have a x, y in common)
    if len(choices) == len(words):
        return next(find_non_overlapping(list(choices.items()), []), None)
    

Tests

Test 1

from pprint import pprint as pp

words = [ "dog", "dogma", "cat" ]
board = [
            ['d', 'r', 'd', 'o', 'r', 's'],
            ['o', 'b', 'i', 'g', 'n', 'c'],
            ['g', 'f', 'n', 'm', 't', 'a'],
            ['x', 's', 'i', 'a', 'n', 't']]

pp(solve(board, words))
        

Output

Test 1
[('dog', [(0, 0), (1, 0), (2, 0)]),
 ('dogma', [(0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]),
 ('cat', [(1, 5), (2, 5), (3, 5)])]

Test 2

words = ["by","bat"] 
board = [ ['b', 'a', 't'], 
          ['y', 'x', 'b'], 
          ['x', 'x', 'y'], ] 

pp(solve(board, words))

Output

Test 2
[('bat', [(0, 0), (0, 1), (0, 2)]), 
 ('by', [(1, 2), (2, 2)])]