Introduction to Computer Science

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):

    assert salary > 0, 'Salary must be greater than 0:' + str(salary)
    assert 0 < save < 100, 'Savings percentage must be between 0 and 100:' + str(savePct)
    assert 0 < epsilon < 1 , 'Upper boundary must be between 0 and 1:' + str(epsilon)

    # Generate the savings record.
    savingsRecord = nestEggVariable(salary, save, preRetireGrowthRates)

    # Savings at retirement will be the last entry;
    # it is also the upper limit on possible expenses.
    savingsAtRetirement = savingsRecord[-1]
    high = savingsAtRetirement
    guess = high # Seed initial guess.
    low = 0.0 # Seed lower guessing limit.
    found = False # Initialize search check.
    count = 1 # Initialize a counter, so search doesn't get out of hand.

    # Upper limit on count protects against process overruns.
    while not found and count < 100:

        # Calculate the fund balance with the current guess.
        fundBalances = postRetirement(savingsAtRetirement, postRetireGrowthRates, guess)
        endingBalance = fundBalances[-1] # Obtain the ending balance for testing.

        # Check to see if it is within episilon on either side of 0.
        if abs(endingBalance) < epsilon:
            found = True
        else:
            # If not, check to see if it's too high or too low.
            if endingBalance < 0:
                # Guess was too high. I need a new guess halfway between
                # the old one and the low.
                high = guess
                guess = (low + high)/2
            else:
                # Guess was too low. I need a new guess halfway between
                # the old guess and the last high.
                low = guess
                guess = (low + high)/2
            count = count + 1
    return guess

# Problem 2: subStringMatchExact (uses find), subStringMatchExact2 (uses rfind),
# subStringMatchExactR (recursivem uses rfind)
def subStringMatchExact( target, key ):
    if key:
        offsets = ()
        offset = target.find( key )
        while offset != -1:
            offsets += offset,
            offset = target.find( key, offset+1 )
    else:
        # A little something he didn't mention: In Problem 3, if the key 
        # is a single letter and key1 or key2 is empty, n+m+1 overrun the last
        # index and won't return it, even though the last index is an
        # acceptable value. Therefore, we have to add an extra index when key
        # is empty. INELEGANT!
        offsets = range(0, len(target)+1 )
    return offsets

def subStringMatchExact2( target, key ):
    if key:
        offsets = ()
        while target.rfind( key ) != -1:
            offsets += (target.rfind( key ),)
            target = target[:target.rfind( key )]
    else:
        offsets = range(0, len(target) )
    return offsets

def subStringMatchExactR( target, key ):
    if key:
        if target.rfind(key) == -1:
            return ()
        else:
            offset = target.find(key) + 1
            return (target.rfind(key),) + subStringMatchExactR(target[:target.rfind(key)],key)
    else:
        return range(0, len(target)+1 )

# Initialize configuration variables ##########################################
packages = 6, 9, 20            # IMPORTANT: order from smallest to greatest!
upper_limit_of_n = 200         # Imposes upper limit on processes.

# Working variables. ##########################################################
terms = len(packages)          # Yeah, we know, but it saves some processes.
x, y, z = packages             # This allows the rest to handle Problem 4, too.

n = 1 # init n
a = 0 # coefficient is x
b = 0 # coefficient is y
c = 0 # coefficient is z

success = 0 # consecutive success counter
stop = 0    # while switch

# OPTIONAL: Derive obvious factors for quick elimination.
# If python thinks smart, sorting will help.
factors = sorted([x, y, z, x+y, y+z, z+x, x+y+z])

while not stop:

    # Initialize solution switch
    has_solution = False

    # OPTIONAL: Weeds out obvious values of n without the combinatorial work.
    # LOGIC: If n is evenly divisible by any of the factors above, it has a
    # solution set. (We don't need to identify that set.)
    if not n%factors[0] or not n%factors[1] or not n%factors[2] or \
       not n%factors[3] or not n%factors[4] or not n%factors[5] or not n%factors[6]:
        has_solution = True

    else:
        # Aargh! No easy way out; brute force, then:

        # Initialize list to hold test ranges.
        ranges = []

        # Don't waste time on values of n < the largest coefficient.
        if n > z:

            # Generate a test range for each term.
            for i in range(0, terms):

                # LOGIC: For each term, the upper limit will be n divided by
                # the coefficient of that term. Proof: a*x + 0*y + 0*z = n =>
                # => a*x = n => n / a = x; x is the upper limit.
                limit =  int( n / packages[i] ) + 1
                i_range = range( 0, limit )
                ranges.append(i_range)

            # Loop through the test ranges.
            for a in ranges[0]:
                for b in ranges[1]:
                    for c in ranges[2]:
                        # Test solution set against n.
                        if (a*x) + (b*y) + (c*z) == n:
                            has_solution = True
                            # No need to look further.
                            break
                    if has_solution:
                        break
                if has_solution:
                    break

    # Check to see if we have a solution.
    if has_solution:

        # If so, increment success count.
        success += 1

    else:
        # If we find a fail, record it and reset the success counter.
        last_fail = n
        success = 0

    # Check success counter. If equal to smallest coefficient
    # we've passed the last failure.
    if success == x:
        stop = 1

    # If not, check to see if we've reached the upper process limit.
    elif n > upper_limit_of_n:
        stop = 1
        last_fail = 0

    # Otherwise, increment n.
    else:
        n += 1

if last_fail == 0:
    print 'Stopped at upper process limit. No max purchase within limit.'
else:
    print 'Largest number of McNuggets that cannot be purchased in exact quantity: '
    print last_fail

# Initialize state variables.
primes = [2]
count = 1
sum_candidates = 0
sum_tests = 0

# Do this until we have 1000 primes
while len(primes) < 1000:

    # Increment counter by 2. (Eliminates all divisible by 2.)
    count += 2

    # Set prime switch true.
    is_prime = True

    # Loop through the testing slice.
    for prime in primes:

        # Check to see if count is prime.
        if count % prime == 0:

            # Not a prime, set switch to false.
            is_prime = False

            # Don't waste any more time on this number.
            break

        # Check for prime limit.
        if prime**2 > count:
            break

    # Check the switch; if it's still true...
    if is_prime:
        #...count is prime. Add it to the primes array.
        primes.append(count)

# print
ordinal = str(len(primes)) + 'th'
print 'The', ordinal, 'prime is', count
print ' '