Given a pile of disks (2D array – list of lists), each has (width, depth, height) characteristics. The mission is to pile them up and to maximize the total height of the pile. Constraint is – a disk must have strictly smaller width, depth, and height than any other disks below it.
Your function should return an array of the disks in the final pile, starting with the top disk and ending with the bottom disk. You cannot rotate the disk, the disks should be always in the (width, depth, height) order.
Question – can my program be further optimized to better performance? Current it’s O(n^2) time.
Example: Input disks = ((4, 5, 4), (2, 3, 4), (1, 3, 1), (2, 3, 4), (2, 1, 2), (3,2,3))
Output should be: ((2, 1, 2), (3, 2, 3), (4, 5, 4))
# O(n^2) time | O(n) space def disk_piling(disks): disks.sort(key=lambda d: d(2)) #print(disks) heights = (d(2) for d in disks) piles = (None for _ in disks) maxHIndex = 0 for i in range(1, len(disks)): current = disks(i) for j in range(i): nxt = disks(j) if is_valid(nxt, current): print(heights(i), current(2), heights(j)) if heights(i) <= current(2) + heights(j): heights(i) = current(2) + heights(j) piles(i) = j if heights(i) >= heights(maxHIndex): maxHIndex = i return build_Piles(disks, piles, maxHIndex) def is_valid(other, current): return all(other(i) < current(i) for i in (0, 1, 2)) def build_Piles(A, sequences, current): result = () while current is not None: result.append(A(current)) current = sequences(current) return list(reversed(result)) if __name__ == '__main__': # (width, depth, height) disks = ((2, 1, 2), (3, 2, 3), (1, 3, 1), (2, 3, 4), (4, 5, 4), (2, 2, 8)) print(disk_piling(disks))