Given a list of three values, height, width and length, create a stack of boxes that is as tall as possible. A box can be stacked on top of another box if dimensions of its 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. A box can stack in any orientation and multiple instances of the same type of box is allowed.

Hint

The algorithm creates six possible rotations for each box, for each box can be placed in six different orientations by rotating it on its sides. The list of rotated boxes is sorted in descending order based on their base area (width * length). This ensures that boxes with larger base areas are considered first, as they can potentially support more boxes.

Select a box from the sorted list, checks if the current box's base is smaller than the base of the previous box (in terms of both width and length). If the current box can be placed on top of the previous box, the algorithm recursively calculates the maximum stack height possible by considering the remaining boxes in the list.

In essence, the algorithm explores different stacking combinations by iteratively trying to place boxes on top of each other, ensuring that the base of each box is smaller than the base of the box below it. By recursively exploring all possible combinations and tracking the maximum height, it determines the optimal stacking arrangement to achieve the greatest possible stack height.

# Python implementation

def stack(boxes, i):
  height = boxes[i][2]

  for j in range(i + 1, len(boxes)):
    if boxes[i][0] > boxes[j][0] and boxes[i][1] > boxes[j][1]:
      height = max(height, boxes[i][2] + stack(boxes, j))
  
  return height

data = [[4, 6, 7], [1, 2, 3], [4, 5, 6], [10, 12, 32]]
boxes = []

for x in data:
  a = x[0]
  b = x[1]
  c = x[2]

  boxes.append([a, b, c])
  boxes.append([a, c, b])
  boxes.append([b, a, c])
  boxes.append([b, c, a])
  boxes.append([c, a, b])
  boxes.append([c, b, a])

boxes.sort(key = lambda a: (a[0], a[1]), reverse = True)

print(stack(boxes, 0))

// Javascript implementation

function stack(boxes, i) {
  let height = boxes[i][2];

  for (let j = i + 1; j < boxes.length; j++) {
    if (boxes[i][0] > boxes[j][0] && boxes[i][1] > boxes[j][1]) {
      height = Math.max(height, boxes[i][2] + stack(boxes, j));
    }
  }
  
  return height;
}

const data = [[4, 6, 7], [1, 2, 3], [4, 5, 6], [10, 12, 32]];
const boxes = data
  .reduce((cum, i) => {
    const a = i[0];
    const b = i[1];
    const c = i[2];

    cum.push([a, b, c]);
    cum.push([a, c, b]);
    cum.push([b, a, c]);
    cum.push([b, c, a]);
    cum.push([c, a, b]);
    cum.push([c, b, a]);

    return cum;
  }, [])
  .sort((a, b) => (a[0] == b[0]) ? (b[1] - a[1]) : b[0] - a[0]);

console.log(stack(boxes, 0));

Stacking box

Hint