Word Search

2022-02-07.py

question = """
Implement a word search. Given a 2D array of letters and a word to find, 
return the 2D array with the found word's letters replaced with an asterisk (*).

Example:

let grid = [['a','a','q','t'],
            ['x','c','w','e'],
            ['r','l','e','p']]

$ findWord(grid, 'ace')
$ [['*','a','q','t'],
   ['x','*','w','e'],
   ['r','l','*','p']]

"""

import re

grid = [['a','a','q','t'],
        ['x','c','w','e'],
        ['r','l','e','p']]

def makeWord(grid, coords, r=False):
    word = ''
    if r:
        coords = reversed(coords)
    for coord in coords:
        y, x = coord
        word += grid[y][x]
    return word

def testWord(grid, word, coords):
    test_word = makeWord(grid, coords)
    if re.search(word, test_word):
        grid = foundWord(grid, coords)
    test_word = makeWord(grid, coords,True)
    if re.search(word, test_word):
        grid = foundWord(grid, coords)
    return

def foundWord(grid, coords):
    for coord in coords:
        y, x = coord
        grid[y][x] = '*'
    return grid

def findWord(grid, word):
    l = len(word)
    # horizontal search
    y = 0
    for row in grid:
        for z in range(0,len(grid[0]) - l + 1):
            coords = []
            for x in range(0, l):
                xy = [y, x + z]
                coords.append(xy)
            testWord(grid, word, coords)
        y += 1
    # vertical search
    for x in range(0, len(grid[0])):
        coords = []
        for y in range(0, l):
            yx = [y, x]
            coords.append(yx)
        testWord(grid, word, coords)
    # neg diagonal search    
    for a in range(0,l-1):
        coords = []
        for x in range(0,l):
            yx = [x, a+x]
            coords.append(yx)
        testWord(grid, word, coords)
    # pos diagonal search
    for a in range(0,l-1):
        coords = []
        for x in range(0,l):
            yx = [l-x-1, a+x]
            coords.append(yx)
        testWord(grid, word, coords)
    # print results
    for row in grid:
        print(row)

findWord(grid, 'ace')