1
\$\begingroup\$

This function will check a word with some letters missing, missing letters will be indicated by an "_ " (notice that there is a space after the underscore). The word with missing letters needs to be checked against a full word and if both words are found to be identical ( disregarding the "_ " the function should return True otherwise False.

This is part of a problem set from the MIT Online Course. here is how i managed to do this:


def match_with_gaps(my_word, other_word):
    '''
    my_word: string with "_" characters
    other_word: string, regular English word
    returns: boolean, True if all the actual letters of my_word match the 
    corresponding letters of other_word, or the letter is the special symbol "_",
    and my_word and other_word are of the same length;
    False otherwise:
    '''
    my_word = my_word.replace(' ','')
    for char in my_word:
        if char.isalpha():
            if my_word.count(char) != other_word.count(char):
                return False
    return len(my_word) == len(other_word)

An example :

a = match_with_gaps('a p p _ e', 'apple')
b = match_with_gaps('a p p _ c', 'apple')
print(a) >> outputs : True
print(b) >> outputs : False

I also came up with another way:

def match_with_gaps(my_word, other_word):
    '''
    my_word: string with _ characters, current guess of secret word
    other_word: string, regular English word
    returns: boolean, True if all the actual letters of my_word match the 
        corresponding letters of other_word, or the letter is the special symbol
        _ , and my_word and other_word are of the same length;
        False otherwise: 
    '''
    my_word = my_word.replace(' ', '')
    if len(my_word) != len(other_word):
        return False
    else:
        for i in range(len(my_word)):
            if my_word[i] != '_' and (
                my_word[i] != other_word[i] \
                or my_word.count(my_word[i]) != other_word.count(my_word[i]) \
            ):
                return False
        return True

which will give the same output but using a different method.

Which way is more efficient / will give more accurate results? and is there a third better method? Please give reason to your answer. And thanks in advance.

\$\endgroup\$
  • \$\begingroup\$ What should be the output for match_with_gaps('_ _ _ _e', 'apple') ? \$\endgroup\$ – RomanPerekhrest Oct 19 at 18:50
  • \$\begingroup\$ It should return True. \$\endgroup\$ – Elbasel Oct 19 at 18:52
1
\$\begingroup\$

Your second method is better than the first, solely due to the fact that it has one less bug than the first one:

In [5]: match_with_gaps("a p e _ p", "apple")
Out[5]: True

In [6]: match_with_gaps2("a p e _ p", "apple")
Out[6]: False

However, both fail if a character is masked that appears more than once:

In [7]: match_with_gaps("a p _ l e", "apple")
Out[7]: False

In [8]: match_with_gaps2("a p _ l e", "apple")
Out[8]: False

While you do check that the count of each character is the same, this does not mean that the words are the same. And the counts may differ because some character are masked.

The second approach is also slightly better because it checks the length first, there's no need for a complicated algorithm if that is not the case.

In your second function I would use a few tricks to reduce the amount of indentation you have to deal with. You also should not check the count of the characters, since you are going to go through all characters anyway and it actually introduces the second bug:

def match_with_gaps(my_word, other_word):
    '''
    my_word: string with _ characters, current guess of secret word
    other_word: string, regular English word
    returns: boolean, True if all the actual letters of my_word match the 
        corresponding letters of other_word, or the letter is the special symbol
        _ , and my_word and other_word are of the same length;
        False otherwise: 
    '''
    my_word = my_word.replace(' ', '')
    if len(my_word) != len(other_word):
        return False
    for c1, c2 in zip(my_word, other_word):
        if c1 == '_':
            continue
        if c1 != c2:
            return False
    return True

You could make this more compact using all:

def match_with_gaps(my_word, other_word):
    '''
    my_word: string with _ characters, current guess of secret word
    other_word: string, regular English word
    returns: boolean, True if all the actual letters of my_word match the 
        corresponding letters of other_word, or the letter is the special symbol
        _ , and my_word and other_word are of the same length;
        False otherwise: 
    '''
    my_word = my_word.replace(' ', '')
    if len(my_word) != len(other_word):
        return False
    return all(c1 in ('_', c2) for c1, c2 in zip(my_word, other_word))

If you do want to compare counts of characters, you should use collections.Counter, instead of list.count. The former goes through the whole iterable once and sum up the occurrences of each unique element, whereas you need to call list.count for each unique element and each call traverses the whole iterable.

\$\endgroup\$
1
\$\begingroup\$

Your 2nd approach is better that 1st as it adds length comparison, but

  • it has redundant else: branch. The 1st if condition, if positive, has unambiguous statement return False terminating function call
  • my_word.count(my_word[i]), other_word.count(my_word[i] calls will traverse sequence of chars (word) on each loop iteration for equal characters (trying to "run ahead")

Consider the following approach with builtin any function (returns True if any element of the iterable is true):

def match_with_gaps(my_word, full_word):
    '''
    my_word: string with _ characters, current guess of secret word
    full_word: string, regular English word
    returns: boolean, True if all the actual letters of my_word match the
        corresponding letters of full_word, or the letter is the special symbol
        _ , and my_word and full_word are of the same length;
        False otherwise
    '''
    my_word = my_word.replace(' ', '')

    # check for length OR respective characters mismatch
    if len(my_word) != len(full_word) \
            or any(c1 != '_' and c1 != c2 for c1, c2 in zip(my_word, full_word)):
        return False

    return True

print(match_with_gaps('a p p _ e', 'apple'))   # True
print(match_with_gaps('a p p _ c', 'apple'))   # False
print(match_with_gaps('a _ _ _ _', 'apple'))   # True
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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