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.
Pages: 1 2
[…] 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):
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 == 73682Problem: 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 :-)
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; }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]#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: