Software Design Spring 2007 For today you should have: 1) read Chapter 11 2) worked on Homework 4 For lab: 1) finish Homework 4 2) read Chapter 12 Exam #1 will be Monday 26 February. Exam #2 will be Monday 2 April. Dictionary methods ------------------ See the attached documentation. As always, when you are using a new method, test it out in isolation before you design a program around it! A few highlights: 1) In addition to keys(), values() and items(), there are also iterkeys(), itervalues() and iteritems(). The difference is that the first three make a new list; the second three make an iterator object that traverses the dictionary. So the latter is a little more efficient, but it if you modify the dictionary, it breaks the iterator. 2) items() returns a list of tuples. You can loop through it: for t in d.items(): k, v = t # tuple assignment Or you can cut out the middle man: for k, v in d.items(): # loopity 3) We have already seen get(), which takes an optional second argument: d.get(k, 0) # return 0 if k is not in d There is also setdefault, which is similar, but different. Here's a common example: d.setdefault(k, []).append(x) If k is not in d, setdefault creates a new empty list, adds it to the dictionary, and returns a reference to it. Dictionaries and Uniqueness --------------------------- A natural use of dictionaries is to check uniqueness. Here is an example from an old quiz: Write a function named has_duplicates that takes a list as a parameter and that returns True if there is any object that appears more than once in the list, and False otherwise. # simple version using only things in the book def has_duplicates(t): d = {} for x in t: if d.has_key(x): return True d[x] = "the value doesn't matter" return False # a version that uses the id function to deal with # non-hashable keys and the in operator def has_duplicates2(t): d = {} for x in t: y = id(x) if y in d: return True d[y] = None return False # a version that uses the set type def has_duplicates3(t): d = set() for x in t: y = id(x) if y in d: return True d.add(y) return False # test all three versions for test in [has_duplicates, has_duplicates2, has_duplicates3]: t = range(10) + list(string.lowercase) print test(t) t.append('a') print test(t) Homework 3 Solutions -------------------- What was the ultra-secret point of Homework 3? 1) design by assembly "How to think" provides a subset of the string operations, but they are sufficient for this. The task is to arrange them into a solution. Sometimes that just means problem recognition: def has_e(word): return 'e' in word def has_no_e(word): return 'e' not in word Other times some assembly is required: def is_tautonym(word): """return True if the word is a tautonym, like beriberi and tomtom""" if len(word)%2: return i = len(word)/2 return word[:i] == word[i:] def is_abecedarian(word): """return True if the letters of the word are in alphabetical order""" for i in range(len(word)-1): if word[i+1] <= word[i]: # strict version: no doubles return False return True 2) our first design pattern, search! Many problems reduce to traversal+search. for x in collection: # traversal if condition(x): # check a condition return True # found it! return False # didn't find it. But sometimes it takes some rearranging to adapt this pattern to a given problem. 1) in avoids, we reverse the sense of the return value 2) in uses_only, we reverse the sense of the condition 3) in uses_all, we traverse the required letters rather than the word def avoids(word, forbidden): """return True if none of the forbidden letters appears in the word""" for c in word: if c in forbidden: return False return True def uses_only(word, available): """return True if the word only contains available letters""" for c in word: if c not in available: return False return True def uses_all(word, required): """return True if all the required letters appear in the word""" for c in required: if c not in word: return False return True 3) An opportunity for recursion: def is_palindrome(word): if len(word) < 2: return True if word[0] != word[-1]: return False middle = word[1:-1] return is_palindrome(middle) 4) another example of interface design A big, complicated function is almost always a sign that there is an opportunity for abstraction. Imagine that you had to present your program at a code review. How would you convince a reader that it is correct? def rotate_word(word, shift=1): """rotate the letters of a word by the given shift amount""" res = '' for c in word: res += rotate_letter(c, shift) return res def rotate_letter(c, shift=1): """rotate a letter by the given shift amount""" if c in string.lowercase: return rotate(c, shift, 'a') elif c in string.uppercase: return rotate(c, shift, 'A') else: return c def rotate(c, shift, base): """rotate a letter by the given shift amount, relative to the given base""" x = ord(c) - ord(base) y = (x + shift) % 26 + ord(base) return chr(y) 4) a first look at Gui layout class Rotate(Gui): def __init__(self): Gui.__init__(self) # init the Gui self.setup() # make widgets def setup(self): # text entries self.fr() self.entry1 = self.en(LEFT) self.entry2 = self.en(LEFT) self.endfr() # label self.label = self.la() # buttons self.fr() self.bu(LEFT, text='Rotate', command=self.rotate_entry) self.bu(LEFT, text='Quit', command=self.quit) self.endfr() def rotate_entry(self): # get the contents of the entries word = self.entry1.get() shift = self.entry2.get() shift = int(shift) # convert string to int # post the result result = rotate_word(word, shift) self.label.configure(text=result) if __name__ == '__main__': r = Rotate() r.mainloop()