jetamors: Yoruichi is really hot (Default)
[personal profile] jetamors posting in [community profile] 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
From:
Anonymous( )Anonymous This community only allows commenting by members. You may comment here if you're a member of intro_to_cs.
OpenID (will be screened if not on Access List)
Identity URL: 
User (will be screened if not on Access List)
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Links will be displayed as unclickable URLs to help prevent spam.

Profile

Introduction to Computer Science

July 2010

S M T W T F S
    123
45678910
11121314151617
18192021222324
2526272829 3031

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 20th, 2017 07:49 am
Powered by Dreamwidth Studios