Finds the tallest possible stack given n boxes and requiring each box to have a smaller length & width than the one beneath it.

BoxStacking.py

###################################################################
#Box Stacking
#Given n boxes (L, W, H), find the height of the tallest
#possible stack. Box (Li, Wi, Hi) can be on top of box (Lj, Wj, Hj)
#if Li < Lj and Wi < Wj
#
#Based on video from Reducible
#Box Stacking: https://www.youtube.com/watch?v=aPQY__2H3tE
###################################################################

#Box Stacking: It computes the max height possible assuming the box in position k is the base. 
#Since the boxes are sorted by length & width, no box after position k can be stacked on top of
#box k. Table is initialised to height of each box since the base case would be no box can be
#stacked so tallest box is the max height. From there build up solution by iterating through
#box list and updating heights with the max height each box can contain when it's the base.

#Checks if boxes can be stacked according to Li < Lj and Wi < Wj
def checkStackBox(box1, box2):
    if box1[0] < box2[0] and box1[1] < box2[1]:
        return True
    return False

#Computes tallest possible height from given boxes w/ dynamic programming. 
def stackBoxes(boxes):
    boxes.sort()
    heights = [i[2] for i in boxes] #Table to track heights
    for i in range(0, len(boxes)): #loops through all boxes once
        box = boxes[i]
        #Storing indices instead of actual boxes since it makes it easier
        #to retrieve values from list of boxes & list of heights. Will be
        #empty if no previous boxes can be stacked on current box
        box_indices = [j for j in range(i) if checkStackBox(boxes[j], box)]
        m  = max([heights[j] for j in box_indices], default = 0) #Default in case box_indices is empty
        heights[i] = box[2] + m
    return max(heights, default = 0) #Default in case heights is empty

#Code below for testing purposes. Remove triple quotations to run
"""
box_list1 = [
    [2, 3, 3],
    [2, 2, 4],
    [4, 4, 2]
    ]

box_list2 = [
    [5, 2, 1],
    [3, 4, 1],
    [5, 3, 3],
    [2, 5, 3],
    [2, 1, 2],
    [4, 1, 5],
    [4, 5, 1],
    [4, 1, 2],
    [2, 2, 4]
    ]

box_list3 = [
    [4, 5, 3],
    [2, 3, 2],
    [3, 6, 2],
    [1, 5, 4],
    [2, 4, 1],
    [1, 2, 2]
    ]

x = stackBoxes(box_list1)
print(x, "\n")

x = stackBoxes(box_list2)
print(x, "\n")

x = stackBoxes(box_list3)
print(x)
"""