The one about words

Weekly Challenge 299

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Replace Words

Task

You are given an array of words and a sentence.

Write a script to replace all words in the given sentence that start with any of the words in the given array.

My solution

For this task I use a regular expression to make the transformation. The complete code is

def replace_words(words: list[str], sentence: str) -> str:
    regexp = r"(?<![a-z])(" + "|".join(map(re.escape, words)) + r")([a-z]*(?:'[a-z]+)?)"
    return re.sub(regexp, r'\1', sentence)

The first bracket (?<![a-z]) is a negative look behind. 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