PS2: Problems 3, 4 » Solution

[aranthe]

When I worked problem 3, I happened to do it in such a way that it also solved problem 4, so I don't have separate solutions for problems 3 and 4.

Also, I added some code that cuts down on the process count by quickly eliminating obvious factors. I've marked this "OPTIONAL" to avoid confusion with the required parts of the script.

PS 2: Problems 3 and 4

# 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