Stacking boxes into fewest number of stacks efficiently?

Question

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 you can stack one box on top of another if its length and width are less than the other box's.

I can't figure out how to come up with a polynomial time solution. I've built a brute force solution that creates all possible stack arrangements recursively (start with N stacks. Then for each stack, try putting it on top of each other stack. Then recursively generate all stack possibilities given the new stack arrangement.), and then returns the smallest number of stacks needed.

I've sped it up with a few optimizations:

• If you can stack box A on top of box B and box C, and you can stack box B on top of box C, then do not consider stacking box A on box C.
• Memoize the stack arrangements, only considering the bottom and top levels of the stacks

Here's the python code for this solution:

from time import time

def all_stacks(bottom, top, d={}):

    memo_key = (tuple(bottom), tuple(top))
    if memo_key in d:
        # print "Using MEMO"
        return d[memo_key]

    res = len(bottom)
    found = False
    stack_possibilities = {}
    # try to stack the smallest boxes in all the other boxes
    for j, box1 in enumerate(bottom):
        stack_possibilities[j] = []
        for i, box2 in enumerate(top[j:]):
            # box1 fits in box2
            if fits(box2, box1):
                stack_possibilities[j].append(i + j)
                found = True

    for fr, to_list in stack_possibilities.iteritems():
        indices_to_keep = []
        for box_ind in to_list:
            keep = True
            for box_ind_2 in to_list:
                if fits(top[box_ind], top[box_ind_2]):
                    keep = False
            if keep:
                indices_to_keep.append(box_ind)
        stack_possibilities[fr] = indices_to_keep


    if found:
        lens = []
        for fr, to_list in stack_possibilities.iteritems():
            # print fr
            for to in to_list:
                b = list(bottom)
                t = list(top)
                t[to] = t[fr]
                del b[fr]
                del t[fr]
                lens.append(all_stacks(b, t, d))
        res = min(lens)

    d[memo_key] = res

    return res

def stack_boxes_recursive(boxes):
    boxes = sorted(boxes, key=lambda x: x[0] * x[1], reverse=False)
    stacks = all_stacks(boxes, boxes)
    return stacks

def fits(bigbox, smallbox):
    b1 = smallbox[0] < bigbox[0]
    b2 = smallbox[1] < bigbox[1]
    return b1 and b2


def main():

    n = int(raw_input())
    boxes = []
    for i in range(0,n):
        l, w = raw_input().split()
        boxes.append((long(l), long(w)))
    start = time()
    stacks = stack_boxes_recursive(boxes)
    print time() - start

    print stacks


if __name__ == '__main__':
    main()

Input

17
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

Output:

33.7288980484
6

The algorithm solves a 16 box problem in a few seconds (1-3), a 17 box problem in ~30 seconds. I'm pretty sure this is exponential time. (Since there's an exponential number of stack arrangements).

I'm pretty sure there's a polynomial time solution, but I don't know what it is. One of the issues is that memoization depends on the current stack arrangements, meaning you have to do more computations.

Answer 1

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!

Answer 2

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.

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

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

  function getBest(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]]);
    return getBest(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);
  return getBest(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.

function boxBoxes(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;
                       },void 0);
}

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));

Answer 3

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.