Supplementary exercises

The primary purpose of these exercises is to give you more practice on some of the topics we've been covering, especially problem decomposition, algorithm development, and using dictionaries.

When discussing substitution ciphers, a couple students asked about generalizing such ciphers. The following exercises are based upon that idea.

Assume you have a dictionary that maps items to list of items. We don't care what kinds of items these are. For example, {"a": [1,2,3], "b":[2,4,5], "c":[3,5], "d": [1,6,2]}. What we want is to “reverse” the mapping, in the sense illustrated by the following desired result: {1: ["a","d"], 2:["a","b","d"], 3:["a","c"], 4:["b"], 5:["b","c"], 6:["d"]}. Note that the output has the same form as the input.

We can break the overall problem down into smaller pieces. We need to be able to “reverse” one key/value pair, e.g., "a":[1,2,3}, and do that repeatedly. In order to do that, we need to be able to “reverse” each key/item-from-value-list pair, e.g., "a" and 1, and do that repeatedly.

Turn the above idea into pseudo-code for this problem.

• reverseMapping:
      Given a mapping {k1:[v1,v2,...], ...} return its inverse mapping, {v1:[k1,...], v2:[k1,...], ...}.
  
      mapping = empty dictionary
      For each key/list-of-values pair,
          Add the reversed key/list-of-values pair bindings to mapping.
  
      Return mapping
  
  reverseKeyListofValues:
      Given a dictionary, {v1:[k1,...], v2:[k1,...], ...}, a key kn, and a list of values [vm,...], add the inverted key/value mappings to the dictionary.
  
      mapping = the input dictionary
      For each value in the list-of-values,
          Add the reversed key/value pair binding to the mapping.
  
  reverseKeyValue:
      Given a dictionary, {v1:[k1,...], v2:[k1,...], ...}, a key kn, and a value vm, add the inverted key/value mapping to the dictionary.
  
      mapping = the input dictionary
      If vm is already a key in mapping,
          Add kn to vm's list in mapping
      Otherwise,
          Add the mapping vm:[kn] to the mapping
      

Write the corresponding Python code.

• def reverseMapping(mapping):
      Given a mapping {k1:[v1,v2,...], ...} return its inverse mapping, {v1:[k1,...], v2:[k1,...], ...}.
  
      resultMapping = {}
      for key,values in mapping.items():
          reverseKeyListofValues(resultMapping,key,values)
  
      return resultMapping
  
  def reverseKeyListofValues(mapping,key,values):
      Given a dictionary, {v1:[k1,...], v2:[k1,...], ...}, a key kn, and a list of values [vm,...], add the inverted key/value mappings to the dictionary.
  
      for value in values:
          reverseKeyValue(mapping,key,value)
  
  def reverseKeyValue(mapping,key,value):
      Given a dictionary, {v1:[k1,...], v2:[k1,...], ...}, a key kn, and a value vm, add the inverted key/value mapping to the dictionary.
  
      if value in mapping:
          mapping[value].append(key)
      else:
          mapping[value] = [key]