18
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Are there any time/memory limits? \$\endgroup\$
    – Dennis
    Jun 25 '15 at 18:15
  • \$\begingroup\$ @Dennis There are no time or memory limits. \$\endgroup\$
    – Kade
    Jun 25 '15 at 18:18
  • 4
    \$\begingroup\$ It's actually Thursday. \$\endgroup\$
    – mbomb007
    Jun 25 '15 at 19:14
  • 4
    \$\begingroup\$ @mbomb007 Astute observation :P I've adjusted the intro. \$\endgroup\$
    – Kade
    Jun 25 '15 at 19:32
  • 2
    \$\begingroup\$ I NEED to use the chicken mcnugget theorem somehow... \$\endgroup\$ Jun 26 '15 at 0:31
7
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Why is it by the sqrt of the sum of the squares, rather than just the sum? \$\endgroup\$
    – mbomb007
    Jun 25 '15 at 21:43
  • 1
    \$\begingroup\$ @mbomb007 Because it doesn't matter. If a > b, than sqrt(a) > sqrt(b) and vice versa. And using the .a method is shorter than squaring and summing s^R2. \$\endgroup\$
    – Jakube
    Jun 25 '15 at 21:59
5
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Congrats on what appears to be the fastest program so far! It might be faster than my reference program too :P I've added an ideone link at the bottom of your post so people can see the output. \$\endgroup\$
    – Kade
    Jun 25 '15 at 20:04
  • \$\begingroup\$ Your code can produce incorrect output. Input 18 should print 9 9, not 4 4 10. \$\endgroup\$
    – Dennis
    Jun 25 '15 at 21:08
  • \$\begingroup\$ There are other incorrect outputs as well. If I'm not mistaken, you can fix all of them by swapping the order of 9 and 10. \$\endgroup\$
    – Dennis
    Jun 25 '15 at 21:25
  • \$\begingroup\$ @Dennis Thank you, fixed it! \$\endgroup\$ Jun 26 '15 at 6:26
3
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ This may be one of the few situations where working out the solution by hand would be faster than letting the code finish.. nice work regardless :) \$\endgroup\$
    – Kade
    Jun 25 '15 at 18:29
2
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
10
  • \$\begingroup\$ Nothing looks wrong with this right now, I'll test it and see. Once I get home I'll add a reference, ungolfed program that I used to generate the list that's in the Gist. While I wasn't timing, I believe it took somewhere in the 8-12 minute range for all cases. \$\endgroup\$
    – Kade
    Jun 25 '15 at 19:31
  • \$\begingroup\$ @Vioz- Brilliant! :D \$\endgroup\$
    – Beta Decay
    Jun 25 '15 at 19:39
  • \$\begingroup\$ Looks like I may be wrong, after testing 36 it gets through about 40 million combinations (40,007,602 to be exact) before running into a MemoryError. This might be a limitation of my work machine though, as it only has 4GB of memory. \$\endgroup\$
    – Kade
    Jun 25 '15 at 19:42
  • \$\begingroup\$ @Vioz- Hm... Well it's hopeless for me to carry on testing on my phone... \$\endgroup\$
    – Beta Decay
    Jun 25 '15 at 19:47
  • 1
    \$\begingroup\$ @undergroundmonorail If you're using it only once, then for <= 4 chars a straight import is better (5 breaks even). But if you're using it more than once then from blah import* is always best. The only exception I can think of to the above though is if you have multiple imports, which is the only time that comes to mind where as is actually useful. \$\endgroup\$
    – Sp3000
    Jun 26 '15 at 5:47
1
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Your approach doesn't seem to check if the goal can be reached. 11 prints [6] and 18 prints [10, 4]. \$\endgroup\$
    – Dennis
    Jun 25 '15 at 23:54
  • \$\begingroup\$ @Dennis Hey there, thanks for pointing that out. It's been a late night yesterday. Fixed it for 5 chars. 18 printed [10,4] because I was missing a pair of parens. The check was indeed wrong, i just checked if there was at least one element in the resultset, not if it sums up correctly. I don't know what I thought there \$\endgroup\$
    – C5H8NNaO4
    Jun 26 '15 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.