Recursive and iterative nuggets

TrustyTony 0 311 Views

Now that MITx first test is over, I got feeling that this one task requested for generate and test solution is begging also for less efficient recursive solution as it is so simple. Here it is! Single liner aproved by the released grader! If you wander if you are able to buy exactly n nuggets by boxes of 6, 9 or 20 nuggets each, it tells the answer. It does not tell you how heavy your shopping bags would be and how many geeks you need to eat them ;) This recursive version can not deal with 1000000 nuggets (using modulo and nuggets2, you can find that also), but it can tell you that it is possible to get 10001 nuggets. The included iterative count telling version can tell you that it can be manged by 499 twenties, 1 niners and 2 sixes.

def nuggets_counts(n):
    """
    n is an int

    Returns tupple of number of twenties, niners and sixpacks if some integer combination of 6, 9 and 20 equals n
    Otherwise returns empty tupple.
    """
    for twenties in reversed(range(n // 20 +1)):
        left = n - 20 * twenties
        if left == 0:
            return twenties, 0, 0
        for niners in reversed(range(left // 9 +1)):
            left2 = left - niners * 9
            if left2 % 6 == 0:
                return twenties, niners , left2 // 6
    return ()

def nuggets(n):
    """ n int -> True if can be ordered with 6, 9, 20 pack combination else False
    """
    return n >= 0 and (n == 0 or (nuggets(n - 20) or nuggets(n - 9) or nuggets(n - 6)))

def nuggets2(n):
    """ n int -> True if can be ordered with 6, 9, 20 pack combination else False
    """
    return n >= 0 and (any(n % size == 0 for size in (6, 9, 20)) or (nuggets2(n - 20) or nuggets2(n - 9) or nuggets2(n - 6)))

def nug(a,b,c):
    return 6*a + 9*b + 20*c

for t in (60, 15, 16, 19, 18, 10001):
    result = nuggets_counts(t)
    print 'Recursively:', nuggets(t)
    if not result:
        print t, 'not possible but you can'
        t, result = next((t + more, nuggets_counts(t + more)) for more in range(1, 6) if nuggets_counts(t+more))
    print 'buy {t}: {result[0]} twenties, {result[1]} niners and {result[2]} sixpacks.'.format(t=t, result=result)
    print
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview