26
\$\begingroup\$

It was a warm summer evening...

when my stupid car decided to break down in the middle of the road on my way back from the supermarket. I pushed it to the sideline and decided to walk home. I opened the trunk to take out the grocery and remaining stuff. It was then that I noticed the items were not evenly bagged. Some bags had more heavy items while others had few lighter stuff - some even had a mix of such items. To make it easy for me to carry, I decided to group everything in to two bags and make their weights as close to each other as possible.

Making my way downtown

Your goal

is to help me rearrange the items in to two shopping bags in such a way that the difference between both bags is close to zero as possible.
Mathematically:

WEIGHT LEFT HAND — WEIGHT RIGHT HAND ≈ 0

Example

If I had only 2 items, Bread and Peanut butter, and the weight of bread is 250 grams and peanut butter is 150 grams, the best way is to carry them separately in two hands.

WLH - WRH = W(BREAD) - W(P.BUTTER)
250 - 150 = 100

The other possibility is :

W(BREAD, P.BUTTER) - W(empty hand) = (250 + 150) - 0 = 400

This is not better than our first case, so you should go with the first one.

Your code should

  1. take inputs of numbers indicating weights of items in the shopping bag. Units are not important, but they should be the same (ideally kilograms or grams). Input can be done one by one or all at once. You may restrict the total count to 20 items max, if you want.
  2. The input format/type is up to you to choose, but nothing else should be present other than the weights.
  3. Any language is allowed, but stick to standard libraries.
  4. Display output. Again, you're free to choose the format, but explain the format in your post. ie, how can we tell which ones are left hand items and which ones are right hand items.

Points

  1. Shortest code wins.

Hint

The two possible algorithms that I could think of are differentiation (faster) and permutations/combinations (slower). You may use these or any other algorithm that does the job.

\$\endgroup\$
  • 5
    \$\begingroup\$ I like rule 2, it's flexible but does not allow cheating \$\endgroup\$ – edc65 Jun 10 '15 at 9:22
  • 2
    \$\begingroup\$ You've basically reinvented the knapsack problem. en.wikipedia.org/wiki/Knapsack_problem \$\endgroup\$ – Sparr Jun 14 '15 at 0:31
  • \$\begingroup\$ Thank you @Sparr I am wicked smaat (not really) \$\endgroup\$ – Renae Lider Jun 15 '15 at 15:51
  • 2
    \$\begingroup\$ This problem is far too practical and realistic for this site. \$\endgroup\$ – Reinstate Monica iamnotmaynard Nov 18 '17 at 3:00
15
\$\begingroup\$

Pyth, 9 bytes

ehc2osNyQ

Input, output formats:

Input:
[1, 2, 3, 4, 5]
Output:
[1, 2, 4]

Demonstration.

ehc2osNyQ
             Q = eval(input())
       yQ    Take all subsets of Q.
    osN      Order those element lists by their sums.
  c2         Cut the list in half.
eh           Take the last element of the first half.

This works because y returns the subsets in such an order that each subset and its complement are equidistant fom the center. Since the sum of a subset and the sum of its complement will always be equidistant from the center, the list after osNyQ will also have this property. Thus, the center two elements of osNyQ are complements, and must have an optimal split. We extract the first of those two elements and print it.

\$\endgroup\$
  • \$\begingroup\$ The answer by the OP only prints the bags in one hand, so congrats on your 9 byte solution. \$\endgroup\$ – Dennis Jun 13 '15 at 3:11
  • \$\begingroup\$ Your write is bugged for input [7 7 7 10 11] Traceback (most recent call last): File "pyth.py", line 772, in <module> File "<string>", line 4, in <module> File "/app/macros.py", line 865, in order TypeError: unorderable types: int() < list() \$\endgroup\$ – RosLuP Nov 17 '17 at 10:02
  • \$\begingroup\$ @RosLuP This worked at the time, I changed something about s that made it stop working. People didn't like the change, and your comment was the final push I needed to change it back. \$\endgroup\$ – isaacg Nov 18 '17 at 1:56
  • \$\begingroup\$ In the commented code it should not be "subset of Q" but "sublist of Q" \$\endgroup\$ – RosLuP Nov 18 '17 at 10:02
  • \$\begingroup\$ @RosLuP I disagree - a sublist is typically contiguous. Subset and subsequence are two terms for this kind of thing. \$\endgroup\$ – isaacg Nov 18 '17 at 11:25
6
\$\begingroup\$

Pyth, 16

ho.a-FsMNs./M.pQ

This takes the inputs as a pythonic list on STDIN. The output is a list of 2 lists with the first list being the items in one bag, and the second list representing the items in the second bag. This brute forces all combinations, so it will run very slowly (or run out of memory) for large inputs.

Try it online here

To support the handling of just one input, this goes up to 17:

hho.a-FsMNs./M.pQ

This will print the values that go in one hand.

\$\endgroup\$
  • \$\begingroup\$ This is a very impressive solution - it's not obvious at all that it won't give faulty answers like [[2], [1], [1]], but I think it works, due to exactly how ./ works. \$\endgroup\$ – isaacg Jun 10 '15 at 1:24
  • \$\begingroup\$ Actually, I think this fails on cases where everything goes in one hand, like when there's only 1 object. \$\endgroup\$ – isaacg Jun 10 '15 at 1:28
  • \$\begingroup\$ @isaacg I had kind of assumed 1 object wasn't valid, as you clearly had to just hold it in one hand. I wouldn't really know what to return for that, [[x], []]? \$\endgroup\$ – FryAmTheEggman Jun 10 '15 at 1:31
  • \$\begingroup\$ I guess so - it's probably OK unless OP says otherwise. \$\endgroup\$ – isaacg Jun 10 '15 at 1:35
  • \$\begingroup\$ @isaacg I've posted an answer below. It gives the correct answer for 1 element (I had to add one more byte to the code) \$\endgroup\$ – Renae Lider Jun 10 '15 at 2:21
6
\$\begingroup\$

CJam, 19 18 bytes

{S+m!{S/1fb:*}$W=}

This is an anonymous function that pops an array of integers from the stack and returns an array of integers separated by a space.

Thanks to @jimmy23013 for his ingenious :* trick, which saved 1 byte.

Try it online in the CJam interpreter.

How it works

S+    e# Append a space to the array of integers.
m!    e# Push the array of all possible permutations.
{     e# Sort the array by the following:
  S/  e#   Split the array at the space.
  1fb e#   Add the integers in each chunk (using base 1 conversion).
  :*  e#   Push the product of both sums.
}$    e# Permutations with a higher product will come last.
W=    e# Select the last permutation.

Denote the total weight of the shopping bags with W. Then, if the bags in one of the hands weigh W/2 - D/2, those in the other hand must weigh and W - (W/2 - D/2) = W/2 + D/2.

We are trying to minimize the difference D. But (W/2 - D/2)(W/2 + D/2) = W^2/4 - D^2/4, which becomes larger as D becomes smaller.

Thus, the maximal product corresponds to the minimal difference.

\$\endgroup\$
  • \$\begingroup\$ I think :*...W= should work. \$\endgroup\$ – jimmy23013 Jun 10 '15 at 18:52
  • \$\begingroup\$ @jimmy23013: Thanks! That made my answer a whole lot more interesting. \$\endgroup\$ – Dennis Jun 10 '15 at 19:10
5
\$\begingroup\$

Python 2.7, 161, 160

code

from itertools import*
m=input();h=sum(m)/2.;d=h
for r in(c for o in range(len(m)+1) for c in combinations(m,o)):
 t=abs(h-sum(r))
 if t<=d:d=t;a=r
print a

Algorithm

2 x Wone hand = Total weight
Wone hand ~ Total weight / 2

Check if each combination is getting closer to half of total weight. Iterate and find the best one.

input

>>>[1,2,3,4]

output

(2, 3)

The displayed tuple goes in one hand, the ones that are not displayed goes in the other (it is not against the rules).

\$\endgroup\$
  • \$\begingroup\$ You could save one byte by doing from itertools import* \$\endgroup\$ – DJMcMayhem Jun 10 '15 at 21:05
4
\$\begingroup\$

JavaScript (ES6) 117

Using a bit mask to try every possible split, so it is limited to 31 items (ok with the rules). Like the ref answer it outputs just one hand. Note: i look for the minimum difference >=0 to avoid Math.abs, as for each min < 0 there is another > 0, just swapping hands.

To test: run the snippet in Firefox, input a list of numbers comma or space separated.

f=(l,n)=>{ // the unused parameter n is inited to 'undefined'
  for(i=0;++i<1<<l.length;t<0|t>=n||(r=a,n=t))
    l.map(v=>(t+=i&m?(a.push(v),v):-v,m+=m),m=1,t=0,a=[]);
  alert(r)
}

// Test

// Redefine alert to avoid that annoying popup when testing
alert=x=>O.innerHTML+=x+'\n';

go=_=>{
  var list=I.value.match(/\d+/g).map(x=>+x); // get input and convert to numbers
  O.innerHTML += list+' -> ';
  f(list);
}
#I { width: 300px }
<input id=I value='7 7 7 10 11'><button onclick='go()'>-></button>

<pre id=O></pre>

\$\endgroup\$
2
\$\begingroup\$

Haskell, 73 bytes

import Data.List
f l=snd$minimum[(abs$sum l-2*sum s,s)|s<-subsequences l]

Outputs a list of items in one hand. The missing elements go to the other hand.

Usage: f [7,7,7,10,11] -> [7,7,7]

For all subsequences s of the input list l calculate the absolute value of the weight difference between s and the missing elements of l. Find the minimum.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 51 bytes

f l=snd$minimum$((,)=<<abs.sum)<$>mapM(\x->[x,-x])l

Output format is that left-hand weights are positive and right-hand weights are negative.

>> f [2,1,5,4,7]
[-2,-1,5,4,-7]

To generate every possible split, we use mapM(\x->[x,-x])l to negate every possible subset of elements. Then, ((,)=<<abs.sum) labels each one with its absolute sum and snd$minimum$((,)=<<abs.sum) take the smallest-labeled element.

I couldn't get it point-free because of type-checking issues.

\$\endgroup\$
  • \$\begingroup\$ @WillNess They are all in prelude in the current version. \$\endgroup\$ – xnor Sep 17 '16 at 18:51
  • \$\begingroup\$ BTW the following point-free code works at the GHCi prompt: snd.minimum.map((,)=<<abs.sum).mapM(\x->[x,-x]). It's 47 bytes. (though I do have an older version installed...) \$\endgroup\$ – Will Ness Sep 17 '16 at 22:30
0
\$\begingroup\$

R (234)

a longer and slower solution with R.

Function:

function(p){m=sum(p)/2;n=100;L=length(p);a=matrix(0,n,L+2);for(i in 1:n){idx=sample(1:L,L);a[i,1:L]=idx;j=1;while(sum(p[idx[1:j]])<=m){a[i,L+1]=abs(sum(p[idx[1:j]])-m);a[i,L+2]=j;j=j+1}};b=which.min(a[,L+1]);print(p[a[b,1:a[b,L+2]]])}


Expected input - vector with the weights.
Expected output - vector with the weights for one hand.


Example

> Weight(c(1,2,3,4))
[1] 3 2
> Weight(c(10,1,2,3,4))
[1] 10
> Weight(c(40,20,80,50,100,33,2))
[1] 100  40  20  2
> Weight(c(7,7,7,10,11))
[1] 7 7 7

Human readable code version:

weight <- function(input) {
  mid <- sum(input)/2
  n <- 100
  input_Length <- length(input)
  answers <- matrix(0, n, input_Length+2)
  for(i in 1:n){
    idx <- sample(1:input_Length, input_Length)
    answers[i, 1:input_Length ] <- idx
    j <- 1
    while(sum(input[idx[1:j]]) <= mid){
        answers[i, input_Length+1] <- abs(sum(input[idx[1:j]]) - mid)
        answers[i, input_Length+2] <- j
        j <- j + 1
    }
  }
  best_line <- which.min(answers[, input_Length+1])
  print(paste("weight diference: ", answers[best_line, input_Length+1]))
  print(input[answers[best_line, 1:answers[best_line, input_Length+2]]])
}
\$\endgroup\$
0
\$\begingroup\$

Axiom, 292 bytes

R==>reduce;F(b,c)==>for i in 1..#b repeat c;p(a)==(#a=0=>[a];w:=a.1;s:=p delete(a,1);v:=copy s;F(s,s.i:=concat([w],s.i));concat(v,s));m(a)==(#a=0=>[[0],a];#a=1=>[a,a];b:=p(a);r:=[a.1];v:=R(+,a)quo 2;m:=abs(v-a.1);F(b,(b.i=[]=>1;d:=abs(v-R(+,b.i));d<m=>(m:=d;r:=copy b.i);m=0=>break));[[m],r])

A brute force application. This would minimize the set

A={abs(reduce(+,a)quo 2-reduce(+,x))|x in powerSet(a)}

because if is minimum

y=min(A)=abs(reduce(+,a)quo 2-reduce(+,r))

it would be minimum too

2*y=abs(reduce(+,a)-2*reduce(+,r))=abs((reduce(+,a)-reduce(+,r))-reduce(+,r)) 

where (reduce(+,a)-reduce(+,r)) and reduce(+,r) are the 2 weight of two bags.( But that last formula not find to me the minimum, in the application). Ungolf and results

-- Return the PowerSet or the Powerlist of a
powerSet(a)==
    #a=0=>[a]
    p:=a.1;s:=powerSet delete(a,1);v:=copy s
    for i in 1..#s repeat s.i:=concat([p],s.i)
    concat(v,s)

-- Return one [[m], r] where
-- r is one set or list with reduce(+,r)=min{abs(reduce(+,a)quo 2-reudece(+,x))|x in powerSet(a)}
-- and m=abs(reduce(+,a) quo 2-reduce(+,r))
-- because each of two part, has to have the same weight
MinDiff(a)==
    #a=0=>[[0],a]
    #a=1=>[ a ,a]
    b:=powerSet(a)
    r:=[a.1];v:=reduce(+,a) quo 2;m:=abs(v-a.1)
    for i in 1..#b repeat
        b.i=[]=>1
        k:=reduce(+,b.i)
        d:=abs(v-k)
        d<m=>(m:=d;r:=copy b.i)
        m=0=>break
    [[m],r]

--Lista random di n elmenti, casuali compresi tra "a" e "b"
randList(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

(5) -> a:=randList(12,1,10000)
   (5)  [8723,1014,2085,5498,2855,1121,9834,326,7416,6025,4852,7905]
                                                       Type: List Integer
(6) -> m(a)
   (6)  [[1],[1014,2085,5498,1121,326,6025,4852,7905]]
                                                  Type: List List Integer
(7) -> x:=reduce(+,m(a).2);[x,reduce(+,a)-x]
   (7)  [28826,28828]
                                               Type: List PositiveInteger
(8) -> m([1,2,3,4])
   (8)  [[0],[2,3]]
                                                  Type: List List Integer
(9) -> m([10,1,2,3,4])
   (9)  [[0],[10]]
                                                  Type: List List Integer
(10) -> m([40,20,80,50,100,33,2])
   (10)  [[0],[40,20,100,2]]
                                                  Type: List List Integer
(11) -> m([7,7,7,10,11])
   (11)  [[0],[10,11]]
                                                  Type: List List Integer
\$\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.