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'', sentence)

The first bracket (?

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 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'', sentence)

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

The above is the detailed content of The one about words. For more information, please follow other related articles on the PHP Chinese website!