about summary refs log tree commit diff
path: root/scratch/facebook/stacking-boxes.py
blob: 7a3304bc51b9527c27e235f321c1298f070d03e9 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from random import randint

class Box(object):
    def __init__(self, w, h, d):
        self.width  = w
        self.depth  = d
        self.height = h

    def __repr__(self):
        return "{}x{}x{}".format(self.width, self.depth, self.height)

    def lt(self, b):
        return all([
            self.width  < b.width,
            self.height < b.height,
            self.depth  < b.depth,
        ])

    def gt(self, b):
        return all([
            self.width  > b.width,
            self.height > b.height,
            self.depth  > b.depth,
        ])

def random_box():
    return Box(
        randint(1, 10),
        randint(1, 10),
        randint(1, 10),
    )

xs = [random_box() for _ in range(5)]

def highest_stack(xs, cache={}):
    if not xs:
        return 0
    heights = []
    for i in range(len(xs)):
        x, rest = xs[i], xs[0:i] + xs[i+1:]
        if cache and x in cache:
            height = cache[x]
        else:
            height = x.height + highest_stack([b for b in rest if x.gt(b)], cache)
            cache[x] = height
        heights += [height]
    return max(heights)

print(xs)
print(highest_stack(xs))