Choose from an existing set of weights to make a target sum

When doing weightlifting, I want to make a specific weight by attaching several plates to a bar.

I have the following plates:

• 6 plates of 1 kg each
• 6 plates of 2.5 kg each
• 6 plates of 5 kg each
• 6 plates of 10 kg each

The bar itself weighs 10 kg.

It's only allowed to attach the plates in pairs - they are attached at each end of the bar, and the arrangement at the two ends must be completely symmetrical (e.g. attaching two 5-kg plates at one end, and one 10-kg plate at the other end is forbidden for reasons of safety).

Make a program or a function that tells me how many plates of each kind I have to use in order to get a given total weight. The input is an integer greater than 11; the output is a list/array/string of 4 numbers. If it's impossible to combine existing plates to get the target weight, output a zero/empty array, an invalid string, throw an exception or some such.

If there are several solutions, the code must output only one (don't make the user choose - he is too busy with other things).

Test cases:

12 -> [2 0 0 0] - 2 plates of 1 kg plus the bar of 10 kg
13 -> [0 0 0 0] - a special-case output that means "impossible"
20 -> [0 0 2 0] - 2 plates of 5 kg + bar
20 -> [0 4 0 0] - a different acceptable solution for the above
21 -> [6 2 0 0] - 6 plates of 1 kg + 2 plates of 2.5 kg + bar
28 -> [0 0 0 0] - impossible
45 -> [0 2 6 0] - a solution for a random number in range
112 -> [2 4 6 6] - a solution for a random number in range
121 -> [6 6 6 6] - maximal weight for which a solution is possible

If your code outputs the numbers in the opposite order (from the heavy plate to the light one), please specify this explicitly to avoid confusion.

• Isn't this a dupe of the minimum coin counting question? I don't think the same greedy algorithm fails, except with the restriction of 6 of one kind of plate. I think that might not be sufficient difference, but I'm not sure. – FryAmTheEggman Jun 29 '16 at 15:19
• The greedy algorithm doesn't work (not without modification, at least) exactly because the numbers are limited – anatolyg Jun 29 '16 at 15:27
• Related, but that one is ASCII – AdmBorkBork Jun 29 '16 at 15:28
• Yes, the reason I posted was that I was unsure that the modification was significant enough. I posted to try to get community feedback, and I'll remove my comment if it seems like the community disagrees with me. – FryAmTheEggman Jun 29 '16 at 15:38
• Can we output all solutions instead of just one? – Luis Mendo Jun 29 '16 at 15:41

Jelly, 22 bytes

4ṗạµ×2,5,10,20S€+⁵iƓịḤ

How it works

4                       Set the left argument and initial return value to 4.
ṗ                      Take the Cartesian power of [1, 2, 3, 4] and 4, i.e.,
generate all 4-tuples of integers between 1 and 4.
ạ                     Take the absolute difference of all integers in the
4-tuples and the integer 4. This maps [1, 2, 3, 4] to
[3, 2, 1, 0] and places [0, 0, 0, 0] at index 0.
µ                    Begin a new, monadic chain. Argument: A (list of 4-tuples)
2,5,10,20          Yield [2, 5, 10, 20].
×                   Perform vectorized multiplication with each 4-tuple in A.
S€        Sum each resulting 4-tuple.
+⁵      Add 10 to each sum.
Ɠ    Read an integer from STDIN.
i     Find its first index in the array of sums (0 if not found).
Ḥ  Unhalve; yield the list A, with all integers doubled.
ị   Retrieve the 4-tuple at the proper index.

MATL, 29 28 bytes

4t:qEZ^!"[l2.5AX]@Y*10+G=?@.

For inputs that have no solution this produces an empty output (without error).

Try it online!

Explanation

4           % Push 4
t:q         % Duplicate 4 and transform into range [0 1 2 3]
E           % Multiply by 2: transform into [0 2 4 6]
Z^          % Cartesian power. Each row is a "combination" of the four numbers
!           % Transpose
"           % For each column
[l2.5AX]  %   Push [1 2.5 5 10]
@         %   Push current column
Y*        %   Matrix multiply. Gives sum of products
G=        %   Compare with input: are they equal?
?         %   If so
@       %     Push current column, to be displayed
.       %     Break loop
%   Implicit end
% Implicit end
% Implicit display

Mathematica, 70 bytes

Select[FrobeniusSolve[{2,5,10,20},2#-20],AllTrue[EvenQ@#&&#<7&]][[1]]&

Anonymous function. Takes a number as input, and either outputs a list or errors and returns {}[[1]] if there is no solution.

Jelly, 25 bytes

×2,5,10,20S+⁵⁼³
4ṗ4’ÇÐfḢḤ

Try it here.

• 2,5,10,20 -> 2,5,⁵,20 – Leaky Nun Jun 29 '16 at 15:47
• really... isn't , a dyad? My whole life is a lie – Leaky Nun Jun 29 '16 at 15:54
• @LeakyNun , is a dyad, but it can also be used for literals. 2,5,⁵,20 isn't a literal though (2,5 and 20 are, but ,, and , are atoms), so you'd need something to combine the links. – Dennis Jun 29 '16 at 16:10

Python 3, 112 bytes

lambda n:[i for i in[[i//4**j%4*2for j in range(4)]for i in range(256)]if i[0]+2.5*i[1]+5*i[2]+10*i[3]+10==n][0]

An anonymous function that takes input, via argument, of the target mass and returns the number of each plate as a list. If no solution exists, an error is thrown. This is pure brute force.

How it works

lambda n                                   Anonymous function with input target mass n
...for i in range(256)                     Loop for all possible arrangement indices i
[i//4**j%4*2for j in range(4)]             Create a base-4 representation of the index i,
and multiply each digit by 2 to map from
(0,1,2,3) to (0,2,4,6)
[...]                                      Package all possible arrangements in a list
...for i in...                             Loop for all possible arrangements i
i...if i[0]+2.5*i[1]+5*i[2]+10*i[3]+10==n  Return i if it gives the target mass
[...]                                      Package all solutions in a list
:...[0]                                    Return the first list element. This removes any
multiple solutions, and throws an error if there
being no solutions results in an empty list

Try it on Ideone

Brachylog, 50 bytes

,L##l4,L:{.~e[0:3]}a:[2:5:10:20]*+:10+?,L:{:2*.}a.

Returns false when not possible.

Pyth, 3431 25 bytes

h+fqQ+;s*VT[1 2.5 5;)yMM^U4 4]*4]0
yMh+fqQ+;s*VT[2 5;y;)^U4 4]*4]0
yMhfqQ+;s*VT[2 5;y;)^U4 4

Test suite.

Errors in impossibility.

This is essentially a brute-force.

This is quite fast, since there are only 256 possible arrangements.

Scala, 202 bytes

Decided Scala doesn't get much love here, so I present a (probably not optimal) solution in Scala.

def w(i:Int){var w=Map(20->0,10->0,5->0,2->0);var x=i-10;while(x>0){
var d=false;for(a<-w.keys)if(a<=x & w(a)<6 & !d){x=x-a;w=w.updated(a,w(a)+2);d=true;}
if(!d){println(0);return;}}
println(w.values);}

The program outputs in reverse order and with extra junk compared to solutions in post. When a solution is not found, prints 0.

Note: I could not remove any of the newlines or spaces because Scala is dumb, so I think to reduce size, the method must be redone unless I missed something obvious.

APL, 40 bytes

{2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}

In ⎕IO←0. In English:

1. 10+2×,∘.+⌿1 2.5 5 10∘.×⍳4: build the array of all the possible weights, by computing the 4D outer sum of the weights per weight type;
2. ⍵⍳⍨: search the index of the given. If not found the index is 1+the tally of the array at step 1;
3. (4⍴4)⊤: represent the index in base 4, that is, compute the coordinate of the given weigth in the 4D space;
4. : bring the result to problem space, where the coordinates should be interpreted as half the number of the plates.

Example: {2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}112 2 4 6 6

Bonus: since APL is an array language, several weights can be tested at once. In this case the result is transposed:

{2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}12 13 20 21 28 45 112 121
2 0 0 6 0 0 2 6
0 0 0 2 0 2 4 6
0 0 2 0 0 2 6 6
0 0 0 0 0 2 6 6

JavaScript (ES6), 109 bytes

n=>000${[...Array(256)].findIndex((_,i)=>i+(i&48)*9+(i&12)*79+(i&3)*639+320==n*32).toString(4)*2}.slice(-4) Returns 00-2 on error. Alternative solution that returns undefined on error, also 109 bytes: n=>[...Array(256)].map((_,i)=>000${i.toString(4)*2}.slice(-4)).find(s=>+s[0]+s[1]*2.5+s[2]*5+s[3]*10+10==n)