### PS2: Problems 3, 4 » Solution

Apr. 8th, 2010 01:19 pm**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