### 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

## no subject

Date: 2010-02-08 02:28 am (UTC)winterthunder## no subject

Date: 2010-02-12 09:20 pm (UTC)arantheOkay, thanks to accidentally doing the wrong problem set first, it's taken a while, but here are the recursive versions of problems 2 and 3. I don't know if I'll have time to do the fourth one. My next teaching session starts this weekend, and I'm trying to finish a short story for a writing challenge (deadline Sunday), so I'm kind jammed up.

I've tested both of these against my own iterative functions as well as

jetamors's, and they do yield the same results.## python

Date: 2010-06-16 09:49 am (UTC)def subStringMatchExact(target,key):

For example,

subStringMatchExact("

would return the tuple (5, 15).

Here are some test strings that you can use to test your function.

target1 = 'atgacatgcacaagtatgcat' target2 = 'atgaatgcatggatgtaaatgcag'

and four key strings:

key10 = 'a'

key11 = 'atg'

key12 = 'atgc'

key13 = 'atgca'

Test your function on each combination of key and target string, as well as other examples that you create.

## Re: python

Date: 2010-06-17 10:48 am (UTC)## no subject

Date: 2010-06-17 10:07 am (UTC)## no subject

Date: 2010-06-17 01:03 pm (UTC)aranthe`ps3_template.py`

run time environment. As posted, they do not include the`import`

statement required to execute the string functions used, but in context, they produce the same results as the non-recursive versions.## no subject

Date: 2010-06-17 02:21 pm (UTC)jetamors