4orty4

# Problem Set 3
# Name: 4orty4
# Time: 5:00
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):
    """Iteratively counts matches in the string"""
    i = 0 # tracks the postion of the slice
    n = 0 # tracks the number of matching results found
    while i < len(target):
        j = find(target[i:], key) #tracks position of match relative to slice
        if j == -1:
            print 'Search Complete'
            return n
        else:
            n += 1 #found match, add 1 to match counter
            print 'Match ', n, 'found at position ', j+i #j+i = slice position + relative match position
            i += j+1
    print 'Error'
    return None


def countSubStringMatchRecursive(target, key):
    """Recursively counts matches in the string"""
    n = 1
    i = find(target, key)
    print i
    if i == -1: #if no matches are found
        return 0
    else:
        n += countSubStringMatchRecursive(target[i+1:], key)
        return n

# Problems 2, 3 and 4
def subStringMatchExact(target,key):
    """Returns a tuple of the starting points of matches
    in the target string"""
    i = 0 # tracks the postion of the slice
    sols = () # Creates an empty tuple to return after search
    # Special case if the function is sent an empty string as key
    # Returns a tuple with all numbers 0-length of target
    if key == '': return tuple(range(len(target1)))
    while i < (len(target)+1):
        j = find(target[i:], key) #tracks position of match relative to slice
        if j == -1:
            # print 'Search Complete'
            return sols
        else:
            sols +=(j+i,) #adds slice location to solution tuple
            i += j+1

def constrainedMatchPair(firstMatch,secondMatch,length):
    """The function is given two tuples representing starting points 
    of two searches for a search string.  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."""
    ans = ()
    for n in firstMatch:
        matchTest = n + length + 1
        for k in secondMatch: #searches for a matching k value in the second tuple
            if k == matchTest: ans += (n,)
    return ans

#Target and key were reversed from the template 
#for consistency with other functions
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 allAnswers
        print 'match1',match1
        print 'match2',match2
        print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers

def removeDup(t):
    """Scans a tuple of integers and returns a new tuple
    with duplicate integers removed"""
    
    r = ()
    for i in range(0, len(t)):
        isMatch = False
        for j in range(i+1, len(t)):
            # print 't[i], t[j] = ', t[i], t[j]
            if t[i] == t[j]: 
                isMatch = True
        # print isMatch
        if isMatch == False: 
            r+=(t[i],)
            # print 'writing unique answer'
    return r

def removeExactFromAll(exactMatches, allMatches):
    """Receives two tuples of integers. Creates and returns a tuple of
    substitution matches that contains integers from allMatches not 
    included in exactMatches"""
    subMatches = ()
    for i in range (0, len(allMatches)):
        isMatch = False
        for j in range (0, len(exactMatches)):
            if allMatches[i] == exactMatches[j]:
                isMatch = True
        if isMatch == False:
            subMatches += (allMatches[i],)
    return subMatches


def subStringMatchExactlyOneSub(target, key):
    """Returns a tuple representing the starting point 
    of matches with one substitution. It is produced by comparing
    tuple containing the locations of exact matches with the 
    tuple containing location of substitution+exact matches,
    and leaves only the substitution matches."""
    
    #Get location of exact matches
    exactMatches = subStringMatchExact(target,key)
    
    #Get location of sub matches + exactMatches
    allMatches = subStringMatchOneSub(target, key)
    
    #Remove duplicate answers from allMatches
    allMatches = removeDup(allMatches)
    print '    Exact matches are at ', exactMatches
    print '    Substitution matches are at ', allMatches
    
    return tuple(sorted(removeExactFromAll(exactMatches, allMatches)))

x = key12
y = target2
answer = subStringMatchExactlyOneSub(target2, key13)
print 'Searched for ', x, 'in ', y
print 'Substitution matches are located at ', answer

# Lesson 3 Problems 1-4
# Name: 4orty4
# Time: 4:00


##                Problem 1
## 7 * 3   +   9 * 1   +   20 * 1   ==   50
## 7 * 6   +   9 * 1   +   20 * 0   ==   51
## 7 * 1   +   9 * 5   +   20 * 0   ==   52
## 7 * 2   +   9 * 2   +   20 * 1   ==   52
## 7 * 5   +   9 * 2   +   20 * 0   ==   53
## 7 * 0   +   9 * 6   +   20 * 0   ==   54
## 7 * 1   +   9 * 3   +   20 * 1   ==   54
## 7 * 2   +   9 * 0   +   20 * 2   ==   54
## 7 * 4   +   9 * 3   +   20 * 0   ==   55

##              Problem 2
## For package sizes 6,9 and 20 six consecutive
## solutions prove that any higher number can
## also be purchased, because any combination can
## be increased by six by adding an additional
## package of six. For different package sizes,
## (n) consecutive solutions must be found, where
## (n) = the size of the smallest package.

##             Problems 3 and 4
## Solution condensed into one program. Tuple 'packages'
## can be changed to any other non-zero package sizes,
## provided the smallest package is listed first.

# packages[1]*x + packages[2]*y + packages[3]*z = n
# This program will find the highest whole number <200
# that can be purchased given the package sizes.

# Change package size by changing these values
# Smallest package size must be entered first for the program
# to function correctly
packages = (6,9,20)

#initialize values
total = 0
x, y, z = 0, 0, 0
n=0
solCounter = 0
isSolFound = 0
bestSoFar = 0

# For each x, y and z all values are tested between 0 and (n/package size + 1)

for n in range (1, 200):
    for x in range (0, (n/packages[0]+1)): 
        for y in range(0, (n/packages[1]+1)):
            for z in range(0, (n/packages[2]+2)):
                total = packages[0]*x + packages[1]*y + packages[2]*z
                if total == n:
                    print packages[0],'*',x,'  +  ',packages[1],'*',y,'  +  ',packages[2],'*',z,'  ==  ',total
                    isSolFound = 1
    #the loop continues even if a solution is found
    #not ideal but not sure how to break out of all 3 for loops
    #at once.

    if isSolFound == 1:
        solCounter += 1
        isSolFound = 0
    else:
        solCounter = 0
        bestSoFar = n # Stops when consecutive solutions = smallest package size
    if solCounter == packages [0]:
        break #breaks the loop so it doesn't have to try all 200 n's

print 'Package sizes are', packages[0], packages[1],'and', packages[2]               
print 'Largest number that can not be bought in exact quantity:', bestSoFar

# Problem Set 1
# Problem 1
# Name: 4orty4
# Time: 2:00

# This program will calculate the 1000th prime number.
# 2 is the first prime number.

# First I need to generate odd numbers to test, since
# all primes except 2 are odd.  This means that I will
# begin the prime counter at 1

# A positive number, x, is prime if:
# x/n=(int) only where x=n (n>1)
# or x%n=0 only where x=n (n>1)

candidate = 1 # 3 will be the first tested number
divisor = 2 
primecounter = 1 
# initial state for number of primes found (because 2 already known prime)
# +1 for each prime found, up to 1000

while primecounter < 1000:
    candidate = candidate + 2 # The next odd number is tested
    divisor = 2
    isnotprime = 0 #this will flip to 1 if a divisor is found
    while divisor <= (candidate/2) and isnotprime == 0:  
        if candidate%divisor == 0:
            isnotprime = 1 #a divisor is found so this while statement stops
        else:
            divisor = divisor + 1 #the loop is tried with a new divisor

        # The while loop continues until either the largest allowable divisor
        # has been tried, or the candidate is proven to not be prime.
        
    if isnotprime == 0: # 0 result means the number is prime
        primecounter = primecounter + 1
    

print 'The 1000th prime number is', candidate


# Problem Set 1
# Problem 2
# Name: 4orty4
# Time: 1:00

# This program will calculate the sum of the natural logs
# of all primes less than n.
# It will print n, the sum, and the ratio of sum/n
# It differs from the first part of the assignment
# because the caluclation stops when the prime is less
# than a given number, rather than stopping when the 1000th
# prime number is found.

from math import *
n = int(raw_input('Select n: the maximum value of the last prime:'))
# Converts input from str to int

logsum = log(2) # Initializes the logsum value to the log of 2
candidate = 1 # 3 will be the first number tested
divisor = 2 # first divisor to test is 2
primecounter = 1 # 2 already known as prime

while candidate < n: # Loop stops when 
    candidate = candidate + 2 # The next odd number is tested
    divisor = 2 #reset divisor to 2
    isnotprime = 0 #this will flip to 1 if a divisor is found
    while divisor <= (candidate/2) and isnotprime == 0:  
        if candidate%divisor == 0:
            isnotprime = 1 #a divisor is found so this while statement stops
        else:
            divisor = divisor + 1 #the loop is tried with a new divisor
        
    if isnotprime == 0: # 0 result means the number is prime
        logsum = logsum + log(candidate)
        ##primecounter = primecounter + 1

        
print 'The n you selected is', n,'\n'
print 'The sum of the logarithms for all primes less than',n,'is',logsum,'\n'
print 'The ratio of the sum to n is',logsum/n

# Problem Set 0
# Name: 4orty4
# Collaborators: NA
# Time: 0:15
# 

lastname = raw_input('What is your last name?')

firstname = raw_input('What is your first name?')

print 'Your name is', firstname, lastname

exit = raw_input('Press \'Return\' key to quit')