# 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ṗạµ×2,5,10,20S€+⁵iƓịḤ  Main link. No arguments

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. 2×: 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)