MIT 6.00 Assignments solutions

ps2.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

# for i in range(35, 45):
#     print(i, diophantine(i))

'''
Theorem: If it is possible to buy x, x+1,..., x+5 sets of McNuggets, for some x, then it is
possible to buy any number of McNuggets >= x, given that McNuggets come in 6, 9 and 20
packs.
'''

"""
if x, x+1, x+2, x+3, x+4, x+5,
then x+6 = x + 6
x + 7 = x + 1 + 6
...
x + 11 = x + 5 + 6

x + 12 = x + 6 + 6
...


For this type of problem, if you can find a string of sequential numbers 
that is as long as the smallest counting unit then you can count to any 
subsequent number by adding this smallest counting unit a member of this 
base sequential series. 

"""


def largest(x, y, z):
    n = 1
    count = 0
    k = 0
    largest_not_valid = n
    valid = False
    while n <= 200:

        for a in range(20):
            for b in range(20):
                for c in range(20):
                    if x * a + y * b + z * c == n:
                        valid = True

        if valid:
            count += 1
            if count == x:
                print("Largest number of McNuggets that cannot be bought in exact quantity:" + str(largest_not_valid))
                return None
        else:
            largest_not_valid = n
            count = 0
        valid = False
        n += 1


largest(6, 9, 20)
largest(16, 19, 20)