The one about words

Weekly Challenge 299

Each week Mohammad S. Anwar sends out , . This ensures that we only look at the first letters in each word. The next section (" + "|".join(map(re.escape, words)) + r") joins the words we want to replace with a | character, escaping any characters that have special meaning in a regular expression. The final part ([a-z]*(?:'[a-z]+)?) matches any remaining letters, optionally with an apostrophe ' character and some more letters. This ensures we match compound words like can't and would've.

For the input from the command line, I take the last value as the sentence and everything else as words.

Examples

$ ./ch-1.py cat bat rat "the cattle was rattle by the battery"

the cat was rat by the bat



$ ./ch-1.py a b c "aab aac and cac bab"

a a a c b



$ ./ch-1.py man bike "the manager was hit by a biker"

the man was hit by a bike



$ ./ch-1.py can "they can't swim"

they can swim



$ ./ch-1.py row "the quick brown fox"

the quick brown fox

Task 2: Word Search

Task

You are given a grid of characters and a string.

Write a script to determine whether the given string can be found in the given grid of characters. You may start anywhere and take any orthogonal path, but may not reuse a grid cell.

My solution

For this task, I start by checking all rows have the same number of columns. I then go through each cell. If the letter in that cell is the first letter of the word, I call the find_match function. If that returns true, this function will return true. If it doesn't, I continue to the next cell that contains the starting letter. If none exists, I return false.

def word_search(matrix: list[list[str]], word: str) -> bool:

    rows = len(matrix)

    cols = len(matrix[0])



    for row in range(rows):

        if len(matrix[row]) != cols:

            raise ValueError("Row %s has the wrong number of columns", row)



    for row in range(rows):

        for col in range(cols):

            if matrix[row][col] == word[0]:

                if find_match(matrix, word[1:], [[row, col]]):

                    return True



    return False

The find_match function is a recursive function. It takes three parameters

1. The matrix


2. The remain letters of the word (ones that haven't been matched)


3. A list (arrayref in Perl) of [row,col] pairs of cells we have visited.

From the last position, we can move one of four directions (up, down, left or right). I check that moving this direction does not put us out of bounds or is a cell we've already used. If it isn't and the letter in this cell matches the letter we are looking for, I call the function again, taking the first letter off the word variable, and adding the new position. If I get to a point where there are no letters left, the word can be found and I return True.

def find_match(matrix, word, positions):

    if word == '':

        return True



    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    current_row = positions[-1][0]

    current_col = positions[-1][1]

    for direction in directions:

        next_row = current_row + direction[0]

        next_col = current_col + direction[1]

        if next_row < 0 or next_row >= len(matrix) or next_col < 0 or next_col >= len(matrix[0]):

            continue



        if [next_row, next_col] in positions:

            continue



        if matrix[next_row][next_col] == word[0]:

            if find_match(

                    matrix,

                    word[1:],

                    [*positions, [next_row, next_col]]

            ):

                return True



    return False

Examples

$ ./ch-2.py '[["A", "B", "D", "E"],["C", "B", "C", "A"],["B", "A", "A", "D"],["D", "B", "B", "C"]]' BDCA

True



$ ./ch-2.py '[["A", "A", "B", "B"],["C", "C", "B", "A"],["C", "A", "A", "A"],["B", "B", "B", "B"]]' ABAC

False



$ ./ch-2.py '[["B", "A", "B", "A"],["C", "C", "C", "C"],["A", "B", "A", "B"],["B", "B", "A", "A"]]' CCCAA

True