McNugget Numbers, Revisited

April 13, 2012

We begin with a brute-force solution that generates all possible combinations of McNuggets and discards those that don’t work; we use list comprehensions from the Standard Prelude:

(define (mcnugget-list n)
  (list-of (list a b c)
    (a range (+ (ceiling (/ n 6)) 1))
    (b range (+ (ceiling (/ n 9)) 1))
    (c range (+ (ceiling (/ n 20)) 1))
    (= (+ (* 6 a) (* 9 b) (* 20 c)) n)))

> (mcnugget-list 100)
((0 0 5) (1 6 2) (4 4 2) (7 2 2) (10 0 2))

We take a dynamic programming approach to the problem of counting the ways to form McNugget Numbers without enumerating them. Set up a matrix with n+1 columns numbered 0 to n and 4 rows for sizes of 0, 6, 9 and 20 McNuggets. The first row has 0 in every column except column 0, which gets a 1, as there is one way to count 0 McNuggets. Each subsequent row is filled from left to right, with each cell equal to the sum of the cell above and the cell k columns to the left, where k is the size of the current McNuggets box, either 6, 9 or 20; note that cells in the first k columns are the same as the cells in the row above. When all the columns are filled in all the rows, the right-most value on the last row is the desired result. As a practical matter, because each row is filled left-to-right based on the row above, it is only necessary to keep a single row in memory. Here’s the code:

(define (mcnugget-count n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs (list 6 9 20) (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x
          (+ (vector-ref cs x)
             (vector-ref cs (- x (car xs)))))))))

> (mcnugget-count 1000000)
462964815

This is exactly the same algorithm as the classic problem of counting the number of ways to make change for a given amount, given a list of available coins. The only difference is to give the list of coins as an input to the problem instead of fixing the list as [6, 9, 20]:

(define (counts xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

> (counts '(6 9 20) 1000000)
462964815
> (counts '(1 5 10 25 50 100) 100)
293
> (counts '(1 2 5 10 20 50 100 200) 200)
73682

Thus, there are 5 ways to form the McNugget Number 100, 462964815 ways to form the McNugget Number 1000000, 293 ways to make change for a US dollar, and 73682 ways to make change for two British pounds sterling.

You can run the program at http://programmingpraxis.codepad.org/ZmjVOjQu.

About these ads

Pages: 1 2

9 Responses to “McNugget Numbers, Revisited”

  1. [...] today’s Programming Praxis exercise, our goal is to calculate the number of ways a number can be expressed [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/04/13/programming-praxis-mcnugget-numbers-revisited/ for a version with comments):

    import Control.Monad.Identity
    
    mcNuggetCount :: Num a => [Int] -> Int -> a
    mcNuggetCount xs n = foldl (\a x -> fix $ 
        zipWith (+) a . (replicate x 0 ++)) (1 : repeat 0) xs !! n
    
    main :: IO ()
    main = do print $ mcNuggetCount [6,9,20] 1000000 == 462964815
              print $ mcNuggetCount [1,5,10,25,50,100] 100 == 293
              print $ mcNuggetCount [1,2,5,10,20,50,100,200] 200 == 73682
    
  3. Brikesh Kumar said

    Problem: Find all possible combination of x,y,z for which
    6x + 9y+ 20z = 100 (or P as input)
    Sol: Compute Possible values range of x,y,z. This is the quotient of p divided by 6,8,20
    In the above example
    x = {0-13}
    y= {0-11 }
    z ={0-5}
    Compute the combination by brute force:

    List<tuple> result = new List<tuple>
    for(int x= 0; x<= 13; x++)
    {
    for(int y = 0; y <= 11; y++)
    {
    for(int z =0; z <= 5; z++)
    {
    int number = 6x + 9y + 20z;
    //put 100 as input variable
    if( 100/number ==0)
    {
    Add(x,y,z) to result list;
    }
    else
    continue;
    }
    }
    }

  4. Brikesh Kumar said

    Not a very good algorithm. Looks like a cubic Algorith O(3). Will work to improve it.

  5. List result = new List
    for(int x= 0; x<= 13; x++)
    {
    for(int y = 0; y <= 11; y++)
    {
    for(int z =0; z <= 5; z++)
    {
    int number = 6x + 9y + 20z;
    //put 100 as input variable
    if( number ==100)
    {
    Add(x,y,z) to result list;
    }
    else
    continue;
    }
    }
    }

  6. Here’s an O(n) solution, that probably can be reduced to a closed form with some more work. However, Remco’s solution above is much more beautiful :-)

    typedef signed long long sll;
    sll mcnuggetnum(int n) {
    	// 6*x+9*y+20*z = n.
    	sll s = 0;
    	// 3(2x+3y) = n-20z ==> z === 2n (mod 3).
    	for(int z = (2*n)%3, z_lim = n/20; z <= z_lim; z += 3) {
    		// Similarly, 2x+3y = (n-20z)/3 = u. Take mod 2.
    		int u = (n-20*z)/3;
    		s += (u/3 + 2 - (u%2))/2;
    	}
    	return s;
    } 
    
  7. Dynamic Programming

    
    target=10**6
    coins=[6,9,20]
    ways=[1]+[0]*target
    for coin in coins:
        for i in range(coin,target+1):
            ways[i]+= ways[i-coin]
    
    print ways[target]
    
  8. sibendu dey said

    #include

    int mc_check(int);
    void com_mc(int);

    void main() {
    int number;
    clrscr();
    printf(“Enter Number to be checked \n”);
    scanf(“%d”,&number);
    if(mc_check(number)==1) {
    com_mc(number);
    }
    else {
    printf(“Not an McNugget”);
    }
    getch();
    }

    int mc_check(int check) {
    int i,flag=1;
    if( check%6==0 || check%9==0 ||check%20==0 || (check-20)%6==0 || (check-20)%9==0 || (check-9)%20==0 || (check-9)%20==0 || (check-6)%9==0 || (check-6)%20==0 )
    return flag;
    else
    return 0;
    }

    void com_mc(int number) {
    int i,j,k,flag1,flag2,flag3;
    for(i=0;((flag1=i*6)<=number);i++) {
    for(j=0;((flag2=j*9)<=(number-flag1));j++) {
    for(k=0;((flag3=k*20)<=(number-flag1-flag2));k++) {
    if((i*6+j*9+k*20)==number)
    printf("Combination:%d*6+%d*9+%d*20\n",i,j,k);
    }
    }
    }
    }

  9. This is an intuitive yet slow python implementation:

    def mcnugget(n):
    	return len([(i,j,k) for i in range(n/6+1) for j in range(n/9+1) for k in range(n/20+1) if i*6 + j*9 + k*20 == n])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: