Given a group of boxes, you are requested to arrange these boxes on top of each other to reach the maximum possible height. Note: a box cannot be placed on top of another box unless the area of its 2D base is smaller or equal of the 2D base of the lower box. It is allowed to rotated any box to use any two sides as its base.
For example, consider below 4 boxes where each box has the following dimensions
Input:
Box 1: (4,5,2), Box 2:(3,1,6), Box 3:(3,2,1),
Box 4:(6,8,3)
Output:
From bottom to top as follows:
Box 4 on the base (6,3) and height 8,
then Box 1 on the base (4,2) and height 5, then Box 2 on the base (1,3) and height 6, finally, on top Box 3 on the base (2,1) and height 3.
The total height is 22
[Explanation: as we can see that the first box in the bottom is the box # 4 with base 6×3 and height 8, then box # 1 with base 4×2 and height 5, and so on. This arrangement of boxes fulfils the constraint mentioned above: “the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box”. This solution also satisfies the tallest possible stack]
- Describe how a brute-force approach algorithm would solve the above problem , and explain its complexity .
- Design an algorithm to solve the above scenario for N boxes.[full explanation of your answer should be provided]
- What will happen to the complexity of your efficient algorithm if the constraint “a box cannot be placed on top of another box unless the area of its 2D base is smaller or equal of the 2D base of the lower box” is not required anymore?
- Develop a python code to implement your efficient algorithm.
EXPERT ANSWER
1. Here we don’t have knowledge about the box property. Eg. Box(3,4,5) and Box(5,2,3) We are not aware which is height,length and breadth of the box. In other word the arguments passed to box can be anything. But after further reading we are sure that the maximum of these three arguments will be height. so rest argument will form our base but not sure about length or breadth we know the base area i.e. length*breadth.
2. Now we are aware of two thing height and base area.
Brute Force Approach
1. We start with 1st box and place it on top of stack.
2. Then we take next box(Boxnew) and compare with box on the top of stack (Boxtop) .
3. If (Boxtop) has base greater than (Boxnew). then we will place (Boxnew) on (Boxtop).
4. If (Boxtop) has base smaller than (Boxnew). then we will pop the boxes till It satisfies condition 3
5. The popped boxes will be treated as new box to be pushed.
6. Repeat step 2 to step 5 until no new box left to be pushed.
7. To keep track of height we will add height to a variable(Height = 0, declared initially) when ever a box is pushed and subtract the height whenever a box is popped.
8. Finally we will get height.
Complexity: In the worst case n boxes are to be pushed and popped n times for successful placement of 1 box.The push and pop operation takes O(1) so for 1 push and pop O(1)*2 . Therefore, for n operation O(1)*2*n = 2*O(n) = O(n). This is for 1 box placement. so for n boxes we will need 2*O(n)*n = 2*O(n2).
Total time complexity = O(n2).
# Better way to solve this problem using the following algorithm
1. First we sort the boxes according to thier bases in reverse order. i.e. in descending order.
2. Now we look at the list of boxes it is already placed. From index 0 to n-1. the box at index 0 will be greater or equal base to box at index 1 and so on. So if we have to make a stack we can traverse the list and put the boxes on top of stack and increase height variable.
Complexity: For sorting we have O(nlogn) and for traversing we have O(n).
Total time complexity = O(nlogn) + O(n) = O(nlogn).
This code is for the example said in the problem . For n boxes we can take input and replace the Box list.
class Box:
def __init__(self,a,b,c):
self.a = a
self.b = b
self.c = c
self.height = max(a,b,c)
self.base = a*b*c // self.height
if __name__=="__main__":
#List of boxes
Boxes = []
# box given in example
b1 = Box(4,5,2)
b2 = Box(3,1,6)
b3 = Box(3,2,1)
b4 = Box(6,8,3)
# Add individual box to make a list of Boxes
Boxes.append(b1)
Boxes.append(b2)
Boxes.append(b3)
Boxes.append(b4)
# sort the boxes according to their bases
Boxes.sort(key=lambda x: x.base, reverse=True)
#print boxes after sorting according to their bases
print('Boxes after Sorting: ')
for b in Boxes:
print("base:",b.base,"height:",b.height)
# totalHeight calculation
totalHeight = 0
for b in Boxes:
totalHeight += b.height
# print total height
print('Tallest stack of boxes: ',totalHeight)For n boxes we can use the code
class Box:
def __init__(self,a,b,c):
self.a = a
self.b = b
self.c = c
self.height = max(a,b,c)
self.base = a*b*c // self.height
if __name__=="__main__":
#List of boxes
Boxes = []
n = int(input('Enter no of boxes: '))
for i in range(n):
# enter value separated by space e.g. 4 5 2
abc = list(map(int,input('Enter box {} properties: '.format(i)).split()))
b = Box(abc[0],abc[1],abc[2])
Boxes.append(b)
# sort the boxes according to their bases
Boxes.sort(key=lambda x: x.base, reverse=True)
#print boxes after sorting according to their bases
print('Boxes after Sorting: ')
for b in Boxes:
print("base:",b.base,"height:",b.height)
# totalHeight calculation
totalHeight = 0
for b in Boxes:
totalHeight += b.height
# print total height
print('Tallest stack of boxes: ',totalHeight)
If the constraint is not given : we can place any box on top of any boxes
We can just traverse the list of boxes without sorting it. and take the inc the height variable to keep track of height. We have already calculated the height while creating an instance of boxes. So it’s just to find max of three. Now we can solve the problem in O(n).
Explanation: – O(n) for finding height here n = 3 and O(n) for traversing n boxes . O(n) + O(n) = 2*O(n) = O(n).