jyen

# Problem Set 4
# Name: jyen
# Time: 1 hour

#
# Problem 1
#

def nestEggFixed(salary, save, growthRate, years):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: the annual percent increase in your investment account (an
      integer between 0 and 100).
    - years: the number of years to work.
    - return: a list whose values are the size of your retirement account at
      the end of each year.
    """
    savings = [salary * save * .01]
    for n in range (1, years):
        year = (savings[n - 1] * (1 + .01 * growthRate) + (salary * save * .01))
        savings.append (year)
    return savings

def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 15
    years      = 5
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]

    # TODO: Add more test cases here.

#
# Problem 2
#

def nestEggVariable(salary, save, growthRates):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
    """
    savings = []
    year = 0
    for rate in growthRates:
        year = year * (1 + .01 * rate) + (salary * save * .01)
        savings.append(year)
    return savings

def testNestEggVariable():
    salary      = 10000
    save        = 10
    growthRates = [3, 4, 5, 0, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]

    # TODO: Add more test cases here.

#
# Problem 3
#

def postRetirement(savings, growthRates, expenses):
    """
    - savings: the initial amount of money in your savings account.
    - growthRate: a list of the annual percent increases in your investment
      account (an integer between 0 and 100).
    - expenses: the amount of money you plan to spend each year during
      retirement.
    - return: a list of your retirement account value at the end of each year.
    """
    funds = []
    year = savings
    for rate in growthRates:
        year = year * (1 + .01 * rate) - expenses
        funds.append(year)
    return funds

def testPostRetirement():
    savings     = 100000
    growthRates = [10, 5, 0, 5, 1]
    expenses    = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord
    # Output should have values close to:
    # [80000.000000000015, 54000.000000000015, 24000.000000000015,
    # -4799.9999999999854, -34847.999999999985]

    # TODO: Add more test cases here.

#
# Problem 4
#

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - preRetireGrowthRates: a list of annual growth percentages on investments
      while you are still working.
    - postRetireGrowthRates: a list of annual growth percentages on investments
      while you are retired.
    - epsilon: an upper bound on the absolute value of the amount remaining in
      the investment fund at the end of retirement.
    """
    savings = nestEggVariable(salary, save, preRetireGrowthRates)
    nestegg = savings[-1]

    low = 0
    high = nestegg
    finalBalance = nestegg

    while abs(finalBalance) > epsilon:
        expenses = (high + low) / 2.0
        print 'Testing for expenses at ', expenses
        finalBalance = postRetirement(nestegg, postRetireGrowthRates, expenses)[-1]
        print 'Final balance is ', finalBalance
        if finalBalance > 0:
            low = expenses
        else:
            high = expenses
    return expenses
        
def testFindMaxExpenses():
    salary                = 10000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    # Output should have a value close to:
    # 1229.95548986

    # TODO: Add more test cases here.

# Set 3
# jyen

from string import *

def countSubStringMatch (target, key):
    """ Iteratively counts the number of times a term appears in a string"""
    count = 0
    place = 0
    while find(target, key, place) != -1:
        place = find(target, key, place) + 1
        count += 1
    return count

def countSubStringMatchRecursive (target, key):
    """ Recursively counts the number of times a term appears in a string"""
    if find(target, key) != -1:
        return 1 + countSubStringMatchRecursive(target[find(target, key)+1:], key)
    return 0

def subStringMatchExact (target, key):
    """Iteratively finds the locations where a term appears in a string"""
    places = []
    index = 0
    while find(target, key, index) != -1:
        places.append(find(target, key, index))
        index = find(target, key, index) + 1
    return tuple(places)

 
def constrainedMatchPair (firstMatch, secondMatch, length):
    places = ()
    for x in firstMatch:
        for y in secondMatch:
            if x + length + 1 == y:
                places += (x,)
    return places

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
    return allAnswers
        
def subStringMatchExactlyOneSub (target, key):
    nearmatches = ()
    exactmatches = subStringMatchExact(target, key)
    allmatches = subStringMatchOneSub(target, key)
    for x in allmatches:
        if x not in exactmatches:
            nearmatches += (x,)
    return nearmatches

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'

print countSubStringMatch(target1,key12)
print countSubStringMatchRecursive(target1,key12)
print subStringMatchExact(target2,key12)
print subStringMatchOneSub(target2, key12)
print subStringMatchExactlyOneSub(target2, key12)

# Problem Set 2
# jyen
# 1 hour

# Problem 1
# 50 = 6(5) + 9(0) + 20(1)
# 51 = 6(1) + 9(5) + 20(0)
# 52 = 6(2) + 9(0) + 20(2)
# 53 = 6(1) + 9(3) + 20(1)
# 54 = 6(9) + 9(0) + 20(0)
# 55 = 6(1) + 9(1) + 20(2)
# 56 = 50 + 6(1)
# 57 = 51 + 6(1)
# 58 = 52 + 6(1)
# 59 = 53 + 6(1)
# 60 = 54 + 6(1)
# 61 = 55 + 6(1)
# 62 = 56 + 6(1)
# 63 = 57 + 6(1)
# 64 = 58 + 6(1)
# 65 = 59 + 6(1)

# Problem 2
# The theorem is true because x+5 and x+6(1) are contiguous. We can then continue indefinitely: x + (1 ...) + 6(1).   However, only when x is sufficently large so x...x+5 is contiguous.

# Problem 3

candidatenumber = 1
satisfied = 0
while satisfied <6:
    if candidatenumber%6 == 0 or candidatenumber%9 == 0 or candidatenumber%20 == 0:
        satisfied += 1
        #print "Candidate: ", candidatenumber, " is divisible by 6, 9 or 20"
    else:
        solved = 0
        c = 0
        while solved == 0 and candidatenumber > 20*c:
            a = 0
            b = 0
            while solved == 0 and candidatenumber > 9*b + 20*c:
                a = 0
                while solved == 0 and candidatenumber > 6*a + 9*b + 20*c:
                    #print candidatenumber, a, b, c
                    if (candidatenumber - (6*a) - (9*b) - (20*c))%6 == 0 or (candidatenumber - (6*a) - (9*b) - (20*c))%9 == 0 or (candidatenumber - (6*a) - (9*b) - (20*c))%20 == 0:
                        solved = 1
                        #print "Candidate: ", candidatenumber, " solved by ", a, b, c
                    a += 1
                b +=1
            c += 1
        if solved == 1:
            satisfied +=1
        else:
            satisfied = 0
            #print "Candidate: ", candidatenumber, " not solved."
    candidatenumber += 1

print "The largest number of McNuggets that cannot be bought in exact quantity is ", candidatenumber - 7

#problem 4

candidatenumber = 1
satisfied = 0
packages = (6, 9, 20)

while satisfied <6 and candidatenumber <= 200:
    if candidatenumber%packages[0] == 0 or candidatenumber%packages[1] == 0 or candidatenumber%packages[2] == 0:
        satisfied += 1
        #print "Candidate: ", candidatenumber, " is divisible by a package size"
    else:
        solved = 0
        c = 0
        while solved == 0 and candidatenumber > packages[2]*c:
            a = 0
            b = 0
            while solved == 0 and candidatenumber > packages[1]*b + packages[2]*c:
                a = 0
                while solved == 0 and candidatenumber > packages[0]*a + packages[1]*b + packages[2]*c:
                    #print candidatenumber, a, b, c
                    if (candidatenumber - (packages[0]*a) - (packages[1]*b) - (packages[2]*c))%packages[0] == 0 or (candidatenumber - (packages[0]*a) - (packages[1]*b) - (packages[2]*c))%packages[1] == 0 or (candidatenumber - (packages[0]*a) - (packages[1]*b) - (packages[2]*c))%packages[2] == 0:
                        solved = 1
                        #print "Candidate: ", candidatenumber, " solved by ", a, b, c
                    a += 1
                b +=1
            c += 1
        if solved == 1:
            satisfied +=1
        else:
            satisfied = 0
            #print "Candidate: ", candidatenumber, " not solved."
    candidatenumber += 1

if candidatenumber <= 200:
    print "The largest number of McNuggets that cannot be bought in exact quantity is ", candidatenumber - 7
else: print "No solution found - max limit reached."

# problemset 1
# Jyen
# Time 30 min


#problem 1
n = 1000
primescount = 1
candidatenumber = 3

while primescount < n: #evaluate until Nth prime found
    test = 3
    if candidatenumber%2 > 0: 
        while candidatenumber%test>0 and test < candidatenumber/2:
            test = test + 1
        if candidatenumber%test>0 or candidatenumber == test: 
            # print candidatenumber
            primescount = primescount + 1
    candidatenumber = candidatenumber + 1

print "Part 1: The 1,000th prime is ", (candidatenumber - 1)

# problem 2
from math import *
stringinput = raw_input ("How many numbers? ")
n = int(stringinput)
sumoflogs = 0
primescount = 1
candidatenumber = 3

print "Part 2:"
while primescount < n:
    test = 3
    if candidatenumber%2 > 0:
        while candidatenumber%test>0 and test < candidatenumber/2:
            test = test + 1
        if candidatenumber%test>0 or candidatenumber == test:
            sumoflogs = sumoflogs + log(candidatenumber)
            #print sumoflogs
            primescount = primescount + 1
    candidatenumber = candidatenumber + 1
print "Sum of the logs of the primes = ", sumoflogs
print "N = ", n
print "Ration sumoflogs/N =", (sumoflogs/n)

# Problem Set 0
# Name: Jyen
# Time: 5 mins

lname = raw_input("Enter your last name:")
fname = raw_input("Enter your first name:")
print fname + " " + lname