Packing Cuboid Boxes into the Shortest Stretchy Truck

Question

You are a package handler for Big Company^TM 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)
```

Answer 1

Ruby, 292... 228 bytes

->t,b{1.step.find{|l|[p].product(*b.map{|c|c.permutation.flat_map{|x,y,z|[*x..t[0]].product([*y..t[1]],[*z..l]).map{|i,j,k|[i-x...i,j-y...j,k-z...k]}}}).any?{|c|c.combination(2).none?{|a,b|a&.zip(b)&.all?{|x,y|[*x]&[*y]!=[]}}}}}

Try it online!

Probably still a lot left to optimize.

Can get the 6th test case on TIO in 17 seconds by adding a uniq after permutation. No way to get more than that.

Explanation:

Brute force approach, pure and simple. Start with length 1, rotate all the boxes, and try all the possible translations. If there is no way to fit them, increase length and try again.

Answer 2

Jelly, 44 bytes

_⁹żAƑƇŻ€,Œp€+þ@/ʋ/€Ẏ
Œ!€⁹,1W;"çⱮ/pẎ€QƑƇɗ/ʋ1#

Try it online!

A dyadic pair of links taking a list of boxes as the left argument and the truck’s first two dimensions as the right argument. Returns the result as an integer. Very inefficient as the boxes and truck get bigger and do times out on TIO even on the fifth test case.

Explanation

Helper link

Takes three truck dimensions on the left and a list of permuted boxes on the right. Returns a list of lists of coordinates for all possible translated and rotated versions of that box

_⁹                    | Subtract the permuted boxes from the truck
  ż                   | Zip each with the relevant permuation
   AƑƇ                | Keep only those that are non-negative (by checking whether the numbers are changed when absoluted)
                ʋ/€   | For each of the remaining ones, reduce using the following:
      Ż€              | - For each of the (truck-box) dimensions, generate a list from zero to that number
        ,             | - Pair with the box dimensions
         Œp€          | - Cartesian products of each
            +þ@/      | - Reduce using outer addition (generates a list of lists of coordinates for each cell of the translations of that permuation of the box)
                   Ẏ  | Tighten

Main link

Œ!€                     | Permutations of each box’s dimensions
   ⁹,                   | Pair truck dimensions with this (call this y)
     1              ʋ1# | Starting with 1, find the first integer x which satisfies the following, using y as the right argument:
      W;"               | - Wrap and concatenate zipped; effectively prepends x to the first member of y (the truck’s two dimensions)
         çⱮ/            | - Call the helper link with the three truck dimensions on the left for each box’s permutations on the right
                  ɗ/    | - Reduce the results of the helper link with the following:
            p           |   - Cartesian product
             Ẏ€         |   - Tighten (concatenate outer lists)
               QƑƇ      |   - Check whether unchanged on uniquifying (i.e. are there any duplicates?)