Compsci 6/101, Spring 2012, Lab 6

For this lab you'll think about solving some of the APTs due next week some of which will use a new Python structure: a set.

    SpeedDial

    Read the SpeedDial problem statement (a handout for this lab).

    Put answers on handin page.

  1. First solve one of the problem instances by hand/paper-pencil. What value should be returned by the call assignNumbers(numbers,howMany,slots) for the values below? Show how you determined the answer. numbers = [1111,123456,654321,1234567,7654321,123456789,111222,2222] howMany = [3,4,5,8,7,2,2,3] slots = 4
  2. Write code using the function sum, list comprehensions, and the enumerate loop (e.g., for i,val in enumerate(numbers) that calculates the total number of keypresses needed when there are no speed-dial slots. Ideally you'll write one line as below, but more than one is ok if that helps you think about the problem. It will likely help to convert integer values to string values using str, e.g., str(123) = "123" because you can use the len function with strings. total = sum([ ])
  3. Suppose a six digit number like "123456" is dialed 12 times. If this number is put into a speed-dial slot, how many key-presses are saved? Note that with no speed-dial slots 72 key-presses are needed.

  4. Using the list comprehension/code you wrote for the problem before the last one (sum, str, enumerate) as a model, write code that creates a list named saved of how many key-presses are saved for each phone number in numbers -- you code should result in saved[i] having the value of how many key-presses are saved when numbers[i] is dialed howMany[i] times. saved =
  5. Which of the values in the list saved created in the previous problem represent numbers that should be put in speed-dial slots? Why?
  6. Using a slice and list functions such as sorted, max, sum, min, etc. write an expression that stores the number of key-presses saved in a variable named saved_presses using the list saved created above. It may help to remember that a negative index in a slice accesses list-elements from the end so that, for example, [1,2,3,4,5][-2:] evaluates to the list [4,5] by "slicing" the last two elements. saved_presses =
  7. What's left to solve this APT -- write the last steps on the handin pages.

    AnagramFree

    Read the AnagramFree APT -- this part of the lab suggests a new Python construct, a set, that makes solving the APT simpler.

    In Python a set does not store duplicates, each value is only stored once. For example, the code below generates the output shown:

    x = set([1,2,3,1,2,3,1,2,3,1,1,1]) print len(x), x Output is: 
      3, set([1,2,3])
    A set can be created from a list as shown, and elements can be added to the set using the set method .add, e.g., s = set() s.add("big") s.add("big") s.add("big") s.add("small") s.add("small") print len(s),s will generate 
       2, set(['small','big'])

  8. Write an expression that determines the number of different strings in the list foods below, e.g., that sets diff to have the value 4, but will work even if the values in food change (answer on handin pages): foods = ["bagel", "bagel", "cheese", "bagel", "hummus" "onion", "bagel", "onion"] diff =
  9. For a string s, the value of sorted(s) is a sorted list of the individual characters in the string, e.g., sorted("apple") = ['a','e','l','p','p']

    What's the value of the list comprehension below (write it out) --- you should have a list of lists:

    [sorted(w) for w in ['cow', 'dog', 'ant', 'bat']]
  10. The string method join creates a string from a list of strings as shown below.

    method call result
    ''.join(["a", "r", "t"]) "art"
    ' '.join(["the","big", "dog", "runs"]) "the big dog runs"

    The string to the left of the dot '.' is inserted between each string in the list that's a parameter to the join method and one string is returned as shown. In the first call above an empty string '' is inserted, in the second a space ' ' is inserted.

    Using sorted and join write a list comprehension to create in unique the sorted string version of each string in words, e.g., to create ["aet", "aet", "aet", "abt", "abt", "deo" "deo"] out of the list ["eat", "aet", "tea", "bat", "tab", "ode", "doe"]

    words = ["eat", "aet", "tea", "bat", "tab", "ode", "doe"] unique =
  11. Using the techniques from the previous problems write a one line version of getMaximumSubset for the AnagramFree APT. Use set, sorted, join and a list comprehension. If you can't do it one line, use more than one. def getMaximumSubset(words): return len( )

    MemberCheck

    You'll look at the APT MemberCheck

    The union of two sets A and B is the elements that are in A together/combined with the elements in B. The union is a set, so there are no duplicates. The vertical bar | is the set-union operator in Python: 

      set([1,2,3]) | set([2,3,4,5]) == set([1,2,3,4,5])

    To solve this APT consider the list comprehension below:

    cheats1 = [x for x in club1 if x in club2 or x in club3]
  12. In words(on the handin pages) describe the contents of the list referenced by variable cheat1

  13. On the handin pages write two more list comprehensions that interchange the roles of the three clubs so that there are three list variables cheat1, cheat2, and cheat3 that represent similar lists for the three clubs.

  14. A set can be created from a list using x = set(lst), and the union operator | combines sets just as the addition operator + adds integers or concatenates strings, e.g., the expression below stores the union of three sets in a variable w. w = x | y | z

    The sorted function returns a sorted list from any Python sequence, e.g., a list a string or a set. Write one line using sorted, the three lists created in the previous problem, and set operators to return the correct value for the APT. 

      return sorted(......)