The McNuggets Challenge

This is not an eating competition, instead you have to think.

The Challenge

Chicken McNuggets can be ordered in the sizes of 6, 9 and 20 pieces. Being allowed to use a combination of the sizes, what is the highest number that you can NOT order?

Example: 98 pieces can be ordered using a combination (4×20 pieces + 2×9 pieces). 14 pieces cannot be ordered (no combination of 6, 9 and 20 equals 14)

Solution

To solve this we created a small optimisation model that for a proposed number verifies if it is possible to order that quantity.

  • The variables are the number of 6-packs, 9-packs and 20-packs respectively.
  • The objective is to maximise the total number of nuggets ordered.
  • The total number of nuggets ordered is constrained to not be larger than a quantity currently investigated
  • In a loop the program tests order quantities in a decreasing order until the maximum order is not equal the constraint/proposed quantity.

Example Code

TheMcNuggetsChallenge.java
import org.ojalgo.OjAlgoUtils;
import org.ojalgo.netio.BasicLogger;
import org.ojalgo.optimisation.Expression;
import org.ojalgo.optimisation.ExpressionsBasedModel;
import org.ojalgo.optimisation.Optimisation.Result;
import org.ojalgo.optimisation.Variable;

/**
 * What's largest number of nuggets you can order at McDonalds that they can't deliver (that exact quantity)?
 *
 * @see https://www.ojalgo.org/2019/05/the-mcnuggets-challenge/
 * @see https://github.com/optimatika/ojAlgo/wiki/The-McNuggets-Challenge
 */
public class TheMcNuggetsChallenge {

    public static void main(final String[] args) {

        BasicLogger.debug();
        BasicLogger.debug(TheMcNuggetsChallenge.class);
        BasicLogger.debug(OjAlgoUtils.getTitle());
        BasicLogger.debug(OjAlgoUtils.getDate());
        BasicLogger.debug();

        ExpressionsBasedModel model = new ExpressionsBasedModel();

        Variable numberOfPack6 = model.newVariable("#6-packs").lower(0).integer(true);
        Variable numberOfPack9 = model.newVariable("#9-packs").lower(0).integer(true);
        Variable numberOfPack20 = model.newVariable("#20-packs").lower(0).integer(true);

        Expression totalNuggetsOrdered = model.addExpression().weight(1);
        totalNuggetsOrdered.set(numberOfPack6, 6);
        totalNuggetsOrdered.set(numberOfPack9, 9);
        totalNuggetsOrdered.set(numberOfPack20, 20);

        for (int i = 100; i > 0; i--) {
            totalNuggetsOrdered.upper(i);
            Result result = model.maximise();

            if (Math.round(result.getValue()) < i) {
                BasicLogger.debug("Not possible to order {} nuggets", i);
                break;
            } else {
                BasicLogger.debug(result);
            }
        }
    }

}

Console Output

class TheMcNuggetsChallenge
ojAlgo
2019-05-09

OPTIMAL 100.0 @ { 0, 0, 5 }
OPTIMAL 99.0 @ { 5, 1, 3 }
OPTIMAL 98.0 @ { 0, 2, 4 }
OPTIMAL 97.0 @ { 8, 1, 2 }
OPTIMAL 96.0 @ { 0, 4, 3 }
OPTIMAL 95.0 @ { 1, 1, 4 }
OPTIMAL 94.0 @ { 0, 6, 2 }
OPTIMAL 93.0 @ { 4, 1, 3 }
OPTIMAL 92.0 @ { 2, 0, 4 }
OPTIMAL 91.0 @ { 4, 3, 2 }
OPTIMAL 90.0 @ { 2, 2, 3 }
OPTIMAL 89.0 @ { 0, 1, 4 }
OPTIMAL 88.0 @ { 8, 0, 2 }
OPTIMAL 87.0 @ { 0, 3, 3 }
OPTIMAL 86.0 @ { 1, 0, 4 }
OPTIMAL 85.0 @ { 0, 5, 2 }
OPTIMAL 84.0 @ { 4, 0, 3 }
OPTIMAL 83.0 @ { 0, 7, 1 }
OPTIMAL 82.0 @ { 7, 0, 2 }
OPTIMAL 81.0 @ { 2, 1, 3 }
OPTIMAL 80.0 @ { 0, 0, 4 }
OPTIMAL 79.0 @ { 2, 3, 2 }
OPTIMAL 78.0 @ { 0, 2, 3 }
OPTIMAL 77.0 @ { 8, 1, 1 }
OPTIMAL 76.0 @ { 0, 4, 2 }
OPTIMAL 75.0 @ { 1, 1, 3 }
OPTIMAL 74.0 @ { 0, 6, 1 }
OPTIMAL 73.0 @ { 4, 1, 2 }
OPTIMAL 72.0 @ { 2, 0, 3 }
OPTIMAL 71.0 @ { 4, 3, 1 }
OPTIMAL 70.0 @ { 5, 0, 2 }
OPTIMAL 69.0 @ { 0, 1, 3 }
OPTIMAL 68.0 @ { 5, 2, 1 }
OPTIMAL 67.0 @ { 0, 3, 2 }
OPTIMAL 66.0 @ { 1, 0, 3 }
OPTIMAL 65.0 @ { 0, 5, 1 }
OPTIMAL 64.0 @ { 4, 0, 2 }
OPTIMAL 63.0 @ { 0, 7, 0 }
OPTIMAL 62.0 @ { 7, 0, 1 }
OPTIMAL 61.0 @ { 2, 1, 2 }
OPTIMAL 60.0 @ { 0, 0, 3 }
OPTIMAL 59.0 @ { 2, 3, 1 }
OPTIMAL 58.0 @ { 0, 2, 2 }
OPTIMAL 57.0 @ { 5, 3, 0 }
OPTIMAL 56.0 @ { 0, 4, 1 }
OPTIMAL 55.0 @ { 1, 1, 2 }
OPTIMAL 54.0 @ { 0, 6, 0 }
OPTIMAL 53.0 @ { 4, 1, 1 }
OPTIMAL 52.0 @ { 2, 0, 2 }
OPTIMAL 51.0 @ { 4, 3, 0 }
OPTIMAL 50.0 @ { 5, 0, 1 }
OPTIMAL 49.0 @ { 0, 1, 2 }
OPTIMAL 48.0 @ { 8, 0, 0 }
OPTIMAL 47.0 @ { 0, 3, 1 }
OPTIMAL 46.0 @ { 1, 0, 2 }
OPTIMAL 45.0 @ { 0, 5, 0 }
OPTIMAL 44.0 @ { 4, 0, 1 }
Not possible to order 43 nuggets

If you believe there is a number greater than 100 that cannot be ordered, then you need to modify and run the code yourself.