The McNuggets Challenge

There is an updated version of this available at https://www.ojalgo.org/2019/05/the-mcnuggets-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 (4x20 pieces + 2x9 pieces). 14 pieces cannot be ordered (no combination of 6, 9 and 20 equals 14)

Code that solves the problem

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

public class TheMcNuggetsChallenge {

    public static void main(String[] args) {
        
        BasicLogger.debug();
        BasicLogger.debug(TheMcNuggetsChallenge.class.getSimpleName());
        BasicLogger.debug(OjAlgoUtils.getTitle());
        BasicLogger.debug(OjAlgoUtils.getDate());
        BasicLogger.debug();

        final ExpressionsBasedModel model = new ExpressionsBasedModel();

        Variable numberOfPack6 = model.addVariable("#6-packs").lower(0).integer(true);
        Variable numberOfPack9 = model.addVariable("#9-packs").lower(0).integer(true);
        Variable numberOfPack20 = model.addVariable("#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);
            }
        }
    }

}

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

Console output

TheMcNuggetsChallenge
ojAlgo
2018-04-01

OPTIMAL 100.0 @ [0.0, 0.0, 5.0]
OPTIMAL 99.0 @ [2.0, 3.0, 3.0]
OPTIMAL 98.0 @ [0.0, 2.0, 4.0]
OPTIMAL 97.0 @ [8.0, 1.0, 2.0]
OPTIMAL 96.0 @ [0.0, 4.0, 3.0]
OPTIMAL 95.0 @ [1.0, 1.0, 4.0]
OPTIMAL 94.0 @ [0.0, 6.0, 2.0]
OPTIMAL 93.0 @ [4.0, 1.0, 3.0]
OPTIMAL 92.0 @ [2.0, 0.0, 4.0]
OPTIMAL 91.0 @ [7.0, 1.0, 2.0]
OPTIMAL 90.0 @ [5.0, 0.0, 3.0]
OPTIMAL 89.0 @ [0.0, 1.0, 4.0]
OPTIMAL 88.0 @ [8.0, 0.0, 2.0]
OPTIMAL 87.0 @ [0.0, 3.0, 3.0]
OPTIMAL 86.0 @ [1.0, 0.0, 4.0]
OPTIMAL 85.0 @ [0.0, 5.0, 2.0]
OPTIMAL 84.0 @ [4.0, 0.0, 3.0]
OPTIMAL 83.0 @ [0.0, 7.0, 1.0]
OPTIMAL 82.0 @ [7.0, 0.0, 2.0]
OPTIMAL 81.0 @ [2.0, 1.0, 3.0]
OPTIMAL 80.0 @ [0.0, 0.0, 4.0]
OPTIMAL 79.0 @ [2.0, 3.0, 2.0]
OPTIMAL 78.0 @ [0.0, 2.0, 3.0]
OPTIMAL 77.0 @ [5.0, 3.0, 1.0]
OPTIMAL 76.0 @ [6.0, 0.0, 2.0]
OPTIMAL 75.0 @ [1.0, 1.0, 3.0]
OPTIMAL 74.0 @ [0.0, 6.0, 1.0]
OPTIMAL 73.0 @ [4.0, 1.0, 2.0]
OPTIMAL 72.0 @ [2.0, 0.0, 3.0]
OPTIMAL 71.0 @ [4.0, 3.0, 1.0]
OPTIMAL 70.0 @ [5.0, 0.0, 2.0]
OPTIMAL 69.0 @ [0.0, 1.0, 3.0]
OPTIMAL 68.0 @ [8.0, 0.0, 1.0]
OPTIMAL 67.0 @ [0.0, 3.0, 2.0]
OPTIMAL 66.0 @ [1.0, 0.0, 3.0]
OPTIMAL 65.0 @ [0.0, 5.0, 1.0]
OPTIMAL 64.0 @ [4.0, 0.0, 2.0]
OPTIMAL 63.0 @ [0.0, 7.0, 0.0]
OPTIMAL 62.0 @ [7.0, 0.0, 1.0]
OPTIMAL 61.0 @ [2.0, 1.0, 2.0]
OPTIMAL 60.0 @ [0.0, 0.0, 3.0]
OPTIMAL 59.0 @ [2.0, 3.0, 1.0]
OPTIMAL 58.0 @ [0.0, 2.0, 2.0]
OPTIMAL 57.0 @ [8.0, 1.0, 0.0]
OPTIMAL 56.0 @ [0.0, 4.0, 1.0]
OPTIMAL 55.0 @ [1.0, 1.0, 2.0]
OPTIMAL 54.0 @ [0.0, 6.0, 0.0]
OPTIMAL 53.0 @ [4.0, 1.0, 1.0]
OPTIMAL 52.0 @ [2.0, 0.0, 2.0]
OPTIMAL 51.0 @ [1.0, 5.0, 0.0]
OPTIMAL 50.0 @ [2.0, 2.0, 1.0]
OPTIMAL 49.0 @ [0.0, 1.0, 2.0]
OPTIMAL 48.0 @ [8.0, 0.0, 0.0]
OPTIMAL 47.0 @ [0.0, 3.0, 1.0]
OPTIMAL 46.0 @ [1.0, 0.0, 2.0]
OPTIMAL 45.0 @ [0.0, 5.0, 0.0]
OPTIMAL 44.0 @ [1.0, 2.0, 1.0]
Not possible to order 43 nuggets