|
1 | | -#Box stacking dynamic programming |
2 | | -#Java code https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/BoxStacking.java |
3 | | - |
4 | | -class Dimension(object): |
5 | | - |
6 | | - def __init__(self, height = 0, length = 0, width = 0): |
7 | | - self.height = height |
8 | | - self.length = length |
9 | | - self.width = width |
10 | | - |
11 | | - def __lt__(self, other): |
12 | | - return self.length*self.width > other.length*other.width |
13 | | - |
14 | | - def __str__(self): |
15 | | - return str(self.height) + " " + str(self.length) + " " + str(self.width) |
16 | | - |
17 | | - @classmethod |
18 | | - def create_empty(self): |
19 | | - return self(0,0,0) |
20 | | - |
21 | | -def create_dimension(height, side1, side2): |
22 | | - d = Dimension(); |
23 | | - d.height = height |
24 | | - if side1 > side2 : |
25 | | - d.length = side1 |
26 | | - d.width = side2 |
27 | | - else: |
28 | | - d.width = side1 |
29 | | - d.length = side2 |
30 | | - return d; |
31 | | - |
32 | | -def max_height(dimensions): |
33 | | - all_rotations = create_all_rotations(dimensions) |
34 | | - all_rotations.sort() |
35 | | - T = [] |
36 | | - result = [] |
37 | | - for i in range(len(all_rotations)): |
38 | | - T.append(all_rotations[i].height) |
39 | | - result.append(i) |
40 | | - |
41 | | - for i in range(1, len(T)): |
| 1 | +""" |
| 2 | +Problem Statement |
| 3 | +================= |
| 4 | +
|
| 5 | +Given different dimensions and unlimited supply of boxes for each dimension, stack boxes on top of each other such that |
| 6 | +it has maximum height but with caveat that length and width of box on top should be strictly less than length and width |
| 7 | +of box under it. You can rotate boxes as you like. |
| 8 | +
|
| 9 | +1) Create all rotations of boxes such that length is always greater or equal to width |
| 10 | +2) Sort boxes by base area in non increasing order (length * width). This is because box |
| 11 | + with more area will never ever go on top of box with less area. |
| 12 | +3) Take T[] and result[] array of same size as total boxes after all rotations are done |
| 13 | +4) Apply longest increasing subsequence type of algorithm to get max height. |
| 14 | +
|
| 15 | +Analysis |
| 16 | +-------- |
| 17 | +If n number of dimensions are given total boxes after rotation will be 3n. |
| 18 | +* Space complexity is O(n) |
| 19 | +* Time complexity - O(nlogn) to sort boxes. O(n^2) to apply DP on it So really O(n^2) |
| 20 | +
|
| 21 | +Video |
| 22 | +----- |
| 23 | +* https://youtu.be/9mod_xRB-O0 |
| 24 | +
|
| 25 | +References |
| 26 | +---------- |
| 27 | +* http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/ |
| 28 | +* http://people.cs.clemson.edu/~bcdean/dp_practice/ |
| 29 | +""" |
| 30 | + |
| 31 | +from collections import namedtuple |
| 32 | +from itertools import permutations |
| 33 | + |
| 34 | +dimension = namedtuple("Dimension", "height length width") |
| 35 | + |
| 36 | + |
| 37 | +def create_rotation(given_dimensions): |
| 38 | + """ |
| 39 | + A rotation is an order wherein length is greater than or equal to width. |
| 40 | +
|
| 41 | + :param given_dimensions: Original box dimensions |
| 42 | + :return: All the possible rotations of the boxes with the condition that length >= height. |
| 43 | + """ |
| 44 | + for current_dim in given_dimensions: |
| 45 | + for (height, length, width) in permutations((current_dim.height, current_dim.length, current_dim.width)): |
| 46 | + if length >= width: |
| 47 | + yield dimension(height, length, width) |
| 48 | + |
| 49 | + |
| 50 | +def sort_by_decreasing_area(rotations): |
| 51 | + return sorted(rotations, key=lambda dim: dim.length * dim.width, reverse=True) |
| 52 | + |
| 53 | + |
| 54 | +def can_stack(box1, box2): |
| 55 | + return box1.length < box2.length and box1.width < box2.width |
| 56 | + |
| 57 | + |
| 58 | +def box_stack_max_height(dimensions): |
| 59 | + boxes = sort_by_decreasing_area([rotation for rotation in create_rotation(dimensions)]) |
| 60 | + num_boxes = len(boxes) |
| 61 | + T = [rotation.height for rotation in boxes] |
| 62 | + R = [idx for idx in range(num_boxes)] |
| 63 | + |
| 64 | + for i in range(1, num_boxes): |
42 | 65 | for j in range(0, i): |
43 | | - if(all_rotations[i].length < all_rotations[j].length |
44 | | - and all_rotations[i].width < all_rotations[j].width): |
45 | | - T[i] = T[j] + all_rotations[i].height; |
46 | | - result[i] = j |
47 | | - max_height = 0 |
48 | | - for m in T: |
49 | | - max_height = max(m, max_height) |
| 66 | + if can_stack(boxes[i], boxes[j]): |
| 67 | + if (T[j] + boxes[i].height) > T[i]: |
| 68 | + T[i] = T[j] + boxes[i].height |
| 69 | + R[i] = j |
| 70 | + |
| 71 | + max_height = max(T) |
| 72 | + start_index = T.index(max_height) |
| 73 | + |
| 74 | + # Prints the dimensions which were stored in R list. |
| 75 | + while True: |
| 76 | + print boxes[start_index] |
| 77 | + next_index = R[start_index] |
| 78 | + if next_index == start_index: |
| 79 | + break |
| 80 | + start_index = next_index |
50 | 81 |
|
51 | 82 | return max_height |
52 | 83 |
|
53 | | -def create_all_rotations(dimensions): |
54 | | - all_rotated_dimensions = [] |
55 | | - for dimension in dimensions: |
56 | | - new_dimension = create_dimension(dimension.height, dimension.length, |
57 | | - dimension.width) |
58 | | - all_rotated_dimensions.append(new_dimension) |
59 | | - new_dimension = create_dimension(dimension.length, dimension.height, |
60 | | - dimension.width) |
61 | | - all_rotated_dimensions.append(new_dimension) |
62 | | - new_dimension = create_dimension(dimension.width, dimension.height, |
63 | | - dimension.length) |
64 | | - all_rotated_dimensions.append(new_dimension) |
65 | | - return all_rotated_dimensions |
66 | | - |
67 | | -max = max_height([Dimension(3,2,5), Dimension(1,2,4)]) |
68 | | -print("Max height", max); |
69 | 84 |
|
| 85 | +if __name__ == '__main__': |
| 86 | + |
| 87 | + d1 = dimension(3, 2, 5) |
| 88 | + d2 = dimension(1, 2, 4) |
| 89 | + |
| 90 | + assert 11 == box_stack_max_height([d1, d2]) |
0 commit comments