Stacking Boxes Into Fewest Number Of Stacks Efficiently?

I got this question in an online coding challenge. Given a list of boxes with length and widths (l, h), output the minimum number of stacks needed to contain all boxes, given that

Solution 1:

Let's build a graph, where there is vertex for each box and an edge from a box A to a box B if A can be stacked on top of B. This graph is acyclic (because "can stack on top" is a transitive relation and a boxed can't stacked on top of itself).

Now we need to find the minimum path cover of this graph. It's a standard problem and it's solved this way:

1. Let's build a bipartite graph (each vertex in the original graph gets two "copies" in the left and the right part). For each A->B edge in the original graph, there is an edge between the left copy of A and the right copy of B.

2. The answer is number of boxes minus the size of the maximum matching in the bipartite graph.

The bipartite graph as O(n) vertices and O(n^2) edges. If we use, for instance, Kuhn's algorithm to find a matching, the total time complexity is O(n^3), where n is the number of boxes.

Solution 2:

I came across this question recently too. I propose the following O(NlogN) solution:

1) Maintain a list AllStkTops of the topmost box of all the current box-stacks that are being used. It would be initialized to an empty list.

2) Sort the boxes in decreasing order of their lengths. (if the lengths are equal, then sort them in increasing (yes, not decreasing) order of breadths).

3) Start picking the boxes (starting from the longest) and put them in one of the current stacks. For the first box, there will be no stacks, so it would be the foundation of the first box-stack. The second box will either go to the top of the first box or would be the base of second stack. As we continue with this process, we would realize that for any box in hand, its length is going to be smaller or equal to the topmost box of all the stacks. Therefore, we only need to worry about the breadth. Check its breadth with the tops of all current stacks starting from the first stack, and put it on the top of the stack that will have i) length and breadth being strictly larger than that of the current box, and ii) minimum possible breadth (for optimality). If none of the stacks can accommodate this box, create a new stack with this box as its base.

Note that the breadth of all stack tops would be in increasing order since we only create a new stack when the breadth of the box goes bigger than all the stack tops at that point of time. (For the case of equal length boxes, we already had them in increasing order of breadths while sorting). Therefore, we can use a binary search procedure to find a narrowest stack top that would have sufficiently large breadth. But we would also need to ensure that its length is strictly larger (and not just equal to) than that of the given box. However, I claim that the length of the top would never be an issue because i) Boxes are picked in decreasing order of lengths, so the length of the top cannot be strictly less for sure, and ii) It could also not be equal because we already sorted the boxes with equal lengths in increasing order of their breadths, so the stack that got the previous box would have to be towards the left of this stack top.

Therefore, we can use a binary-search procedure to find the optimal stack top for the current box.

We can repeat the above procedure until we place all the boxes in the stacks. At the end, count the number of stacks in AllStkTops.

This is O(NlogN) in complexity since sorting takes O(NlogN) time, and binary search for every box takes O(logN) time.

I would love to take any questions and/or flaws that someone finds in my algorithm.

Cheers!

Solution 3:

This looked simple at first but considering the possibilities, quickly turned out to be a tough one. Yet i have managed to implement my algorithm in JS where i feel very confident, plus JS have specialties such as objects being reference types which, in this particular case helped me enormously.

I start with the assumption that we can turn the boxes to have their longer side on the x axis. Then the given 17 boxes are done in-between 4~10 msecs in Chrome and like 15~25 msecs in FF resulting a minimum of 5 boxes in total can contain all 17.

Moreover i have tried a 50 boxes case (each with random dimensions between 1-100). So the 50 box case, depending on how they can fit, resolves in between an unbelievable 250~15000 msecs both in Chrome and FF. I guess 70 is the limit for this job before it gets really boring.

The code can still be boosted in terms of speed but as of now this is how it is. I will try to make a detailed description of the code in a day or two once i have some free time.

functioninsertBoxes(data){
  if (data.length <= 1) return data[0] ? [data] : data;

  functionflatMap(o){
    return o.inside.length ? o.inside.reduce((p,b) => p.concat(flatMap(b).map(f => f.concat(o.id))),[])
                           : [[o.id]];
  }

  functiongetBest(arr, r = []){
    var i = arr.findIndex(a => a.every(i => !used[i])),len,tgt,bests,best;
    if (i === -1) return r;
      len = arr[i].length;
      tgt = arr.slice(i);
    bests = tgt.filter(a => a.length === len && a.every(x => !used[x]));
     best = bests.map((a,i) => [a.reduceRight((p,c) => p + boxes[c].x + boxes[c].y, 0), i])
                 .reduce((p,c) => c[0] < p[0] ? c : p,[Infinity,-1]);
    bests[best[1]].forEach(i => used[i] = true);
    r.push(bests[best[1]]);
    returngetBest(tgt,r);
  }

  var boxes = data.map((e,i) => ({id:i, x:Math.max(e[0],e[1]), y:Math.min(e[0],e[1]), inside:[]})),
       used = Array(data.length).fill(false),
    interim = boxes.map((b,_,a) => { a.forEach(box => (b.x > box.x && b.y > box.y) && b.inside.push(box));
                                     return b;
                                   })
                   .map(b =>flatMap(b))
                   .reduce((p,c) => p.concat(c))
                   .sort((a,b) => b.length-a.length);
  returngetBest(interim).map(b => b.map(i => data[i]))
                         .concat(insertBoxes(data.reduce((p,c,i) => used[i] ? p : (p.push(c),p) ,[])));
}

var input = [[9, 15], [64, 20], [26, 46], [30, 51], [74, 76], [53, 20], [66, 92], [90, 71], [31, 93], [75, 59], [24, 39], [99, 40], [13, 56], [95, 50], [3, 82], [43, 68], [2, 50]];
   result = [],
       ps = 0,
       pe = 0,
ps = performance.now();
result = insertBoxes(input);
pe = performance.now();
console.log("boxing", input.length, "boxes done in:", pe-ps,"msecs and all boxes fit in just", result.length,"boxes");
console.log(JSON.stringify(result));

Note: The above code uses a recursive top to bottom approach yet i have started thinking that a bottom to top dynamical programming approach would be the real solution to this problem.

OK just as i have thought dynamic programming approach results a much faster solution. I am not deleting the above but please disregard it.

The following code would resolve a 17 item boxes array in less than 1ms, 1000 items boxes array in less than 100ms.

functionboxBoxes(d){
  return d.sort((a,b) => b[0]*b[1] - a[0]*a[1])
          .map(b => b[0] < b[1] ? b : [b[1],b[0]])
          .map(function(b,i,a){
                 b.c = i ? a.slice(0,i)
                            .filter(f => f[0] > b[0] && f[1] > b[1]).length || Infinity
                         : Infinity;
                 return [b];
               })
          .sort((a,b) => b[0].c - a[0].c)
          .reduceRight(function(p,c,i,a){
                         var r = a.filter(f => f[f.length-1][0] > c[0][0] &&
                                               f[f.length-1][1] > c[0][1]);
                         r.length && r[0].push(...a.splice(i,1)[0]);
                         return a;
                       },void0);
}

var data = [[9, 15], [64, 20], [26, 46], [30, 51], [74, 76], [53, 20], [66, 92], [90, 71], [31, 93], [75, 59], [24, 39], [99, 40], [13, 56], [95, 50], [3, 82], [43, 68], [2, 50]];
  result = boxBoxes(data);
console.log(result.length,"boxes:",JSON.stringify(result));