Compsci 6/101, Fall 2011, Lab 7

For this lab you will think about solving some of the APTs due next week.

Turn in this page for your group

Sets

Most of these APTs will use a new Python structure: a set.

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

   3, set([1,2,3])

   2, set(['small','big'])

APT 1: SpeedDial

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 previously as a model, write code that creates a list named saved of how many key-presses are saved for each phone number in numbers -- your 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?

APT 2: AnagramFree

Read the AnagramFree problem statment.

1. 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: foods = ["bagel", "bagel", "cheese", "bagel", "hummus" "onion", "bagel", "onion"] diff =

2. 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']]

3. 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 =

4. Using the techniques from the previous problems write a 2-3 line version of getMaximumSubset. Use set, sorted, join and a list comprehension. def getMaximumSubset(words): return len( )

General Input Functions

Complete the function promptInRange that prompts the user, using the given String prompt, to enter a value until their input is between the given comparable values low and high inclusive. You may assume that the value low is always less than high.

For example, the following code:

generates the output below (assuming the user enters the values in italics below):

   Enter a value between 1 and 10: 8
   The value entered was 8
   Enter another one between 3 and 30: 0.1
   Enter another one between 3 and 30: 31
   Enter another one between 3 and 30: 5.5
   The value entered was 5

Note, that your function should not assume what type of data the user wants to enter (in the example above, int and float values were entered) as long as it is comparable (even lists are comparable!). This is part of what makes the function general. How would verify that the value returned by this function is a specific type that you are looking for (e.g., an int)?