Nuggets of Code
It's a hypothetical situation where it is Friday evening, and you've invited over the usual golfing buddies to participate in your favourite hobby: code golfing. However, as this is such a brain-draining task, you need to pick up some brain food for the group so you can golf as much as possible off your code.
Now, everyone's favourite snack is chicken nuggets, but there's a problem: There is no single pack of them which covers everyone's needs. So, since you're already in the golfing mood, you decide to create a program that figures out exactly what packs you must buy to be able to cover everyone's Nugget needs.
Chicken nugget pack sizes are all over the place, and depending on where you live in the world, the standard sizes change too. However, the closest [place that serves nuggets] stocks the following sizes of nugget packs:
4, 6, 9, 10, 20, 40
Now you may notice that you cannot order certain combinations of nuggets. For example,
11 nuggets is not possible, since there is no combination that equals
11 exactly. However, you can make
43 by getting 1 pack of
20, 1 pack of
10, 1 pack of
9 and 1 pack of
20 + 10 + 9 + 4 = 43 (597)
597 is each term squared and added together (hint: the optimal solution has this as the highest value). There are of course other ways of making
43, but as you know, the more nuggets per pack, the cheaper it gets per nugget. So, you want to ideally buy the least number of packs and in the greatest quantities to minimize your cost.
You should create a program or function which takes a list of integers corresponding to each person's requirements. You should then calculate and print the most cost-efficientα order to buy the chicken nuggets. The most cost-efficientα order is the combination by which the sum of the squares of each quantity is the highest. If there is absolutely no way to buy the nuggets perfectly, you must print a falsy value such as
Impossible!, or whatever is available in your language.
[2 7 12 4 15 3] => [20 10 9 4] 1, 1, 2, 1 => False 6 5 5 5 5 5 9 => 40 [6, 4, 9] => 9 10 1 => 0 199 => 40, 40, 40, 40, 20, 10, 9 2 => Impossible!
Here is the list of ideal solutions for the first 400. Note these are not formatted how I would expect yours to be, each
tuple is in the form
(N lots of M).
- No standard loopholes.
- No use of built-in functions that do all or the majority of the task, such as
α - To clarify this with an example, you could also make 43 by doing
4 + 6 + 6 + 9 + 9 + 9 = 43 (319), but this would not be optimal, and thus an incorrect output, as the sum of the squares is less than the combination I noted in the introduction. Essentially, higher sum of squares = lower cost = most cost-efficient.