9
\$\begingroup\$

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.


Santa has a bunch of presents wrapped in cuboid boxes of various sizes. As his sled flies above a chimney, a stack of presents will be automatically dropped through it. Santa wants to carefully choose the presents so that all of them fit into a rectangular chimney.

All presents must be center-aligned due to magical physics issues (i.e. placing two small presents side-by-side is not allowed). The presents can be rotated, but four of the faces must be parallel to that of the chimney. A present fits in the chimney if both its width and length are <= those of chimney after rotation.

On second thought, Santa decides that choosing the maximum number of presents is not great, because a single large present is more valuable than a bunch of tiny ones.

Task

Given the dimensions of the presents and the chimney, determine the maximum volume of presents that fit in the chimney (i.e. sum of the presents' heights is <= that of the chimney). All dimensions are positive integers.

Standard rules apply. The shortest code in bytes wins.

Test cases

Presents and chimney are given as [width, length, height].

Presents: [[6, 6, 4], [2, 2, 2], [2, 2, 2], [2, 2, 2]]
Chimney: [6, 6, 6]
Answer: 152
Explanation: Use the large box and a small cube.

Presents: [[6, 10, 9], [10, 7, 6], [10, 7, 5], [10, 7, 4], [5, 10, 10]]
Chimney: [6, 5, 999]
Answer: 0
Explanation: No present fits in the chimney

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [2, 6, 6]
Answer: 72 (=6*(1*2*6))
Explanation: All six presents can be rotated to [2, 6, 1],
which fits the chimney and takes up only 1 unit of height

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [1, 6, 6]
Answer: 36
Explanation: All six presents can be rotated to [1, 6, 2]

Presents: [[1, 2, 6], [1, 6, 2], [2, 1, 6], [2, 6, 1], [6, 1, 2], [6, 2, 1]]
Chimney: [1, 3, 13]
Answer: 24
Explanation: All six presents can be rotated to [1, 2, 6]
\$\endgroup\$
3
  • \$\begingroup\$ This question more likely a combination of two problems: 1. rotate the present so it has smallest height while fit the chimney; 2. A classical knapsack problem. \$\endgroup\$
    – tsh
    Commented Dec 22, 2022 at 1:45
  • \$\begingroup\$ @tsh Yeah, right. This is what you get when you're pressed for challenges... \$\endgroup\$
    – Bubbler
    Commented Dec 22, 2022 at 2:05
  • 1
    \$\begingroup\$ @Arnauld fixed. \$\endgroup\$
    – Bubbler
    Commented Dec 22, 2022 at 10:35

5 Answers 5

3
\$\begingroup\$

Python 3, 180 bytes

lambda W,L,H,c:max(sum(h*w*l for h,w,l in a[::2])for a in P(c+[[0]*3]*len(c))if sum(min(h+H*(w>W or l>L)for h,w,l in P(b))for b in a[::2])<=H)
from itertools import*
P=permutations

Try it online!

It works on first two testcases. But It sadly timeout for third one.

\$O((2N+1)!)\$ solution, where \$N\$ is the number of presents.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js)*, 153 bytes

* This code relies on a specific implementation of sort(). The engine used on TIO is Node 11.6.0. This was also succesfully tested with Node 16.14.0.

Expects (w,l,h,a) where w,l,h are the dimensions of the chimney and a is the list of dimensions for the presents.

f=(w,l,h,a,V=o=0)=>a.map((b,i)=>f(w,l,h-(g=H=>m=n?([W,L,H]=b.sort(_=>-40%n--),W>w|L>l|H>g(v=W*L*H)?m:H):1/0)(n=42),a.filter(_=>i--),V+v),h<0|V<o?0:o=V)|o

Try it online!

Just like my answer to the previous challenge, this is sponsored by the Ministry of Silly Sorts.

\$\endgroup\$
1
\$\begingroup\$

Python3, 221 bytes:

lambda c,p:max(max(f(c,[*i]))for i in P(p,len(p)))
from itertools import*
P=permutations
def f(c,p,H=0,v=0):
 yield v
 if p:
  for w,l,h in P(p[0],3):
   if c[0]>=w>0<l<=c[1]and H+h<=c[2]:yield from f(c,p[1:],H+h,w*l*h+v)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 80 bytes

Fθ«≔E³E³§ι⁺κμζ≔Φ⁺ζEζ⮌κ⬤꬛μ§ηνζ¿ζ⊞υ⟦Πι⌊Eζ⊟κ⟧»I⌈EΦEX²LυΦυ﹪÷ιX²μ²¬›↨Eι⌊λ¹↨η⁰↨Eι⌈λ¹

Try it online! Link is to verbose version of code. Explanation: Based on my answer to CGAC2022 Day 21: Present stack headache.

Fθ«

Loop over the presents.

≔E³E³§ι⁺κμι

Rotate them 120° and 240° around a corner.

≔Φ⁺ιEι⮌κ⬤꬛μ§ηνι

Also rotate them 180° around their length axis, then filter on which orientations fit in the chimney.

¿ζ⊞υ⟦Πι⌊Eζ⊟κ⟧

If there were any then push the shortest such orientation to the predefined empty list along with the volume of the present.

»I⌈EΦEX²LυΦυ﹪÷ιX²μ²¬›↨Eι⌊λ¹↨η⁰↨Eι⌈λ¹

Generate the powerset of the list of presents that fit, filter on those whose height fits in the chimney, and output the maximum volume.

\$\endgroup\$
0
\$\begingroup\$

Pyth, 38 bytes

K_EeSmsm*FkdfghKshMTyhM_#SmSf.AtgVKT.p

Try it online!

Explanation

Picks the shortest orientation for each present, then looks at all possible sets of presents and picks the highest volume one which fits.

K_EeSmsm*FkdfghKshMTyhM_#SmSf.AtgVKT.pdQ    # implicitly add dQ to the end
                                            # implicitly assign Q = eval(input())
K_E                                         # assign K to the second input reversed
                          m            Q    # map Q over lambda d
                            f       .pd     # filter permutations of d over lambda T
                                gVKT        # vectorize >= over K and T
                             .At            # true if the last two element are true (we've now filtered out orientations which don't fit in the chimney)
                           S                # sort (this orders the orientations from shortest to tallest)
                         S                  # sort (this orders our presents shortest to tallest)
                       _#                   # filter out empty lists (avoids indexing errors)
                     hM                     # map each element to the first element of itself
            f       y                       # filter the power set over lambda T
             ghKshMT                        # first element of K >= sum of the first element(s) of T (leaving only sets of presents that fit)
     m                                      # map over lambda d
      s                                     # sum of
       m   d                                # map d over lambda k
        *Fk                                 # k reduced on multiplication (we've now mapped the sets to their volumes)
   eS                                       # take the largest element
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.