You are a package handler for Big CompanyTM and your job is to load boxes into a truck. These are special, stretchy trucks: their length can be adjusted at will. But stretching trucks are expensive, so keep the truck lengths as short as possible!
The Challenge
Write a full program or function that, when given the truck's height and width, and a list of cuboid boxes, outputs the minimum truck length for that sequence.
Input
Your program has 2 inputs:
- The truck's height and width: a 2-tuple of positive integers
- The boxes to pack: a list of 3-tuples of positive integers
Each box is represented as a 3-tuple of numbers, representing their height, width, and length. It is guaranteed that boxes will be smaller than or the same size as the height and width of the truck.
You can freely rotate the boxes any number of times in 90-degree intervals. You can freely reorder the list of boxes.
You can freely rotate the truck around its length axis, i.e. a (3,5)
truck is the same as a (5,3)
truck.
Output
Your program must output the minimum length of the truck needed to pack all of the boxes.
Additional Rules
- Standard loopholes are forbidden.
- Input and output can be in any reasonable format.
- This is code-golf, so shortest code wins!
Test Cases
(truck h, w) [(box h, w, l)...] -> truck length
(1,1) [(1,1,1)] -> 1
(a single box)
(1,1) [(1,1,1) (1,1,1)] -> 2
(a line of two 1x1x1 boxes)
(2,1) [(1,1,1) (1,1,1)] -> 1
(two boxes stacked)
(1,2) [(1,1,1) (1,1,1)] -> 1
(two boxes on the floor, next to each other)
(5,7) [(3,3,5) (1,1,1) (1,2,2)] -> 3
(3x3x5 box is rotated such that it is parallel long-side-wise on the floor)
(5,7) [(5,3,5) (5,7,1) (5,2,2) (5,2,2)] -> 5
(the 5x7x1 box on the back wall, the 5x2x2 boxes next to each other)
(4,4) [(3,2,5) (2,2,3) (2,2,4) (2,2,6)] -> 7
(3x2x5 forces 2x2x3 and 2x2x4 to be length-wise adjacent)
(5,5) [(1,1,1) (2,2,2) (3,3,3) (4,4,4) (5,5,5)] -> 12
(3x3x3 4x4x4 5x5x5 boxes adjacent, 1x1x1 and 2x2x2 crammed into empty space)
(5,5) [(1,1,1) (2,2,2) (3,3,3) (4,4,4) (5,5,5) (1,8,5)] -> 13
(same arrangement as above, but 1x8x5 is squeezed between the wall and 4x4x4)
```
(5,7) [(5,3,5) (5,7,1) (5,2,2) (5,2,2)] -> 5
. I think those two test cases are incorrect. \$\endgroup\$