5
\$\begingroup\$

I'm solving a python exercise. Here is a brief description:

Please write a function named find_words(search_term: str). It should return a list containing all the words in the file which match the search term.The search term may include lowercase letters and the following wildcard characters:

  • A dot . means that any single character is acceptable in its place. For example, ca. would yield words like cat and car, p.ng would yield words like ping and pong, and .a.e would yield words like sane, care and late.
  • An asterisk * at the end of the search term means that any word which begins with the search term is acceptable. An asterisk at the beginning of the search term means that any word which ends with the search term is acceptable. For example, ca* would yield words like california, cat, caring and catapult, while *ane would yield words like crane, insane and aeroplane. There can only ever be a single asterisk in the search term.
  • If there are no wildcard characters in the search term, only words which match the search term exactly are returned.

You may assume both wildcards are never used in the same search term. You may also assume the argument to the function will be in lowercase entirely.

This is the solution I came up with:

def find_words(search_term: str):

    file_to_list = []
    searched_word_list = []
    with open("words.txt", "r") as my_file:
        for line in my_file:
               line = line.strip() 
               file_to_list.append(line)

        if search_term in file_to_list:
            for item in file_to_list:
                if item == search_term:
                    searched_word_list.append(item) 

        elif "*" in search_term:
            if search_term.startswith("*"):
                search_term = search_term.replace("*","")
                for item in file_to_list:
                    if item.endswith(search_term):
                        searched_word_list.append(item)
            elif search_term.endswith("*"):
                search_term = search_term.replace("*","")
                for item in file_to_list:
                    if item.startswith(search_term):
                        searched_word_list.append(item)

        elif "." in search_term:
            for item in file_to_list:
                if len(search_term) == len(item):
                    check = False
                    false_counter = 0 #used for "false True cases" e.g. all false and the last true
                    for char_index in range(len(search_term)):
                        if search_term[char_index] != '.' and search_term[char_index] == item[char_index]:
                            check = True
                        elif search_term[char_index] != '.' and search_term[char_index] != item[char_index]:
                            check = False
                            false_counter +=1
                    if check == True and false_counter == 0:
                        searched_word_list.append(item)
                   

    return searched_word_list

This solution works fine and the requirements are satisfied, but I'm wondering whether there is a more efficient solution. I'd like to specify that I'm not allowed to use any library since I'm kind of new to programming and the aim of this exercise is to train some basic knowledge of Python. Thanks for the help.

\$\endgroup\$
1
  • \$\begingroup\$ Are you allowed to use python builtin libraries? Can you also post the words.txt here? \$\endgroup\$ Commented Dec 14, 2023 at 12:03

2 Answers 2

2
\$\begingroup\$

Edit

Originally misread the question. Assumed that there was only 1 . wildcard. Updated my code and removed point number 2 replaced with point 3.

Algorithm

  1. The current algorithm is going to be super slow. You are first matching every word in its entirety. Then check for wild cards. So, if you have a wild card in the search string you are doing the work twice. Checking if there is an * at the beginning or end of a search term is very cheap do it first.
  2. For ., you can use the same startswith and endswith trick you employed for *. At the start of the for loop find where the . is in the search_term and split the it in two two words. You can then find try to match them with the list. (See edit)
  3. Instead of using flags like check and false_counter, use the built-in all() function. It returns true only if all the elements in a list (str is a list of char) satisfy a condition. The syntax might look a bit unusual for a beginner. This is what is called as generator comprehension in python.
  4. The lines below are cursed. The first statement is going to match every word in the file list with the search_term and tell you if one exists. You then manually do the entire process to find the word. Remove the if statement.
if search_term in file_to_list:
    for item in file_to_list:
        if item == search_term:
            searched_word_list.append(item)
  1. Don't use elif "*" in search_term. It will have a penalty if the last letter is * because the code is going to check every single letter before it checks the last one. Instead, just check for the first and last letter to see if it *.

Nitpicks

  1. It is generally preferable to separate IO operations from logic. Create a second function that searches words from a find_matching_words(search_term: str, word_list : List[str]) -> List[str]. U can open the file and read all the words in the current function and then pass the list of word for logic in the second
  2. Add return type annotations.
  3. Use list or generator comprehension instead of for loops for list creation they are faster than for loops.
  4. Don't modify function parameters unless you explicitly write in documentation that you are going to do it. Python uses reference semantics which means if I search_term in my code then search_term in main will change. This behavior can be confusing.

Here is the code with all the changes applied

def matches_with_dot_wildcard(search_term, word):
    return len(search_term) == len(word) \
        and all(
            s == '.' or c == s for s, c in zip(search_term, word)
        )

def find_words(search_term, word_list):

    if search_term[0] == '*':
        search_term_stripped = search_term[1:]
        return [word for word in word_list if word.endswith(search_term_stripped)]
    elif search_term[-1] == '*':
        search_term_stripped = search_term[:-1]
        return [word for word in word_list if word.beginswith(search_term_stripped)]
    elif '.' in search_term:
        return [
            word for word in word_list 
            if matches_with_dot_wildcard(search_term, word)
        ]
    else:
        return [word for word in word_list if word == search_term]

def main():
    search_term = 'cat'
    word_list = []
    with open("words.txt", "r") as my_file:
        word_list = [line.strip() for line in my_file]

    find_words(search_term, word_list)

if __name__ == '__main__':
    main()
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Yes. Thanks. I misread the question. It states that there can only ever be one *. I mistook it for there can ever be only one wildcard. \$\endgroup\$ Commented Dec 14, 2023 at 20:10
1
\$\begingroup\$

To start, the specification itself is bad. The function signature find_words(search_term: str) is missing a filename, file object or content string. Further, what is a "word character"? They leave you to guess. For the purposes of my demonstration I assume that it matches the Python pattern definition for a word character:

Matches Unicode word characters; this includes alphanumeric characters (as defined by str.isalnum()) as well as the underscore (_). If the ASCII flag is used, only [a-zA-Z0-9_] is matched.

As a consequence, something like tater-tots would be interpreted as two different words, while tater_tots would be interpreted as one word. This is not what your code does now, and that's fine; but as you'll see there are alternative implementations that can behave differently.

In your implementation, your with captures too much code. Everything after file_to_list.append(line) should be de-indented, because you're done with the file and all of your lines are in memory. But: what if the file were massive (many GB)? In a case like that, you shouldn't store everything in memory at all; instead you should iterate over the lines of the file and process them in a stream-like fashion. That means no file_to_list, and the bulk of your code would remain within the with scope.

There's a different way of thinking about this problem, which is to pre-process the user's pattern into a regular expression, and then apply that regular expression to the lines of the file. This will have different performance characteristics (that I have not shown). Overall, though, the most important thing is to only traverse the file content once, and traverse it in chunks of memory having a better guarantee of fitting in memory.

Example (no validation)

Note that this isn't too fussed over input validation. Pattern characters like ! that are invalid will simply be ignored.

import re
from typing import Iterator, Pattern, Iterable

metapattern = re.compile(
    r'''(?x)             # verbose
    (?P<startwild>^\*)?  # wild range at start, optional
    (?P<plaintext>\w*)   # zero or more plain pattern characters
    (?P<onewild>\.)?     # single wild character, optional
    (?P<endwild>\*$)?    # wild range at end, optional
    '''
)


def compile_fragments(search_term: str) -> Iterator[str]:
    yield r'\b'  # Word boundary at start

    for match in metapattern.finditer(search_term):
        startwild = match.group('startwild')
        if startwild is not None:
            yield r'\w*'
        plaintext = match.group('plaintext')
        if plaintext:
            yield re.escape(plaintext)
        onewild = match.group('onewild')
        if onewild is not None:
            yield r'\w'
        endwild = match.group('endwild')
        if endwild is not None:
            yield r'\w*'

    yield r'\b'  # Word boundary at end


def compile_search(search_term: str) -> Pattern:
    pat = ''.join(compile_fragments(search_term))
    return re.compile(pat)


def find_words(search_pat: Pattern, content: Iterable[str]) -> Iterator[str]:
    for fragment in content:
        yield from search_pat.findall(fragment)


def test() -> None:
    actual = tuple(find_words(
        search_pat=compile_search('ca.'),
        content=('cat arcade\n', 'caller car\n'),
    ))
    assert actual == ('cat', 'car')

    actual = tuple(find_words(
        search_pat=compile_search('p.ng'),
        content=('network ping\n', 'pong game\n', 'pingpong', 'pangpang'),
    ))
    assert actual == ('ping', 'pong')

    actual = tuple(find_words(
        search_pat=compile_search('.a.e'),
        content=('sane care latte late later late_comer',),
    ))
    assert actual == ('sane', 'care', 'late')

    actual = tuple(find_words(
        search_pat=compile_search('ca*'),
        content=('california, cat', 'caring, correct, orca, catapult'),
    ))
    assert actual == ('california', 'cat', 'caring', 'catapult')

    actual = tuple(find_words(
        search_pat=compile_search('*ane'),
        content=('crane, insane,\naeroplane, inane_idea',),
    ))
    assert actual == ('crane', 'insane', 'aeroplane')


def print_from_file(search_term: str, filename: str) -> None:
    search_pat = compile_search(search_term)
    with open(filename) as file:
        for match in find_words(search_pat, file):
            print(match)


if __name__ == '__main__':
    test()

Example (validation)

Validation can be performed by looking for skipped character sequences while iterating in the metapattern:

import re
from typing import Iterator, Pattern, Iterable

metapattern = re.compile(
    r'''(?x)             # verbose
    (?P<startwild>^\*)?  # wild range at start
    (?P<plaintext>\w+)?  # one or more plain pattern characters
    (?P<onewild>\.)?     # single wild character
    (?P<endwild>\*$)?    # wild range at end, optional
    '''
)


def compile_fragments(search_term: str) -> Iterator[str]:
    yield r'\b'  # Word boundary at start
    pos = 0

    for match in metapattern.finditer(search_term):
        if match.start() != pos:
            # Skipped over some invalid characters, so this is not a valid pattern
            raise ValueError(f'"{search_term}" is not a valid pattern')
        pos = match.end()

        if match.group('startwild') is not None:
            yield r'\w*'
        plaintext = match.group('plaintext')
        if plaintext:
            yield re.escape(plaintext)
        if match.group('onewild') is not None:
            yield r'\w'
        if match.group('endwild') is not None:
            yield r'\w*'

    yield r'\b'  # Word boundary at end


def compile_search(search_term: str) -> Pattern:
    pat = ''.join(compile_fragments(search_term))
    return re.compile(pat)


def find_words(search_pat: Pattern, content: Iterable[str]) -> Iterator[str]:
    for fragment in content:
        yield from search_pat.findall(fragment)


def test() -> None:
    actual = tuple(find_words(
        search_pat=compile_search('ca.'),
        content=('cat arcade\n', 'caller car\n'),
    ))
    assert actual == ('cat', 'car')

    actual = tuple(find_words(
        search_pat=compile_search('p.ng'),
        content=('network ping\n', 'pong game\n', 'pingpong', 'pangpang'),
    ))
    assert actual == ('ping', 'pong')

    actual = tuple(find_words(
        search_pat=compile_search('.a.e'),
        content=('sane care latte late later late_comer',),
    ))
    assert actual == ('sane', 'care', 'late')

    actual = tuple(find_words(
        search_pat=compile_search('ca*'),
        content=('california, cat', 'caring, correct, orca, catapult'),
    ))
    assert actual == ('california', 'cat', 'caring', 'catapult')

    actual = tuple(find_words(
        search_pat=compile_search('*ane'),
        content=('crane, insane,\naeroplane, inane_idea',),
    ))
    assert actual == ('crane', 'insane', 'aeroplane')

    for invalid_char in '!@#$%^&(){}[]':
        try:
            compile_search('invalid' + invalid_char)
            raise AssertionError(f'"{invalid_char}" should be an invalid character')
        except ValueError:
            pass


def print_from_file(search_term: str, filename: str) -> None:
    search_pat = compile_search(search_term)
    with open(filename) as file:
        for match in find_words(search_pat, file):
            print(match)


if __name__ == '__main__':
    test()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.