Solution to ps3

[jetamors]

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

Comments

python

[(Anonymous)]

Write the function subStringMatchExact. This function takes two arguments: a target string, and a key string. It should return a tuple of the starting points of matches of the key string in the target string, when indexing starts at 0. Complete the definition for

def subStringMatchExact(target,key):
For example,
subStringMatchExact("atgacatgcacaagtatgcat","atgc")
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

[(Anonymous)]

SEND THIS PROGRAM SOLUTION PLEASE