Geek asks and answers

MIT OCW 6.00 Chicken McNugget program ... again

I spent a little time reading the previous questions / answers about the MIT OpenCourseWare 6.00 task regarding the program for determining the maximum unreachable number of McNuggets smokers in packages 6, 9 and 20. Unfortunately, I find it difficult to integrate these answers into the code that I tried to do myself.

Firstly, here is the actual wording of the problem set that I am trying to write for the code:

... we can write an exhaustive search to find the largest number of McNuggets that cannot be purchased in the exact quantity. The search format should probably follow this outline:
β€’ Hypothesize possible instances of McNuggets numbers that cannot be bought exactly starting at 1
β€’ For each possible instance called n, check if non-negative integers a, b, and c exist such that 6a + 9b + 20c = n. (This can be done by looking at all possible combinations of a, b, and c)
β€’ If not, n cannot be purchased in the exact quantity, with the exception of n β€’ When you find six consecutive n values ​​that actually pass the test for the exact solution, the last answer that was saved (not the last n value in which the solution was) is the correct answer, since you know the theorem that any larger quantity can also be bought in the exact quantity. Write an iterative program that finds the largest number of McNuggets that cannot be purchased in the exact amount. Your program should print the answer in the following format (where instead of (n) the correct number is indicated): "The largest number of McNuggets that cannot be bought in the exact quantity: (n)"
Hint: your program should follow the diagram above.

( , , n , n.)

:

n = 1                                  #set first value for trying to solve the equation
savedn = []                            #list for holding values of n w/ no integer solution
consecutivecount = 0
while consecutivecount < 6:
    for a in range(0,n):
        for b in range(0,n):
            for c in range(0,n):
                if 6*a + 9*b + 20*c == n:
                    consecutivecount += 1
                else:
                    #NOW A MIRACLE HAPPENS!!!
                    consecutivecount = 0      #resets consecutivecount value to zero
                    savedn += [n]             #adds current value of n to list
                n += 1                        #increases value of n to continue test loop
print 'Largest amount of McNuggets that cannot be bought in exact quantity:',str(savedn[-1])+'.'

:

  • , , . / bools, , - . bools? ? , "else".

  • , . , , , , "savedn + = [n]", .

, , , , , . , , , , , .

- , . ( , Python 2.5.)

+3
3

. , " , , " n "McNuggets"? ​​, - :

solution = (0,0,0)
for a in range(0,n):
    for b in range(0,n):
        for c in range(0,n):
            if 6*a + 9*b + 20*c == n:
                solution = (a,b,c)

, , , :

while consecutivecount < 6:
    solution = (0,0,0)
    # ** find a solution like above
    if solution == (0,0,0):
        consecutivecount = 0      #resets consecutivecount value to zero
        savedn += [n]             #adds current value of n to list
    else:
        consecutivecount += 1
    n += 1                        #increases value of n to continue test loop

, n, , consecutivecount, , ( reset consecutivecount). , n.

+1

itertools.product, 3- . ,

from itertools import product, count

v = [6,9,20]
min_v = min(v)
miss = 0

for n in count(1):
    for w in product(range(n), repeat=len(v)):
        if sum(i * j for i, j in zip(v, w)) == n:
            break
    else:
        miss = n
    if n == miss + min_v:
        break

print miss

, , @Joran . , product

from itertools import product, count

v = [6,9,20]
min_v = min(v)
miss = 0

for n in count(1):
    for w in product(*(range(1 + n // i) for i in v)):
        if sum(i * j for i, j in zip(v, w)) == n:
            break
    else:
        miss = n
    if n == miss + min_v:
        break

print miss

,

from itertools import product, count

v = [6,9,20]
min_v = min(v)
miss = 0

for n in count(1):
    for w in product(*(range(0, n + 1, i) for i in v)):
        if sum(w) == n:
            break
    else:
        miss = n
    if n == miss + min_v:
        break

print miss
0

, :

def solution_exists(amt, pieces, i=None):
    """
    Return True if any whole multiples of pieces[:i+1] sum to amt, else False
    """
    if i is None:
        i = len(pieces) - 1   # start with last item
    p = pieces[i]
    if i:
        return any(solution_exists(amt - p*k, pieces, i-1) for k in range(amt // p + 1))
    else:
        return amt % p == 0

def find_max_unbuyable(pieces):
    least = min(pieces)
    n = 0
    last_unsolved = None
    consecutive = 0
    while consecutive < least:
        n += 1
        if solution_exists(n, pieces):
            consecutive += 1
        else:
            last_unsolved = n
            consecutive = 0
    return last_unsolved

def main():
    pieces = [6, 9, 20]
    max_unbuyable = find_max_unbuyable(pieces)
    print("Largest number of McNuggets that cannot be bought in exact quantity: {n}".format(n=max_unbuyable))

if __name__=="__main__":
    main()

find_max_unbuyable ; .

solution_exists ; . , , , (amt // p), (amt - p*k). . , , any True. (i == 0, ) True, p (amt % p == 0).

There are two advantages to writing solution_existsas follows: firstly, it is a more efficient solution (iterate as little as possible, execute the last part as modular division instead of another iteration, short circuit as soon as a solution is found); secondly, since it is recursive, it will be happy to work on an arbitrarily large number of packages.

0
source

More articles:


All Articles