12
\$\begingroup\$

With all the gyms closed down with the COVID-19 situation, we have to exercise with the weight we have lying around at home. The problem is, we have a small selection of plates at varying weights, and can't immediately determine if we can create a setup at the desired weight.

Given an unsorted array of weighted plates and an unsorted array of barbells of different weights, determine the fewest amount of plates you need to put on a barbell to reach the desired weight, in ascending order mirrored at the halfway point, basically mirroring how it would be loaded on a real barbell (see example output). The plates have to be in pairs; you cannot use a particular plate an odd number of times since you put one plate on each side for equilibrium (e.g. every plate of a certain weight on one side should have a counterpart of the same weight on the otherside). If the desired weight cannot be achieved, approximate as closely as possible (while still maintaining equilibrium on both sides).


Examples:

Input (3 barbells, a set of plates, and goal weight): [[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 47]

Output (exact match, barbell and plate arrangement): [10, [3.5,15,15,3.5]


Input (3 barbells, a set of plates, and goal weight): [[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 45]

Output (exact match, barbell and plate arrangement): [45, []]


Input (3 barbells, a set of plates, and goal weight): [[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 0]

Output (closest approximation, barbell and plate arrangement): [6, []]


Input (3 barbells, a set of plates, and goal weight): [[10, 45, 6], [3.5,37,20,15,2.5,15,2.5,3.5,5,7], 9001]

Output (closest approximation, barbell and plate arrangement): [45, [2.5,3.5,15,15,3.5,2.5]]

Winners will be selected first by time complexity, then character count for tie-breaker.

\$\endgroup\$
  • \$\begingroup\$ So to clarify, does equilibrium mean that 1. There must be the same number of plates on each side of the barbell. 2. For each individual plate on the left there should also be a matching plate on the right with the same weight. \$\endgroup\$ – dingledooper Apr 28 at 3:01
  • \$\begingroup\$ I will clarify the question, your second point captures my intent. Each weighted plate on one side should have a counterpart of the same weight on the other side. \$\endgroup\$ – Josue Espinosa Apr 28 at 3:03
  • 1
    \$\begingroup\$ Welcome to the site! \$\endgroup\$ – null Apr 28 at 3:16
  • \$\begingroup\$ Updated to only consider time complexity as primary judgment criteria then using character count for tie-breaking :-) \$\endgroup\$ – Josue Espinosa Apr 28 at 3:40
  • \$\begingroup\$ The 'equilibrium' requirement seems to me to mean that the plates with weights 5, 7, 20, and 37 in the examples can't ever be used, as there's only one of each. Is that the intention? \$\endgroup\$ – Dingus Apr 28 at 3:40
3
\$\begingroup\$

C++ (gcc), \$ O(2^{\frac{|P|}4} \times (|B| + \frac{|P|}2)) \$, 933 bytes

Input/Output Format

Takes as input a vector of plates \$ P \$, a vector of barbells \$ B \$, and a target weight \$ W \$. It outputs the plate arrangement on the first line, and the barbell on the second line.

#include <bits/stdc++.h>
using namespace std;using d=double;
int f(auto b,auto p,d w){
unordered_map<d,int>u;vector<d>s,A,B;
for(auto i:p)u[i]++;
for(auto i:u)while((i.second-=2)>=0)s.push_back(i.first*2);
int z=s.size(),i,j,k;vector<pair<d,vector<d>>>x(1<<z/2),y(1<<z/2+1);d m=DBL_MAX,n,r;
for(i=0,k=1;i<z/2;i++){
for(j=0;j<k;j++)x[j+k]=x[j];
for(;j<k*2;j++)x[j].first+=s[i],x[j].second.push_back(s[i]/2);
auto _=x.begin();inplace_merge(_,_+k,_+k*2);k*=2;
}
for(k=1;i<z;i++){
for(j=0;j<k;j++)y[j+k]=y[j];
for(;j<k*2;j++)y[j].first+=s[i],y[j].second.push_back(s[i]/2);
auto _=y.begin();inplace_merge(_,_+k,_+k*2);k*=2;
}
for(auto f:b)
for(i=0,j=(1<<z-z/2)-1;i<1<<z/2&&j>=0;n>w?j--:i++){
n=x[i].first+y[j].first+f;
if(abs(n-w)<m)r=f,A=x[i].second,B=y[j].second,m=abs(n-w);
}
A.insert(A.end(),B.begin(),B.end());
sort(A.begin(),A.end());for(auto i:A)cout<<i<<' ';
reverse(A.begin(), A.end());for(auto i:A)cout<<i<<' ';
cout<<'\n'<<r;
}

Try it online!

Explanation

The algorithm calculates all possible subset sums \$ S \$ of \$ P \$, and then finds the sum \$ s + b \$ which is closest to \$ W \$, where \$ s \$ and \$ b \$ are elements in \$ S \$ and \$ B \$, respectively. Using the meet-in-the-middle approach decreases the complexity quite a bit. (I'm aware this code is super long, and I'll try to shrink it a bit eventually).

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 2, \$ O(2^{\frac{|W|}2} \cdot |B| \cdot |W| + |W|^2) \$, 203 bytes

Naive implementation, looks at all combinations of possible weights \$W\$ and barbells \$B\$.

lambda B,W,T:min([(w+w[::-1],b)for w in p(sorted(sum([W.count(x)/2*[x]for x in set(W)],[])))for b in B],key=lambda(a,b):((T-sum(a)-b)**2,len(a)))
p=lambda l:l and[l[:1]+x for x in p(l[1:])]+p(l[1:])or[l]

Try it online!

Ungolfed

def f(Barbells, Weights, Target):
  # For every pair of same weights keep one, order them ascending
  usable_weights = concat([Weights.count(x)/2 * [x] for x in set(Weights)])
  usable_weights = sorted(usable_weights)

  # list all possible combinations of symmetric weights and barbells
  possible_setups = [(w+w[::-1], b)for w in powerset(usable_weights)for b in Barbells]

  # Find the one with the weight being the closest to the target,
  # on a tie take the one with the lowest number of weights
  return min(possible_setups, key=lambda(a,b): ((Target - sum(a) - b)**2, len(a)))

concat = lambda ls:sum(ls, [])
powerset = lambda l:l and [l[:1]+x for x in powerset(l[1:])]+powerset(l[1:]) or [[]]

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Looks like the last test case doesn't adhere to the plate arrangement ([3.5, 2.5, 15, 15, 2.5, 3.5], 45) should be ([2.5, 3.5, 15, 15, 3.5, 2.5], 45) \$\endgroup\$ – Josue Espinosa Apr 28 at 11:58
  • \$\begingroup\$ @JosueEspinosa I missed the part about the ascending order, thanks for reminding me. Should be fixed now \$\endgroup\$ – ovs Apr 28 at 12:06
1
\$\begingroup\$

Haskell, \$O(Wlog(W)+B2^WW) \$, 159 bytes

Worst case time, where \$W\$ is the number of weights and \$B\$ is the number of barbells.

import Data.List
h(a:b:r)|a==b,p<-h r=[a:q++[b]|q<-p]++p|1>0=h$b:r
h _=[[]]
(b#w)g|p<-h$sort w=snd$snd$minimum[(abs$g-a-sum q,(length q,(a,q)))|a<-b,q<-p]

Try it online!

I was never good at calculating time complexity, so feel free to correct me if you think I'm wrong. Here's some annotated source code to show some of my thinking:

import Data.List
-- O(h 0) = 1
-- O(h W) = 2*O(h$W-2) = 2^W
h(a:b:r)|a==b,p<-h r=[a:q++[b]|q<-p]++p|1>0=h$b:r
h _=[[]]
-- O(B#W$_) = W*log(W)+B*O(h W)*W = W*log(W)+B*2^W*W
(b#w)g|p<-h$sort w=snd$snd$minimum[(abs$g-a-sum q,(length q,(a,q)))|a<-b,q<-p]

The \$Wlog(W)\$ is for sorting the weights and the \$W\$ factor on the second part is for the linear time calculation of length q and sum q.

My implementation is a fairly straightforward brute force approach. I don't even optimize for the ideal case because it's extra bytes and it wouldn't help the worst case time anyway. The idea is to sort the list of weights and pick up on adjacent weights of equal value. I remove them from the list and recur, returning the resulting list along with those results with that weight on either side. In this way I build up a list of all possible weight combinations. Then it's a simple matter of looping over each barbell and finding the setup with the minimum error.

I've also tried to ensure that Haskell doesn't calculate some values like h$sort w and h r multiple times. I believe the compiler can usually optimize cases where it notices redundancy like that but I thought it best to err on the side of caution.

| improve this answer | |
\$\endgroup\$

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.