Nuggets of Code

Question

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 4,

20 + 10 + 9 + 4 = 43 (597)

where 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.

The Task

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 0, False, Impossible!, or whatever is available in your language.

Example I/O:

[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).

Rules

1. No standard loopholes.
2. No use of built-in functions that do all or the majority of the task, such as FrobeniusSolve in Mathematica.

---

^{α - 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.}

Answer 1

Pyth, 26 25 bytes

e+Zo.aNf!-TCM"  
("./sQ

Notice that there are some unprintable chars. Try it online: Demonstration. It is quite slow (but not as slow as my 26 byte solution).

Explanation:

                          implicit: Q = input list
                     sQ   sum(Q)
                   ./     generate all integer partitions
       f                  filter for partitions T, which satisfy:
             "   ("          string containing chars with the ASCII-values of 4,6,9,10,20,40
           CM                convert each char to the ASCII-value
         -T                  remove this numbers from T
        !                    and check, if the resulting list is empty
    o                      order the remaining subsets N by:
     .aN                      the vector length of N (sqrt of sum of squares)
  +Z                       insert 0 at the beginning
 e                         print the last element

Pyth, 32 bytes

e+Zo.aNfqsTsQysm*]d/sQdCM"  
(

Notice that there are some unprintable chars. Try it online: Demonstration This version is way faster. It finds the solution for the input [6,7,8] in about one second and the solution for the input [30] in about 90 seconds.

Explanation:

                                 implicit: Q = input list
                          "...(  the string containing chars with the ASCII-values of 4,6,9,10,20,40
                        CM       convert each char to the ASCII-value
                m                map each number d to:
                  ]d                create the list [d]
                 *  /sQd            and repeat it sum(Q)/d times
               s                 unfold
              y                  generate all subsets
        f                        filter for subsets T, which satisfy:
         qsTsQ                      sum(Q) == sum(T)
    o                            order the remaining subsets N by:
     .aN                            the vector length of N (sqrt of sum of squares)
  +Z                             insert 0 at the beginning
 e                               print the last element

Answer 2

Perl, 175 153

sub f{my$n=$_[0];if(!$n){return 1;}foreach$o(40,20,9,10,6,4){if($n>=$o&&f($n-$o)){print"$o ";return 1;}}return 0;}$n+=$_ for@ARGV;if(!f($n)){print":(";}

Takes it's input from the program arguments. Prints a :( if it can't find a perfect solution.

Ungolfed Code:

sub f
{
    my $n = $_[0];
    if(!$n)
    {
        return 1;
    }
    foreach $o(40,20,9,10,6,4)
    {
        if($n>=$o&&f($n-$o))
        {
            print "$o ";
            return 1;
        }
    }
    return 0;
}

$n += $_ for @ARGV;
if(!f($n))
{
    print ":(";
}

P.S.: This is probably the first entry that doesn't take 10 minutes for 1 2 ;)

Check it out here.

Answer 3

CJam, 45 29 28 bytes

q~:+_[40K9A6Z)U]m*_::+@#=0-p

Note that this approach is very slow and memory-intensive.

Try it online in the CJam interpreter.

It can be sped up significantly at the cost of 5 bytes:

q~:+_40/4+[40K9A6Z)U]m*_::+@#=0-p

Complexity is still exponential in the sum of the input, but this should handle test cases up to 159 with the online interpreter and up to 199 with the Java interpreter in a couple of seconds.

Try it online in the CJam interpreter.

Idea

An optimal purchase (maximal sum of squares) is a valid purchase (correct number of nuggets) that has as many 40's as possible, then as many 20's as possible, then as many 9's as possible (e.g., 9 9 is preferable over 10 4 4) and so forth for 10's, 6's and 4's.

In this approach, we generate the Cartesian product of N copies of the array [40 20 9 10 6 4 0], where N is the desired number of nuggets. N is a (bad) upper bound for the number of purchases we have to make. In the sped up version of the code, we use N/40 + 4 instead.

Because of how the array is ordered, the Cartesian product will start with the vector [40 ... 40] and end with the vector [0 ... 0]. We compute the index of the first vector that has the correct sum (which will also have the optimal sum of squares), retrieve the corresponding array element, remove the zeroes that served as placeholders and print the result.

If no vector could be found, the index will be -1, so we retrieve [0 ... 0], which will print an empty array instead.

Code

q~                            e# Read from STDIN and evaluate the input.
  :+                          e# Push N, the sum of all elements of the resulting array.
     [40K9A6Z)U]              e# Push B := [40 20 9 10 6 4 0].
    _           m*            e# Push B**N, the array of all vectors of dimension N
                              e# and coordinates in B.
                  _::+        e# Copy and replace each vector by its sum.
                      @#      e# Get the first index of N.
                        =     e# Retrieve the corresponding element.
                         0-p  e# Remove 0's and print.

Answer 4

Julia, 126 bytes

r->(t=filter(i->all(j->j∈[4,6,9,10,20,40],i),partitions(sum(r)));show(!isempty(t)&&collect(t)[indmax(map(k->sum(k.^2),t))]))

This creates an unnamed function that accepts an array as input and prints an array or boolean to STDOUT, depending on whether a solution exists. To call it, give it a name, e.g. f=n->....

Ungolfed + explanation:

function f(r)
    # Nugget pack sizes
    packs = [4, 6, 9, 10, 20, 40]

    # Filter the set of arrays which sum to the required number of nuggets
    # to those for which each element is a nugget pack
    t = filter(i -> all(j -> j ∈ packs, i), partitions(sum(r)))

    # Print the boolean false if t is empty, otherwise print the array of
    # necessary nugget packs for which the sum of squares is maximal
    show(!isempty(t) && collect(t)[indmax(map(k -> sum(k.^2), t))])
end

Examples:

julia> f([1])
false

julia> f([2,7,12,4,15,3])
[20,10,9,4]

Answer 5

Python 3 - 265 characters

import itertools as i
n=list(map(int,input().split(',')));m=[]
for f in range(1,9):
 for j in range(6*f):
  for x in i.combinations((4,6,9,10,20,40,)*f,j+1):
   if sum(n)==sum(x):m.append(x)
if m!=[]:v=[sum(l**2for l in q)for q in m];print(m[v.index(max(v))])
else:print(0)

Showing spacing:

import itertools as i
n=list(map(int,input().split(',')));m=[]
for f in range(1,5):
 for j in range(6*f):
\tfor x in i.combinations((4,6,9,10,20,40,)*f,j+1):
\t if sum(n)==sum(x):m.append(x)
\t\tif m!=[]:v=[sum(l**2for l in q)for q in m];print(m[v.index(max(v))])
else:print(0)

Passes all test cases

Note: I don't know if this will pass all cases because it is so slow... But it should...

Answer 6

JavaScript, 261 256 261

d="length";function g(a){for(z=y=0;y<a[d];z+=+a[y++]);return z}x=[40,20,10,9,6,4];l=prompt().split(",");o=g(l);p=[];for(i=0;i<x[d];i++)r=g(p),s=r+x[i],(s<o-3||s==o)&&p.push(x[i]),(i==x[d]-1||40<o-r)&&r+x[i]<o-3&&(i=-1,0==i||o-r<p[p[d]-1]&&p.pop());g(p)==o&&p||0

I'm not sure if this is alright, it seems to work but I'm surely missing things.

It doesn't seem to be slow though, up to 123456 it outputs [40 x 3086, 10, 6] almost immediatly.

Explanation:

Iterating over the nugget sizes (biggest first)

• If the sum of the stack plus the nugget size is less than the goal - 3 -> push it on a stack
• If there is more than 40 left -> reset the loop counter
• If the sum of the stack is more than the goal when the last nugget-size was reached -> pop the last element, reset the loop counter
• If the sum of the stack adds up, return it, otherwise return 0

For 199 | 1 the stack built looks like this

i | stack
0   [40]
0   [40, 40]
0   [40, 40, 40]
0   [40, 40, 40, 40]
0   [40, 40, 40, 40]
1   [40, 40, 40, 40, 20]
2   [40, 40, 40, 40, 20, 10]
3   [40, 40, 40, 40, 20, 10, 9]
4   [40, 40, 40, 40, 20, 10, 9]
5   [40, 40, 40, 40, 20, 10, 9]
==> [40, 40, 40, 40, 20, 10, 9]

For 1

i | stack
0   []
1   []
2   []
3   []
4   []
5   []
==> 0