An immutable (and hashable) set of Boxes.
| 47 | pass |
| 48 | |
| 49 | class Stack(frozenset): |
| 50 | """ An immutable (and hashable) set of Boxes. """ |
| 51 | |
| 52 | def stackable_on(self, bottom): |
| 53 | """ Return a Stack with the Boxes that can be stacked on 'bottom'. """ |
| 54 | return Stack(box for box in self if box < bottom) |
| 55 | |
| 56 | def subtract(self, box): |
| 57 | """ Return a new Stack with 'box' removed. """ |
| 58 | return Stack(b for b in self if b != box) |
| 59 | |
| 60 | @staticmethod |
| 61 | def height(seq): |
| 62 | """ Return the height of a valid stack of Boxes. |
| 63 | |
| 64 | The Boxes must be given in a sorted sequence, where the first element |
| 65 | is the bottom of the stack and the last one its top. In other words: |
| 66 | the box at index i must be strictly larger in width, height and depth |
| 67 | than the box at index i + 1. AssertionError is raised otherwise. |
| 68 | |
| 69 | """ |
| 70 | |
| 71 | if __debug__: |
| 72 | for index in xrange(0, len(seq) - 1): |
| 73 | assert seq[index] > seq[index + 1] |
| 74 | |
| 75 | return sum(box.height for box in seq) |
| 76 | |
| 77 | @memoize |
| 78 | def find_tallest(self): |
| 79 | """ Return a sorted list with the Boxes that build the highest Stack. """ |
| 80 | |
| 81 | # In order to build the highest stack, we need to try each of the boxes |
| 82 | # as a possible bottom and find the height of the tallest stack than we |
| 83 | # can obtain with it. This height is equal to the height of the bottom |
| 84 | # box plus the height of the highest substack -- a recursive algorithm. |
| 85 | # These substacks can only be built using the boxes that are strictly |
| 86 | # smaller than the bottom. |
| 87 | |
| 88 | if not self: |
| 89 | return [] |
| 90 | |
| 91 | # Map each box to the highest substack we can build with it as bottom |
| 92 | substacks = dict() |
| 93 | for box in self: |
| 94 | stack_ = self.subtract(box) |
| 95 | stackable = stack_.stackable_on(box) |
| 96 | substacks[box] = stackable.find_tallest() |
| 97 | |
| 98 | # Find the box for which the total height (its own height plus that |
| 99 | # of the tallest substack) is the highest, and use it as the bottom. |
| 100 | total_height = lambda x: x[0].height + Stack.height(x[1]) |
| 101 | bottom, stack_ = max(substacks.iteritems(), key=total_height) |
| 102 | return [bottom] + stack_ |
| 103 | |
| 104 | |
| 105 | class StackTest(unittest.TestCase): |
no outgoing calls