Practice for Exam 2

The following problems are typical of those that will be on the exam. However, these example problems are not comprehensive of the relevant material. In addition to answering these problems, you should also review the course's online notes and the solutions to assignments 3 and 4. We have also made a study guide.

Problems

What if we had a bunch of regular expressions and a bunch of words, and we wanted to pick the words that match all of the regular expressions. The idea is that the regular expressions represent conditions that we are looking for. Maybe we we are looking for words that both begin with “dis” and end with “tion”. Rather than constructing one regular expression that combines these ideas, we could instead construct two simpler regular expressions, one for each part. This is yet another application of the concept of problem decomposition.

Define a function that takes a list of regular expression strings and a list of strings. Return a list of those strings that match all of the regular expressions.

For example, matchesAllREs(["dis[a-z]*$","[a-z]*tion$"],["distinction", "disaster", "disintegration", "ablation"]) should return ["distinction","disintegration"].

• One solution:

  import re
  
  # We need to loop over all the regular expressions and all the strings.
  # We can choose to do so in either order.
  # This is just one possible way of constructing the code.
  
  def matchAll(regexps,strings):
      """Returns all strings that match all regexps."""
      result = []
      for s in strings:
          if matchesAllREs(regexps,s):
              result.append(s)
      return result
  
  def matchesAllREs(regexps,s):
      """Returns whether the string s matches all the regular expressions."""
      for r in regexps:
          if not re.match(r,s):
              return False
      return True
      

• One of the many alternative solutions:

  import re
  
  # A briefer version using a list comprehension for one of the loops.
  
  def matchAll(regexps,strings):
      """Returns all strings that match all regexps."""
      resultStrings = strings
      for r in regexps:
          # Keep only those strings matching this regular expression.
          resultStrings = [s for s in resultStrings if re.match(r,s)]
      return resultStrings
      

Of the following data structures — strings, lists, dictionaries, and tuples — which are mutable and which are immutable?

• We've previously seen that lists and dictionaries are mutable,
  while tuples are immutable.  Strings are also immutable.
      

Why would one choose to use an immutable data structure?

• We've discussed two reasons.  First, you might not ever need or want
  to mutate your data.  Choosing a immutable data type ensures that
  you don't mutate by accident.  Second, only immutable data types
  can be used as dictionary keys.
      

Consider the following simple social network model. A person is a dictionary with the following keys and values: {"Name": aNameString, "Hometown": aHometownString, "Friends": aListOfPersons, "Groups": aListOfGroups}. A Group is a dictionary with the following keys and values: {"Name": aNameString, "Desc": aDescriptionString, "Members": aListOfPersons}. This is a small example of representing a database in Python, using a dictionary for each database “table”, or “entity”.

Write the following functions, utilizing existing functions whenever possible. Ensure that each of the dictionaries' lists never contain duplicate elements.

• makePerson — Returns a person, given a name and hometown.
• makeGroup — Returns a group, given a name and description.
• addFriend — Given a person and a potential friend, it adds the friend to the person if it isn't already a friend.
• mutualAddFriend — Given two persons, it makes them friends of each other.
• unFriend — Given a person and a possible friend, it removes the friend from the person if it is already a friend.
• mutualUnFriend — Given two persons, it makes them not be friends of each other.
• addGroup — Changes a given person to be a member of the given group.
• addMember — Adds a given person to the membership list of a given group.
• joinGroup — Makes a person part of a group, mutating both.
• leaveGroup — Changes a given person to not be a member of the given group.
• removeMember — Removes a given person from the membership list of a given group.
• removeGroup — Makes a person not be part of a group, mutating both.

The idea is that we want to use the code like this:

• john = makePerson("John","Kansas City")
  jeannie = makePerson("Jeannie","Muskogee")
  mutualAddFriend(john,jeannie)
      

• # First, a couple useful helper functions.
  def addToKeyList(d,key,item):
      """Adds item to the dictionary d's key's list.  Assumes that the key is already present."""
      if item not in d[key]:
          d[key].append(item)
  
  def removeFromKeyList(d,key,item):
      """Removes item from the dictionary d's key's list.  Assumes that the key is present."""
      if item in d[key]:
          d[key].remove(item)
  
  # Notice how the functions are built out of smaller functions to keep their code as
  # short, concise expressions of the function's purpose.
  
  def makePerson(name,hometown):
      """Returns a person, given a name and hometown."""
      return {"Name":name, "Hometown":hometown, "Friends":[], "Groups":[]}
  
  def makeGroup(name,description):
      """Returns a group, given a name and description."""
      return {"Name":name, "Desc":description, "Members":[]}
  
  def addFriend(person,friend):
      """Given a person and a potential friend, it adds the friend to the person if it isn't already a friend."""
      addToKeyList(person,"Friends",friend)
  
  def mutualAddFriend(person1,person2):
      """Given two persons, it makes them friends of each other."""
      addFriend(person1,person2)
      addFriend(person2,person1)
  
  def unFriend(person,friend):
      """Given a person and a possible friend, it removes the friend from the person if it is already a friend."""
      if ("Friends" in person) and (friend in person["Friends"]):
          person["Friends"].remove(friend)
  
  def mutualUnFriend(person1,person2):
      """Given two persons, it makes them not be friends of each other."""
      unFriend(person1,person2)
      unFriend(person2,person1)
  
  def addGroup(person,group):
      """Changes a given person to be a member of the given group."""
      addToKeyList(person,"Groups",group)
      
  def addMember(group,person):
      """Adds a given person to the membership list of a given group."""
      addToKeyList(group,"Members",person)
  
  def joinGroup(person,group):
      """Makes a person part of a group, mutating both."""
      addGroup(person,group)
      addMember(group,person)
  
  def leaveGroup(person,group):
      """Changes a given person to not be a member of the given group."""
      removeFromKeyList(person,"Groups",group)
  
  def removeMember(group,person):
      """Removes a given person from the membership list of a given group."""
      removeFromKeyList(group,"Members",person)
  
  def removeGroup(person,group):
      """Makes a person not be part of a group, mutating both."""
      leaveGroup(person,group)
      removeMember(group,person)