### Solution to ps3

Feb. 7th, 2010 07:35 pm**jetamors**posting in

**intro_to_cs**

As always, please feel free to critique my code, ask questions, or post your own code in the comments. I did problems 2-4 using iterative solutions, so I'd be especially interested in seeing recursive solutions for those problems. Also note that several of these functions call each other, so they need to be placed in the same file.

# ps3 for MIT OpenCourse 6.00 Introduction to Computing # Written by Jetamors, February 2010 from string import * # target strings target1 = 'atgacatgcacaagtatgcat' target2 = 'atgaatgcatggatgtaaatgcag' # key strings key10 = 'a' key11 = 'atg' key12 = 'atgc' key13 = 'atgca' # Problem 1 def countSubStringMatch(target,key): # iterative solution """ This function returns the number of instances of the key in the target string.""" # The strategy here is to look through the entire target and increment every time we find # a match. numinst = 0 # counts the number of instances of the key start = 0 # the index find starts from # print find(target,key) while find(target,key,start) >= 0: numinst += 1 start = find(target,key,start) + 1 # where we start searching again # print numinst, start return numinst def countSubStringMatchRecursive(target,key): # recursive solution """ This function returns the number of instances of the key in the target string.""" # The strategy here is to slice the target every time we find a match, until all # we have left is a string without a match. The number of recursions is the number of # matches. first = find(target,key) if first == -1: return 0 else: return 1 + countSubStringMatch(target[first+1:-1],key) # Problem 2 def subStringMatchExact(target,key): """ This function returns the starting indices of all instances of the key in the target string.""" # This is similar to the iterative solution to problem 1, but here instead of counting the # number of matches, we append the first index of each match to a list. start = 0 # the index find starts from answer= [] # print find(target,key) while find(target,key,start) >= 0: answer.append(find(target,key,start)) start = find(target,key,start) + 1 # where we start searching again # print numinst, start answertuple=tuple(answer) return answertuple # Problem 3 def subStringMatchOneSub(key,target): # this function was provided by the instructor """search for all locations of key in target, with one substitution""" allAnswers = () for miss in range(0,len(key)): # miss picks location for missing element # key1 and key2 are substrings to match key1 = key[:miss] key2 = key[miss+1:] print 'breaking key',key,'into',key1,key2 # match1 and match2 are tuples of locations of start of matches # for each substring in target match1 = subStringMatchExact(target,key1) match2 = subStringMatchExact(target,key2) # when we get here, we have two tuples of start points # need to filter pairs to decide which are correct filtered = constrainedMatchPair(match1,match2,len(key1)) allAnswers = allAnswers + filtered print 'match1',match1 print 'match2',match2 print 'possible matches for',key1,key2,'start at',filtered return allAnswers def constrainedMatchPair(firstMatch,secondMatch,length): """Filter matches to determine which are correct.""" # Here, the strategy is to compare firstMatch to secondMatch to find places where they might # sync up. # print firstMatch # print secondMatch matches = [] for i in range(0,len(firstMatch)): for j in range(0, len(secondMatch)): if secondMatch[j] == firstMatch[i] + length + 1: matches.append(firstMatch[i]) break matchestuple = tuple(matches) return matchestuple # Problem 4 def subStringMatchExactlyOneSub(target,key): """search for all locations of key in target, with exactly one substitution""" # The strategy here is to find all the exact matches, and all the exact matches+near-misses, # and compare them to each other to filter out the exact matches. exactmatch = subStringMatchExact(target,key) allmatch = subStringMatchOneSub(key,target) # all matches and near-matches. You may want to # suppress the print statements in this function! output = [] for i in range(0,len(allmatch)): check = 0 for j in range(0, len(exactmatch)): if exactmatch[j] == allmatch[i]: # the value is only a miss if it's in allmatch and not exactmatch. check = 1 break if check == 0: output.append(allmatch[i]) # print exactmatch # print allmatch outputtuple = tuple(output) return outputtuple