IN PYTHON import prompt # A decorater for speeding up recursive functions # We will discuss memoize in a later lecture. Don't worry about its meaning/implementation class Memoize: def __init__(self,f): self.f = f self.cache = {} def __call__(self,*args): if args in self.cache: return self.cache[args] else: answer = self.f(*args) self.cache[args] = answer return answer # Computes minimum distance between two words recursively # Use memoization for dynamic programming speedup (explained later in the quarter) @Memoize def min_dist(a : str, b : str) -> int: # Levenshtein distance:: 1 for every addition, deletion, substitution if a == '': return len(b) elif b == '': return len(a) elif a[0] == b[0]: return min_dist(a[1:],b[1:]) else: return 1 + min( min_dist(a[1:],b), min_dist(a,b[1:]), min_dist(a[1:],b[1:]) ) # Same basic result, but allows flip letters to count as 1: so min_dist('abc','bac') == 1 not 2 # if a == '' or b == '': # return len(a)+len(b) # else: # return min(1+min_dist(a,b[1:]), # drop 1st char in b # 1+min_dist(a[1:],b), # drop 1st char in a # (0 if a[0]==b[0] else 1)+ min_dist(a[1:],b[1:]), # same or subst # (1 if a[0:2] == b[1::-1] else 2) + min_dist(a[2:],b[2:]) # flip # ) class Misspelling: # __init__ must call this method so I can test Misspelling more easily. # This method should consist of only new bindings to attribute names. # It should (and will when I grade it) always have a list binding # self.last = some value # You may put your own bindings here using any names to test your code; # when I grade your work, I will replace the contents of this method # but the last binding will always be to the attribute last def initialize_attributes(self): self.amoral = 1 self.more = 2 self.babel = 3 self.last = 4 def __init__(self, fix_when_setting=False): self.fix_when_setting = fix_when_setting self.initialize_attributes() def closest_matches(self,name): pass def __getattr__(self,name): pass # Uncomment when ready to solve this part; otherwise o.a = v does nothing # def __setattr__(self,name,value): # pass # You should try to understand the specifications and test your code # to ensure it works correctly, according to the specification. # You are all allowed to ask "what should my code do..." questions online # both before and after I post my batch self_check file. # The driver below will allow you to easily test your code. if __name__ == '__main__': o = Misspelling(prompt.for_bool("Allow fixing mispelling in __setattr__",True)) # Put code here to test object o the same way each time the code is run # Use the while loop below to type in code one on-the-fly when prompted while True: try: print(" " + str(o.__dict__)) test = prompt.for_string("Enter test") if test == "quit": break; if '=' not in test: print(eval(test)) else: exec(test) except Exception as exc: print(exc) print()

2. (5 pts) Complete the class Misspellings, which should be able to correct the misspelling of attribute names: both for getting the value of an attribute and setting the value of an attribute. See the exact specifications below. The distance_helper module defines a Memoize class and a min_dist function. Leave these definitions exactly as they are. Do not worry what the Memoize class does nor how it works: we will study it in a few weeks. Do not worry how the min_dist function works, but understand that it recursively computes the minimum distance between two strings. The more dissimilar the strings, the bigger the value it returns. The distance between strings increases by 1 for every addition, deletion, or substitution it takes to convert one string into the other. For example min_dist ("able", "camel") is 4: to transform "able" into "camel" we can add a c at the front, substitute an m for a b, add an e between the m and 1, and delete the e at the end Going the other way, we can delete the c at the front, substitute a b for an m, add an 1 between the m and e, and delete the 1 at the end. There are other ways to convert in 4 changes, but no ways to do it in 3: so 4 is the minimum distance. The _init_method in Misspelling has a parameter (whose default value is False) that is used to set the fix_when_setting attribute (see below for how this attribute is used). It calls initialize_attributes to initialize the attribute names that may be misspelled in tests. For testing purposes, this is easier to do outside of _init__. You can change the inside of either method, but __init_must call initialize_attributes as its last statement. 1. Write a method named closest_matches; its parameters are self (an object from the class Misspelling) and name (a str); it returns a list of all the attribute names in that Misspelling object that have the same minimum distance from name, so long at that minimum distance is