Text Problems Exercises

We'll start with a discussion of the example chatbot conversations you had. I hope you had some humerous ones.

In the following exercises, remember to provide an appropriate documentation string for each function.

• The “naive” string matching algorithm is a simple approach to checking where a smaller pattern string occurs in a larger text string.

  The algorithm simply checks whether the pattern string matches the part of the text string that starts in position 0, then position 1, etc., as illustrated by the following example.

  ababacababa
  abab                 Match at position 0
  
  ababacababa
   abab
  
  ababacababa
    abab
  
  ababacababa
     abab
  
  ababacababa
      abab
  
  ababacababa
       abab
  
  ababacababa
        abab           Match at position 6
  
  ababacababa
         abab
  

  As illustrated, it doesn't need to try matching the pattern at the final len(pattern)-1 positions of the text.

  Define a function match(text, pattern) that returns a list of matching positions. For example, match("ababacababa", "abab") should return [0, 6]. When there are no matches, for example match("abcd", "efg"), it should return [].

  Hint: To see if part of the text matches the pattern, use the appropriate “slice” of the text string.

• Some computer software is not able to handle people's names or other string input that contains unexpected characters. Define a function is_valid_string(text, valid) that returns whether the text input contains only characters that occur in the valid string.

  For example, is_valid_string("John Greiner", "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ") should return True, while is_valid_string("782d83", "01234567890.") should return False.

  Hint: First remember or look up what Python syntax will tell you whether a character "G" occurs in string "John Greiner".

• Write a function equal_words() that takes two strings and returns whether the two strings are the same, ignoring capitalization.

  For example, equal_words("JoHn", "john") should return True, while equal_words("John", "Stephen") should return False.

  Hint: Look in the CodeSkulptor documentation for functions that can help you with capitalization.

• In future exercises, we will count the number of occurrences of each word in a list or in a file. As a prelude, let's warm up with this simpler version.

  Define a function count_laptops() that takes a list such as ["Apple", "Apple", "Windows", "Linux", "Windows", "Apple"], representing a bunch of student's laptops. It returns three values: a count of the number of Apple laptops, a count of the number of Windows laptops, and a count of the number of Linux laptops.

  For example, given the example list, the function should return the three values 3, 2, 1.