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

[winterthunder]

Thank you! I'm still working on mine (and probably will be for a while, given the schedule for this week). *does not look at answers yet*

[aranthe]

I did problems 2-4 using iterative solutions, so I'd be especially interested in seeing recursive solutions for those problems.

Okay, 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.

# Problem 2: recursive
def subStringMatchExactR( target, key ):
    if key:
        if target.rfind(key) == -1:
            return ()
        else:
            offset = target.find(key) + 1
            return (target.rfind(key),) + subStringMatchExactR(target[:target.rfind(key)],key)
    else:
        # A little something he didn't mention: In the next step, if the key 
        # is a single letter and key1 or key2 is empty, n+m+1 at the last n
        # overruns the last index, even though the last index is an
        # acceptable value. Therefore, we have to add an extra index when key
        # is empty.
        return range(0, len(target)+1 )

def constrainedMatchPairR( firstMatch, secondMatch, length ):
    if not firstMatch:
        return ()
    else:
        tryK = firstMatch[-1] + length + 1
        if tryK in secondMatch:
            return (firstMatch[-1],) + constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
        else:
            return constrainedMatchPairR(firstMatch[:-1], secondMatch, length)

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

[(Anonymous)]

the programmes which you are put it in the net they are unable to run

[aranthe]

To whom are you addressing these comments? If to me, please note that all solutions are tested prior to posting. These two functions are merely two out of a set of four which must be placed within the 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.

[jetamors]

In order to run these programs, you need to install Python on your computer. There are instructions on how to download it here.