Solving a Diophantine

Question

I was given the task to solve the graded Diophantine problem. McDonald’s sells Chicken McNuggets in packages of 6, 9 or 20 McNuggets. Thus, it is possible, for example, to buy exactly 15 McNuggets (with one package of 6 and one package of 9), but it is not possible to buy exactly 16 nuggets, since no non-negative integer combination of 6’s, 9’s and 20’s adds up to 16. To determine if it is possible to buy exactly n McNuggets, one has to solve a Diophantine equation: find non-negative integer values of a, b, and c, such that

6a + 9b + 20c = n.

Write a function buy_nuggets() that takes a number (n) as an argument and returns tuple of four numbers which are; the total number of packages, the number of packages of 6 nuggets, the number of packages of 9 nuggets and the number of packages of 20 nuggets that are needed to sell n number of nuggets. If the combination of nuggets cannot be made then it returns a tuple of four zeros i.e. (0,0,0,0).

Note that there can be multiple solutions for a given n, then your solution should ensure that the smaller packages are used before the larger packages. For example, buy_nuggets(18) should return (3,3,0,0) instead of (2,0,2,0), that is 3 boxes of 6 piece nuggets over 2 boxes of nine piece. Input Format Integer (n)

I was provided with the restrictions -10^6<=a,b,c,n<=10^6

Output Format

Tuple of 4 numbers (d,a,b,c) where

d = total number of packages a - number of packages of 6 b - number of packages of 9 c - number of packages of 20

I then attempted

def nugget_boxes(n): 
    # Write your code here- (above this was given)
    def diophantine(a,b,c,d):
        if a>b and c and d:
            q=extended_nuggets(a,b,c,d)
            a1=q[1]
            b1=q[2]
            c1=q[3]
            d1=q[4]
        if b>a and c and d:
            q=extended_nuggets(a,b,c,d)
            a1=q[2]
            b1=q[1]
            c1=q[3]
            d1=q[4]
        if c>a and b and d:
            q=extended_nuggets(a,b,c,d)
            a1=q[3]
            b1=q[1]
            c1=q[2]
            d1=q[4]           
        else:
            q=extended_nuggets(a,b,c,d)
            a1=q[4]
            b1=q[1]
            c1=q[2]
            d1=q[3]
            assert c%q[0]==0
            d=q[0]
            p=c/d
                return diophantine(int(p*x1),int(p*y1), int(p*z1))
    
    
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(raw_input().strip())

    results = nugget_boxes(n)

    fptr.write(str(results) + '\n')

    fptr.close()

I did ask before and was advised to return the function, I was referred to a python tutorial to which I am grateful for and I am reading, very concise yet informative. However, this specific problem has been giving me a hard time. I know this might be a hard task, but I was hoping you could still attempt teaching even with my current knowledge of coding.

Answer 1

An iterative solution that works well with the specific box sizes is below. It's expandable to other box scenarios by simply adding more nested if blocks.

The way in which the "prefer smaller boxes" requirement is met is simply by ensuring we search the solution space appropriately. In other words, we start with the maximum possible number of six-boxes and search down.

Similarly, we start with the maximum possible number of nine-boxes (given the number of six-boxes) and search down.

We don't have to search number of twenty-boxes since, given the quantity of the two smaller sizes, there's only one possibility: the number that gets as close as possible to the desired quantity without going over.

Then, if we got the quantity exactly, we return the solution immediately. Otherwise, we keep searching. If no solution is found after exhaustive search, we return the sentinel value (all zeroes).

This is certainly better than the naive approach of testing every possible scenario of the counts and saving the one that meets the "prefer smaller boxes" requirement.

import typing as typ

def pack_nuggets(quant: int) -> typ.Tuple[int]:
    """ Figure out how many nugget boxes are needed.

        Given quantity of nuggets, calculates the best triplet
        of boxes (of zize 6, 9, and 20) to satisfy the order.

        Best in this case prefers smaller boxes to larger.

        If no solution, give all zeros.

        Args:
            quant: the quantity of nuggets desired.
        Returns:
            Tuple with total box count followed by count of
            each box in ascending size).
    """

    # Start with maximum possible quantity of six-boxes
    # and gradually reduce to zero.

    max_sixes: int = quant // 6
    for six in range(quant // 6, -1, -1):
        # Start with maximum possible quantity of nine-boxes
        # given current six-box count and gradually reduce
        # to zero.

        six_val: int = six * 6
        max_nines_for_six: int = (quant - six_val) // 9
        for nine in range(max_nines_for_six, -1, -1):
            # There's only really one possible twenty-boxes
            # count that can get to (or a little below) the
            # desired quantity.

            nine_val: int = nine * 9
            twenty: int = (quant - six_val - nine_val) // 20

            # If that's a viable solution, return it.

            if six * 6 + nine * 9 + twenty * 20 == quant:
                return (six + nine + twenty, six, nine, twenty)

    # If there were NO viable solutions, let caller know.

    return (0, 0, 0, 0)

And what self-respecting developer would post code without a test harness? "Not I," said Pax :-)

# Test harness.

if __name__ == "__main__":
    for test_val in range(55):
        print(f"Result is {pack_nuggets(test_val)} for {test_val} nuggets.")
    print(f"Result is {pack_nuggets(1_000_000)} for {1_000_000} nuggets.")

The output from the test harness shows the function in action (comments added by me):

Result is (0, 0, 0, 0) for 0 nuggets.
Result is (0, 0, 0, 0) for 1 nuggets.
Result is (0, 0, 0, 0) for 2 nuggets.
Result is (0, 0, 0, 0) for 3 nuggets.
Result is (0, 0, 0, 0) for 4 nuggets.
Result is (0, 0, 0, 0) for 5 nuggets.
Result is (1, 1, 0, 0) for 6 nuggets.  # Six is first to satisfy.
Result is (0, 0, 0, 0) for 7 nuggets.
Result is (0, 0, 0, 0) for 8 nuggets.
Result is (1, 0, 1, 0) for 9 nuggets.  # Then nine.
Result is (0, 0, 0, 0) for 10 nuggets.
Result is (0, 0, 0, 0) for 11 nuggets.
Result is (2, 2, 0, 0) for 12 nuggets.
Result is (0, 0, 0, 0) for 13 nuggets.
Result is (0, 0, 0, 0) for 14 nuggets.
Result is (2, 1, 1, 0) for 15 nuggets. # A six and a nine.
Result is (0, 0, 0, 0) for 16 nuggets.
Result is (0, 0, 0, 0) for 17 nuggets.
Result is (3, 3, 0, 0) for 18 nuggets. # Prefer 3*six over 2*nine.
Result is (0, 0, 0, 0) for 19 nuggets.
Result is (1, 0, 0, 1) for 20 nuggets. # A single twenty-box.
Result is (3, 2, 1, 0) for 21 nuggets.
Result is (0, 0, 0, 0) for 22 nuggets.
Result is (0, 0, 0, 0) for 23 nuggets.
Result is (4, 4, 0, 0) for 24 nuggets. # Use 4*six, not 2*nine + six.
Result is (0, 0, 0, 0) for 25 nuggets.
Result is (2, 1, 0, 1) for 26 nuggets.
Result is (4, 3, 1, 0) for 27 nuggets.
Result is (0, 0, 0, 0) for 28 nuggets.
Result is (2, 0, 1, 1) for 29 nuggets.
Result is (5, 5, 0, 0) for 30 nuggets.
Result is (0, 0, 0, 0) for 31 nuggets.
Result is (3, 2, 0, 1) for 32 nuggets.
Result is (5, 4, 1, 0) for 33 nuggets.
Result is (0, 0, 0, 0) for 34 nuggets.
Result is (3, 1, 1, 1) for 35 nuggets.
Result is (6, 6, 0, 0) for 36 nuggets.
Result is (0, 0, 0, 0) for 37 nuggets.
Result is (4, 3, 0, 1) for 38 nuggets.
Result is (6, 5, 1, 0) for 39 nuggets.
Result is (2, 0, 0, 2) for 40 nuggets. # Two twenty-boxes.
Result is (4, 2, 1, 1) for 41 nuggets.
Result is (7, 7, 0, 0) for 42 nuggets.
Result is (0, 0, 0, 0) for 43 nuggets.
Result is (5, 4, 0, 1) for 44 nuggets.
Result is (7, 6, 1, 0) for 45 nuggets.
Result is (3, 1, 0, 2) for 46 nuggets.
Result is (5, 3, 1, 1) for 47 nuggets.
Result is (8, 8, 0, 0) for 48 nuggets.
Result is (3, 0, 1, 2) for 49 nuggets.
Result is (6, 5, 0, 1) for 50 nuggets.
Result is (8, 7, 1, 0) for 51 nuggets.
Result is (4, 2, 0, 2) for 52 nuggets.
Result is (6, 4, 1, 1) for 53 nuggets. # 4*six + nine + twenty.
Result is (9, 9, 0, 0) for 54 nuggets. # Prefer 9*six over 6*nine.

# Still very fast, even for a million nuggets.
# But now I feel quite bloated :-)

Result is (166662, 166660, 0, 2) for 1000000 nuggets.

Answer 2

It's unclear what problem you're experiencing with your code, although it does contain several errors, like a>b and c and d is an expression that likely doesn't mean what you think it does. It means 'if a is greater than b and the boolean value of c is True and the boolean value of d is True' - you probably wanted something like 'if a is greater than b, c, and d', although that doesn't make too much sense either, from the point of view of the algorithm

The problem itself is a bit weird - who would want as many small boxes as possible, since larger boxes would typically give you a discount. But apparently, if that's the requirement - the customer is always right.

The problem is fairly straightforward if you're allowed a recursive implementation (which you apparently are):

from typing import Tuple


def pack_nuggets(n: int, sizes: Tuple[int]) -> Tuple[int]:
    if n == 0:
        return (0, *(0 for _ in sizes))
    if not sizes:
        return (0,)
    for x in range(n // sizes[0], 0, -1):
        total, *rest = pack_nuggets((remainder := n - x * sizes[0]), sizes[1:])
        if sum(rest) or not remainder:
            return (sum(rest) + x, x, *rest)
    return (0, *(0 for _ in sizes))


print(pack_nuggets(0, (6, 9, 20)))   # (0, 0, 0, 0)
print(pack_nuggets(10, tuple()))     # (0, )
print(pack_nuggets(18, (6, 9, 20)))  # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20)))  # (5, 3, 1, 1)

Edit: user @paxdiablo correctly pointed out that the solution was returning a pair of an int and a tuple in a tuple; which I'd prefer from a stylistic point of view, but was not in line with OP's question. The new solution correctly returns a single tuple.

In case the typing stuff doesn't work, you can use this - however, that likely means you're using an older version of Python, in which case the walrus operator probably also doesn't work. Here's a solution that works for older Python 3 versions:

def pack_nuggets(n, sizes):
    if n == 0:
        return (0, *(0 for _ in sizes))
    if not sizes:
        return (0,)
    for x in range(n // sizes[0], 0, -1):
        remainder = n - x * sizes[0]
        total, *rest = pack_nuggets(remainder, sizes[1:])
        if sum(rest) or not remainder:
            return (sum(rest) + x, x, *rest)
    return (0, *(0 for _ in sizes))


print(pack_nuggets(0, (6, 9, 20)))   # (0, 0, 0, 0)
print(pack_nuggets(10, tuple()))     # (0, )
print(pack_nuggets(18, (6, 9, 20)))  # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20)))  # (5, 3, 1, 1)