Compsci 6/101, Spring 2011, Lab 6

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( )