How could we split an array into two new ones which their weight differences are minimal?

Question

I am doing the following programming exercise: Stone pile. The statement is:

You are given pile of stones with different weights.

Your task is to divide this stone pile into two parts, so the weight difference between the piles will be minimal. You can't break one stone into smaller ones.

For example if we have stones:

[1, 2, 3, 4]

We could divide them into:

[2, 3], [1, 4]

So the difference will be 0

If you are given empty stone pile, you can still divide it into two piles with no stones.

The pile will contain maximum 22 stones.

Following the examples I have thought:

Sort stones in ascending order
for each stone
 if length is even
  if movement is even
   add min and max to right list
   remove them
  if movement is odd
   add min and max to left list
   remove them

 if length is odd
  if movement is even
   add max to left
   remove it
  if movement is odd
   add min to right
   remove it
   if there are more items
   add next min
   remove it

So in code would be:

import java.util.*;
import java.util.stream.*;

public class Pile {
    public static int minDiff(int[] stones) {
      System.out.println("stones: "+Arrays.toString(stones));
      Arrays.sort(stones);
      System.out.println("stones: "+Arrays.toString(stones));

      List<Integer> allStones = Arrays.stream(stones).boxed().collect(Collectors.toList());
      System.out.println("allStones: "+Arrays.toString(allStones.toArray()));
      ArrayList<Integer> left = new ArrayList<>();
      ArrayList<Integer> right = new ArrayList<>();

      for(int i = 0; allStones.size()>0; i++){
        if(stones.length%2==0){
          if(i%2==0){
            right.add(allStones.get(0));
            right.add(allStones.get(allStones.size()-1));
            allStones.remove(0);
            allStones.remove(allStones.size()-1);
          }else{
            left.add(allStones.get(0));
            left.add(allStones.get(allStones.size()-1));
            allStones.remove(0);
            allStones.remove(allStones.size()-1);
          }
        }else{
          if(i%2==0){
            left.add(allStones.get(allStones.size()-1));
            allStones.remove(allStones.size()-1);
          }else{
            right.add(allStones.get(0));
            allStones.remove(0);
            if(allStones.size()>0){
              right.add(allStones.get(0));
              allStones.remove(0);
            }
          }
        }
      }
      System.out.println("left: "+Arrays.toString(left.toArray()));
      System.out.println("right: "+Arrays.toString(right.toArray()));
      return left.stream().mapToInt(Integer::intValue).sum()-right.stream().mapToInt(Integer::intValue).sum();
    }
}

Currently it is just working when we test it with inputs where the difference is zero. However if we test it with other inputs, it will fail.

Given the following tests, the first suite will pass, the others fail:

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class PersonTest {

    @Test
    public void testDifferenceShouldBeZero(){
        assertEquals(0, Pile.minDiff(new int[]{1, 2, 3}));
        assertEquals(0, Pile.minDiff(new int[]{1, 2, 3, 4}));
        assertEquals(0, Pile.minDiff(new int[]{5,5,4,3,3}));
    }

    @Test
    public void testDifferenceShouldBeOne(){
        assertEquals(1, Pile.minDiff(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}));
    }

    @Test
    public void testDifferenceShouldBeTwo(){
        assertEquals(2, Pile.minDiff(new int[]{89409, 34351, 3065, 10128, 27694, 27585, 87350, 33875, 2658, 41606, 57512, 73368, 83345, 37048, 31827, 94644, 15972, 74813, 31441, 70395}));
    }

}

For example, when stones are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]

Trace is:

stones: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
stones: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
allStones: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
left: [2, 21, 4, 19, 6, 17, 8, 15, 10, 13]
right: [1, 22, 3, 20, 5, 18, 7, 16, 9, 14, 11, 12]

Being the result:

expected:<1> but was:<-23>

How could we split the stone pile in two chunks where the difference is the minimum, for the general case?

We have read:

Krzysztof Cichocki · Answer 1 · 2020-03-15T12:53:26.470

I would use bit combination to divide the stones into two groups and sum up every possible combination, comparing them to choose the one with lowest difference:

import java.util.Arrays;
import java.util.LinkedList;

public class Pile {
    /**
     * return solution as int, if bit is set use the "bitNumber" as index for stone
     * for one side, otherwise for the other
     **/
    private static int divide(int[] stones) {
        int solution = -1;
        long minDifference = Long.MAX_VALUE;
        for (int n = 0; n < (1 << (stones.length + 1)); n++) {
            long sumLeft = 0;
            long sumRight = 0;
            for (int bit = 0; bit < stones.length; bit++) {
                boolean isSet = (n & (1 << bit)) > 0;
                if (isSet) {
                    sumLeft += stones[bit];
                } else {
                    sumRight += stones[bit];
                }

            }
            long diff = Math.abs(sumLeft - sumRight);
            if (diff < minDifference) {
                solution = n;
                minDifference = diff;
            }

        }
        return solution;
    }

    public static long minDiff(int[] stones) {
        int solution = divide(stones);
        long sumLeft = 0;
        long sumRight = 0;

        LinkedList<Integer> left = new LinkedList<>();
        LinkedList<Integer> right = new LinkedList<>();
        for (int bit = 0; bit < stones.length; bit++) {
            boolean isSet = (solution & (1 << bit)) > 0;
            if (isSet) {
                sumLeft += stones[bit];
                left.add(stones[bit]);
            } else {
                sumRight += stones[bit];
                right.add(stones[bit]);
            }
        }
        System.out.println("left: " + Arrays.toString(left.toArray()));
        System.out.println("right: " + Arrays.toString(right.toArray()));
        return Math.abs(sumRight - sumLeft);
    }

}

How could we split an array into two new ones which their weight differences are minimal?

1 Answers1