# Amy Karoline
# Course 600
# Problem Set 3, DNA Sequencing
# Time: ~6.5hours
# 01282011-02012011
######

from string import *

##Problem 1:
##    Write two functions, called countSubStringMatch and
##    countSubStringMatchRecursive that take two arguments, a key string and a
##    target string. These functions iteratively and recursively count the number
##    f instances of the key in the target string. You should complete definitions
##    for
##    def countSubStringMatch(target,key):
##    and
##    def countSubStringMatchRecursive (target, key):
##
##    don't use count function
##    target is big string
##    key is small string

print ''
print 'Problem 1!'
print ''

def countSubStringMatch(target, key):
    ctr = 0
    found = find(target, key)
    while found != -1:
        found = find(target, key, found+1)
        ctr += 1
    return ctr

## You're looking for # of instances of key in target - key is small, target is big

def countSubStringRecursive(target,key):
    foundAt = find(target, key)
    bigLength = len(target)
    smallLength = len(key)
    if foundAt == -1:
        return 0
    nextIndex = foundAt + 1
    return 1 + countSubStringRecursive(target[nextIndex:],key)

big = 'supercalifracalgilistic' #raw_input('key:')
small = 'cal' #raw_input('target:')
print countSubStringMatch(big,small)
print countSubStringRecursive(big,small)  # should return 2

##Problem 2:
##    Use recursive or iterative approaches.
##    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). The file ps3_template.py includes
##        some test strings that you can use to test your function. In particular,
##        we provide two target strings:
##            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.

print ''
print 'Problem 2!'
print ''

def subStringMatchExact(big,small):
    indSolns = ()
    foundAt = find(big, small)
    if foundAt == -1:
        print 'There are no matches. Empty Set:'
        return indSolns
    else:
        while foundAt != -1:
            indSolns += (foundAt,)
            new = foundAt + 1
            foundAt = find(big, small, new)
        return indSolns

a = 'atgacatgcacaagtatgcat'
b = 'atgc'
print subStringMatchExact(a,b)

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'
key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'
print subStringMatchExact(target1, key10)
print subStringMatchExact(target1, key11)
print subStringMatchExact(target1, key12)
print subStringMatchExact(target1, key13)
print subStringMatchExact(target2, key10)
print subStringMatchExact(target2, key11)
print subStringMatchExact(target2, key12)
print subStringMatchExact(target2, key13)


##Problem 3:
##    Near matches of key strings in target strings
##    Write a function, which takes three arguments: a tuple representing starting points for
##    the first substring, a tuple representing starting points for the second substring, and the length
##    of the first substring. The function should return a tuple of all members (call it n) of the first
##    tuple for which there is an element in the second tuple (call it k) such that n+m+1 = k, where m is
##    the length of the first substring.

print ''
print 'Problem 3!'
print ''

def constrainedMatchPair(firstMatch,secondMatch,length):
# firstmatch is a tuple of the starting points for first string matches
# secondmatch is a tuple of the starting points for second string matches
# length is length of the first string, m
# return a tuple of all elements n of the first tuple for which there is an element of the second tuple k
# such that n+m+1 = k and m is the length
# i.e. firstMatch[i] + length + 1 = secondmatch[i]
    matchPairs = ()
    for n in firstMatch:
        k = n + length + 1
        if k in secondMatch:
            matchPairs += (n,)
    return matchPairs

## given function for testing problem 3 from template file
def subStringMatchOneSub(target,key):
    """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
        allAnswers=tuple(set(allAnswers))
    return allAnswers

print subStringMatchOneSub(target1, key10)
print subStringMatchOneSub(target1, key11)


##Problem 4:
##    Write a function, which takes two arguments: a target string and a key string.
##    This function should return a tuple of all starting points of matches of the key to the
##    target, such that exactly one element of the key is incorrectly matched to the target.

print ''
print 'Problem 4!'
print ''

def subStringMatchExactlyOneSub(target,key):
    oneElemOffMatch = ()
    allMatch = subStringMatchOneSub(target, key)
    print 'allmatch is ', allMatch
    exactMatch = subStringMatchExact(target, key)
    print 'exactMatch is ', exactMatch
    for p in range(0, len(allMatch)):
        if allMatch[p] in exactMatch:
            oneElemOffMatch += (allMatch[p],)
    return oneElemOffMatch

print subStringMatchExactlyOneSub(target1, key10)
print subStringMatchExactlyOneSub(target1, key11)

# Amy Karoline
# Course 600
# Problem Set 2, Diophantine Equations - McNuggets
# Time: Problem 1: 3 hrs 15 mins, Problem 2: 45 mins
# Problem 3: 45 mins, Problem 4: 1 hr 30 mins
# 01242011
####

from math import *

## 6a + 9b + 20c = n McNuggets Diophantine equation
##
## Problem 1:
## Show it's possible to buy exactly 50, 51, 52, 53, 54, and 55 McNuggets by
## finding solutions to the Diophantine equation. List the combos of 6, 9, and
## 20 packs of Nuggets you need to buy in order to get each of the exact amounts

a = 0
b = 0
c = 0
n = 0
soln = 0
solns = []
possibleN =[]

# creates lists of possible n values and solutions to the n values
while n <= 55:
    solns.append('nada')
    for a in range(0, n/6+1):
        for b in range(0, n/9+1):
            for c in range(0, n/20+1):
                soln = 6*a + 9*b + 20*c
                if soln == n:
                    if solns[n] == 'nada':
                        solns.insert(n,[a,b,c])
                        possibleN.append(n)
    n += 1
print 'Problem 1:'        
for y in range(50,56):
    print 'For ',y,' nuggets, buy ', solns[y][0],' 6-pack(s), ', solns[y][1],' 9-pack(s), and ', solns[y][2],' 20-pack(s)'

## Then show how, given solutions for 50-55. you can also derive solutions
## for 56-65.
print ''

n=0
soln = 0

for n in range(56,66):
    for z in range(50,56):
        for w in range(1,3):
            if n == 6*w + 6*solns[z][0] + 9*solns[z][1] + 20*solns[z][2]:
                solns.insert(n,[solns[z][0]+w, solns[z][1], solns[z][2]])
                possibleN.append(n)
                
for y in range(56,66):
    print 'For ',y,' nuggets, buy ', solns[y][0],' 6-pack(s), ', solns[y][1],' 9-pack(s), and ', solns[y][2],' 20-pack(s)'

##Problem 2:
##    This theorem is true because the smallest set of McNuggets possible to buy is
##    6. The range from x to x+5 contains 6 sequential values, therefore, every x+n
##    beyond x+5 will be one of the values in the range from x to x+5 plus a multiple
##    of 6.  x+n = 6*z + (one of x to x+5), where z is an integer

##Problem 3: Solving a Diophantine equation
##    Write an exhaustive search to find the largest number of McNuggets that
##    cannot be bought in exact quantity.
##    Mmmm... this is making me crave nuggets.
print ''
print 'Problem 3:'        

a=0
b=0
c=0
n=0
sol=0
consecutiveN = 0        
impossibleN=[]

for n in range(1,200):
    ans=False
    for a in range(0, n/6+1):
        for b in range(0, n/9+1):
            for c in range(0, n/20+1):
                sol = 6*a + 9*b + 20*c
                if sol == n:
                    ans = True
    if ans:
        consecutiveN += 1
        if consecutiveN == 6:
            print 'The largest impossible quantity of McNuggets is: ',impossibleN[-1]
    else:
        impossibleN.append(n)
        consecutiveN = 0


##Problem 4:
##    Use exhaustive search to find the largest number less than 200 of McNuggets
##    that cannot be bought in exact quantity. Sometimes there is not largest value
##    so we have to have the limit of 200 to protect for infinite looping.
print ''
print 'Problem 4:'        

x=1
y=9
z=500

sol=0
consN=0
impN=[]
n=0

packages = (x,y,z)
foundLargest = False

for n in range(1,200):
    ans=False
    for a in range(0, n/packages[0]+1):
        for b in range(0, n/packages[1]+1):
            for c in range(0, n/packages[2]+1):
                sol = packages[0]*a + packages[1]*b + packages[2]*c
                if sol == 1:
                    foundLargest = False
                elif sol == n:
                        ans = True
    if ans:
        consN += 1
        if consN == 6 and packages[0] != 1:
            print 'Given package sizes %d, %d, %d, the largest number of McNuggets that cannot be bought in exact quantity is: %d' % (packages[0], packages[1], packages[2], impN[-1])
            foundLargest = True
    else:
        impN.append(n)
        consN = 0
if not foundLargest:
    print 'There is no largest impossible purchaseable quantity of nuggets under 200 for package sizes ',x,', ',y,', ',z,'.'


        
    


    

# Amy Karoline
# Course 600
# Prob Set 0
# Time: 1 hour
####

lastName = raw_input("Enter your last name:")

firstName = raw_input("Enter your first name:")

print firstName, lastName

# Amy Karoline
# Course 600
# Problem Set 1a & b, Primes
# Prime Numbers are not divisible by anything but 1 and itself
# Time: Part 1: 4.5 hours; Part 2: 1.5 hours
# 01222011
####

from math import *

#Part A
primes = [2] 
x=1000 
testNum = 3 
z=0 

while len(primes) < x :
    notPrime = 0
    divider = 3
    while (divider < (testNum/2)):

        if testNum % divider == 0:
            notPrime = 1
        divider += 1

    if notPrime == 0:
        primes.append(testNum)

    testNum += 2

print primes[x-1]

#Part B

#log(a)x = N means that a^N = x
#log x means log(10)x (common log)
#ln x means log(e)x, e is 2.718... (natural log)

##Rules of logs:
##Inverse: log(a)a^x = x and a^(log(a)x) = x
##Product: log(a)(xy) = log(a)x + log(a)y
##Quotient: log(a)(x/y) = log(a)x = log(a)y
##Power: log(a)(x^p) = p * log(a)x
##Change of base formula: log(a)x = log(b)x/log(b)a

##for sufficiently large n, the product of primes less than n is less than or
##equal to e^n and as n grows, the (product of the primes)/e^n
##gets close to 1

##Write a program that computes the sum of the logarithms of all the primes
##from 2 to some number n, and print out the sum of the logs of the primes,
##the number n, and the ratio of these two quantities. Test this for different
##values of n.

n = None
while not n:
    try:
        n = int(raw_input('Please define n: '))
    except ValueError:
        print 'Invalid Number'

#now compute all primes between 2 and n

primesToN = [2]
testNumB = 3

while testNumB <= n:
    dividerB = 3
    notPrimeB = 0
    
    while dividerB < (testNumB / 2):
        if testNumB % dividerB == 0:
            notPrimeB = 1
        dividerB += 1
        
    if notPrimeB == 0:
        primesToN.append(testNumB)
        
    testNumB += 2

print 'Primes found: ', primesToN


primesCount = 0
logSum = 0

while primesCount < len(primesToN):
    logSum += log(primesToN[primesCount])

    primesCount += 1

print 'logSum: ', logSum
print 'n: ', n
print 'Ratio: ', logSum/n