## 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.

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

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

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;

}

}

}

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

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;

}

}

}

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 :-)

Dynamic Programming

#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);

}

}

}

}

This is an intuitive yet slow python implementation: