Introduction to Computer Science

def nestEggFixed(salary, save, growthRate, years):

    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 < growthRate < 100, 'Growth rate must be greater than 0:' + str(growthPct)
    assert years > 0, 'Years must be greater than 0:' + str(years)

    savingsRecord = [] # Initialize savings list.

    # Add one to years to capture last year.
    for year in range( 1, years+1 ):

        # First year is different.
        if( year == 1 ):
            savingsRecord.append( salary * save * 0.01 )
        else:
            # savingsRecord[-1] is the savings at the end of the last year.
            savingsRecord.append( savingsRecord[-1] * (1 + 0.01 * growthRate) + salary * save * 0.01 )
    return savingsRecord

def nestEggVariable(salary, save, growthRates):

    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)

    savingsRecord = [] # Initialize savings list.
    years = len(growthRates) # Compute number of years from input variable.
    
    # Add one to years to capture last year.
    for year in range( 1, years+1 ):
        
        # First year is different.
        if( year == 1 ):
            savingsRecord.append( salary * save * 0.01 )
        else:
            # savingsRecord[-1] is the savings at the end of the last year.
            savingsRecord.append( savingsRecord[-1] * (1 + 0.01 * growthRates[year-1]) + salary * save * 0.01 )
    return savingsRecord

def postRetirement(savings, growthRates, expenses):

    assert savings > 0, 'Savings must be greater than 0:' + str(savings)

    fundBalances = [] # Initialize fund list.
    years = len(growthRates) # Compute number of years from input variable.
    
    # Add one to years to capture last year.
    for year in range( 1, years+1 ):
        
        # First year is different.
        if( year == 1 ):
            fundBalances.append( savings * (1 + 0.01 * growthRates[year-1]) - expenses )
        else:
            # fundBalances[-1] is the fund at the end of the last year.
            fundBalances.append( fundBalances[-1] * (1 + 0.01 * growthRates[year-1]) - expenses )
    return fundBalances

# 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