jayd

#Problem Set 3a
#jayd
from string import *
def countSubStringMatch(target,key):
    count=0
    while target:
        location=find(target,key)
        if location == -1:
            break
        count += 1
        target=target[location + 1:]
    return count    

print countSubStringMatch("ABXXABXXAB","AB")
#Result = 3

def countSubStringMatchRecursive(target,key):
    location = find(target,key)
    if location == -1:
        return 0
    else:    
        return 1 + countSubStringMatchRecursive(target[location+len(key):],key)   

print countSubStringMatchRecursive("ABXXABXXAB","AB")
#Result = 3   

--------------------------------------------------------------

Problem set 3b
#jayd
from string import *
def subStringMatchExact(target,key):
    matchLocation = []
    start = 0
    while True:
        location = find(target,key,start)
        #break loop if no more matches found
        if location == -1:
            break
        matchLocation.append(location)
        start = location + 1
    return tuple(matchLocation)

    
#TESTS    
targets = ('atgacatgcacaagtatgcat','atgaatgcatggatgtaaatgcag')
keys = ('a','atg','atgc','atgca')
for target in targets:
    for key in keys:
        print "Target: " + target
        print "Key: " + key
        print "Solution: " + str(subStringMatchExact(target,key))    
        
#Output:
# Target: atgacatgcacaagtatgcat
# Key: a
# Solution: (0, 3, 5, 9, 11, 12, 15, 19)
# Target: atgacatgcacaagtatgcat
# Key: atg
# Solution: (0, 5, 15)
# Target: atgacatgcacaagtatgcat
# Key: atgc
# Solution: (5, 15)
# Target: atgacatgcacaagtatgcat
# Key: atgca
# Solution: (5, 15)
# Target: atgaatgcatggatgtaaatgcag
# Key: a
# Solution: (0, 3, 4, 8, 12, 16, 17, 18, 22)
# Target: atgaatgcatggatgtaaatgcag
# Key: atg
# Solution: (0, 4, 8, 12, 18)
# Target: atgaatgcatggatgtaaatgcag
# Key: atgc
# Solution: (4, 18)
# Target: atgaatgcatggatgtaaatgcag
# Key: atgca
# Solution: (4, 18)

------------------------------------------------------------


#Problem set 3d
#jayd
from string import *
#  target strings
target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'
# key strings
key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'
def subStringMatchExact(target,key):
    """Returns a tuple of the exact matches"""
    matchLocation = []
    start = 0
    while True:
        location = find(target,key,start)
        #break loop if no more matches found
        if location == -1:
            break
        matchLocation.append(location)
        start = location + 1
    return tuple(matchLocation)

    
def constrainedMatchPair(firstMatch,secondMatch,length):
    matches=[]
    for match in firstMatch:
        for match2 in secondMatch:
            if match + length + 1 == match2:
                matches.append(match)
    return tuple(matches)
    

def subStringMatchOneSub(target,key):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0,len(key)):
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key',key,'into',key1,',',key2
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        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 subStringMatchExactlyOneSub(target,key):
    """Returns tuple of ONLY partial matches"""
    partialMatch = []
    exactMatch = subStringMatchExact(target,key)
    subMatch = subStringMatchOneSub(target,key)
    for match in subMatch:
        # Check to make sure the value isn't an exact match or already in our list
        if match not in exactMatch and match not in partialMatch:
            partialMatch.append(match)    
    return tuple(partialMatch)
         
matches = subStringMatchExactlyOneSub(target2,key13)
print "The partial only matches are:",matches

#Problem Set 2a: Return the largest unsolvable diophantine equation 
#jayd

def numNuggets(nuggets):
    for numPack20 in range(0,nuggets/20+1):
        #When setting to range it this takes into account the currently selected pack of 20
        for numPack9 in range(0,((nuggets-numPack20*20)/9)+1):
            numPack6=(nuggets-20*numPack20-9*numPack9)/6
            totNuggets = 20*numPack20+9*numPack9 + 6 * numPack6
            if nuggets == totNuggets:
                return True
    return False               
#state varables
n=0
unsolvable=[]
numSolved=0
#Keep solving untill 5 are solved in a row
while numSolved <= 5:
    n+=1
    solved = numNuggets(n)
    if solved == True:
        numSolved+=1
    
    if solved == False:
        numSolved=0
        unsolvable.append(n)
    
print "Largest number of McNuggets that cannot be bought in exact quantity: %i" % unsolvable.pop()
       
#Solution = 43 




#Problem Set 2a
#jayd
#This Function solves the diophantine equation for a tuple of values ordered least to greatest.
def numNuggets(packages,nuggets):
    for large in range(0,nuggets/packages[2]+1):
        #Maximum range takes into account currently selected larger pack
        for medium in range(0,((nuggets-large*packages[2])/packages[1])+1):
            small=(nuggets-packages[2]*large-packages[1]*medium)/packages[0]
            totNuggets = packages[2]*large+packages[1]*medium + packages[0] * small
            #Return True when we find the first soltion
            if nuggets == totNuggets:
                return True
    #When all combinations have been iterated without a solution return false
    return False               

#state varables
n=0
unsolvable=[]
numSolved=0
packsize = (3,7,11)
#Keeps Solving diophantine equations until we have solved at least as many in a row as the smallest pack
while numSolved <= packsize[0]:
    noSolution=False
    n+=1
    #break if no solution found before 200
    if n >= 200:
        noSolution = True
        break
    solved = numNuggets(packsize,n)
    if solved == True:
        numSolved+=1
    
    if solved == False:
        numSolved=0
        unsolvable.append(n)    
if noSolution == False:
    print "Given package sizes %i, %i and %i the largest number of McNuggets that cannot be bought in exact quantity is: %i" % (packsize[0],packsize[1],packsize[2],unsolvable.pop())
else:
    print "Can not find a soltion less than 200"       
 
#Some results from the code
#8,9,20=39
#7,18,23=52
#3,7,11=8


   

#Problem 1 Computing Prime Numbers
#jayd
from math import sqrt
primeNumbers=[2,]    
n=1
#Loop till 1000 primes are generated
while len(primeNumbers) <1000:
    n+=2
    nFactors = 0
    # Loop through all divisors less than the sqrt of n
    for divisor in range(2,int(sqrt(n))+1):       
        remainder = n % divisor
        if remainder == 0: 
            nFactors += 1
    if nFactors == 0: 
        print "Prime Found:",n
        primeNumbers.append(n)  

print "The 1000th prime is:", primeNumbers[999]


#Problem 1 Part 2 Sum of Log(prime) 
#jayd
from math import *
def productOfPrimes(max):
    primeNumbers=[2,]    
    n=1
    #Generate Primes up to a max value
    while primeNumbers[-1] <= max:
        n+=2
        isPrime=True
        # Loop through all divisors less than the sqrt of n (rounded to the nearest int)
        # If a factor is found set isPrime to false and break
        maximum=sqrt(n)
        for divisor in primeNumbers:       
            if divisor > maximum:
                 break
            if n % divisor == 0: 
                isPrime=False
                break 
        if isPrime == True:
            if n < max:
                primeNumbers.append(n)
            else: break
    sumOfPrimes=0
    i=0
    for prime in primeNumbers:
        
        sumOfPrimes+=log(prime)
    print "Sum of Primes:",sumOfPrimes
    ratio=sumOfPrimes/max
    return ratio    

ratio = productOfPrimes(97)
print "Ratio:",ratio

#Problem Set 0
#jayd
lastName = raw_input("Enter your last name:")
firstName = raw_input("Enter your first name:")
print firstName +" "+lastName