Stacking box (Memoization)

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

This algorithm uses memoization to improve performance. It's same as the recursive version of Stacking box, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def stack(boxes, i):
  global cache
  if not cache:
     cache = [None] * len(boxes)

  if not cache[i - 1]:
    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))
    
    cache[i - 1] = height

  return cache[i - 1]

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

let cache = null;

function stack(boxes, i) {
  if (!cache) {
    cache = Array(boxes.length);
  }

  if (cache[i] === undefined) {
    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));
      }
    }
    
    cache[i] = height;
  }

  return cache[i];
}

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