McNuggets problem

From Wikipedia:

McNuggets problem
You are encouraged to solve this task according to the task description, using any language you may know.

The McNuggets version of the coin problem was introduced by Henri Picciotto,
who included it in his algebra textbook co-authored with Anita Wah. Picciotto
thought of the application in the 1980s while dining with his son at
McDonald's, working the problem out on a napkin. A McNugget number is
the total number of McDonald's Chicken McNuggets in any number of boxes.
In the United Kingdom, the original boxes (prior to the introduction of
the Happy Meal-sized nugget boxes) were of 6, 9, and 20 nuggets.

Task

Calculate (from 0 up to a limit of 100) the largest non-McNuggets number (a number n which cannot be expressed with 6x + 9y + 20z = n where x, y and z are natural numbers).

C

<lang c>#include <stdio.h>

int main() {

   int max = 0, i = 0, sixes, nines, twenties;

loopstart: while (i < 100) {

       for (sixes = 0; sixes*6 < i; sixes++) {
           if (sixes*6 == i) {
               i++;
               goto loopstart;
           }

           for (nines = 0; nines*9 < i; nines++) {
               if (sixes*6 + nines*9 == i) {
                   i++;
                   goto loopstart;
               }

               for (twenties = 0; twenties*20 < i; twenties++) {
                   if (sixes*6 + nines*9 + twenties*20 == i) {
                       i++;
                       goto loopstart;
                   }
               }
           }
       }
       max = i;
       i++;
   }

   printf("Maximum non-McNuggets number is %d\n", max);

   return 0;

}</lang>

REXX

This REXX version generalizes the problem (does not depend on fixed meal sizes),   and also checks for:

•   a meal that doesn't include McNuggets   (in other words, zero nuggets)
•   a meal size that includes a double order of nuggets
•   a meal size that includes a single nugget   (which means, no largest McNugget number)
•   excludes meals that have a multiple order of nuggets
•   automatically computes the high value algebraically instead of using   100.

<lang rexx>/*REXX pgm solves the McNuggets problem: the largest McNugget number for given meals. */ parse arg y /*obtain optional arguments from the CL*/ if y= | y="," then y= 6 9 20 /*Not specified? Then use the defaults*/ say 'The number of McNuggets in the serving sizes of: ' space(y) $=

1. = 0 /*the Y list must be in ascending order*/

z=.

      do j=1  for words(y);      _= word(y, j)  /*examine  Y  list for dups, neg, zeros*/
      if _==1               then signal done    /*Value ≡ 1?  Then all values possible.*/
      if _<1                then iterate        /*ignore zero and negative # of nuggets*/
      if wordpos(_, $)\==0  then iterate        /*search for duplicate values.         */
           do k=1  for #                        /*   "    "  multiple     "            */
           if _//word($,k)==0  then iterate j   /*a multiple of a previous value, skip.*/
           end   /*k*/
      $= $ _;      #= # + 1;     $.#= _         /*add─►list; bump counter; assign value*/
      end        /*j*/

if #<2 then signal done /*not possible, go and tell bad news. */ _= gcd($) if _\==1 then signal done /* " " " " " " " */ if #==2 then z= $.1 * $.2 - $.1 - $.2 /*special case, construct the result. */ if z\==. then signal done h= 0 /*construct a theoretical high limit H.*/

      do j=2  for #-1;  _= j-1;       _= $._;       h= max(h, _ * $.j  -  _  -  $.j)
      end   /*j*/

@.=0

      do j=1  for #;    _= $.j                  /*for every value, make as possible.   */
        do k=_  by _  to h;   @.k=1;  end /*k*/ /*populate every multiple as possible. */
      end   /*j*/

      do j=1  for #;    _= $.j                  /*populate the  Jth + Kth   summand.   */
        do k=1  for h;  if \@.k  then iterate
        s= k + _;       @.s= 1                  /*add two #s;   mark as being possible.*/
        end   /*k*/
      end     /*j*/

      do z=h  by -1  for h                      /*find largest integer not summed.     */
      if \@.z  then leave
      end     /*z*/

say done: if z==. then say 'The largest McNuggets number not possible.'

               else say 'The largest McNuggets number is: '          z

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: procedure; $=; do j=1 for arg(); $=$ arg(j); end; $= space($)

    parse var $ x $;     x= abs(x);
      do  while $\==;  parse var $ y $;  y= abs(y);  if y==0  then iterate
        do  until y==0;  parse value  x//y  y   with   y  x;  end
      end;              return x<lang>

output   when using the default inputs:

The number of McNuggets in the serving sizes of:  6 9 20

The largest McNuggets number is:  43