CGAC2022 Day 21: Present stack headache

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

challenge idea by emanresu A

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.

Given the dimensions of the presents and the chimney, determine the maximum number 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]
Explanation: Use three small cubes.
(Placing two or more cubes above or below the single large box is not allowed)

Presents: [[6, 10, 9], [10, 7, 6], [10, 7, 5], [10, 7, 4], [5, 10, 10]]
Chimney: [6, 5, 999]
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]
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]
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]
Explanation: All six presents can be rotated to [1, 2, 6]

• All presents must be center-aligned due to magical physics issues mean all thing differ pos on one direction, or the direction is given?
– l4m2
Dec 21, 2022 at 10:27
• In all your test cases the height of the chimney is >= every dimension in the list of presents. May we assume that to be true in all cases? Dec 21, 2022 at 11:19
• Can we throw an error instead of outputting 0 if no presents fit? Dec 21, 2022 at 11:40
• Suggested test case: [[6, 10, 9], [10, 7, 6], [10, 7, 5], [10, 7, 4], [5, 10, 10], [1, 6, 7]], [6, 7, 21] -> 3 Dec 21, 2022 at 18:39
• Sorry for late response. @ l4m2: The intention is that all the presents are stacked vertically and no other direction. @ Shaggy: No, the chimney height can be smaller than any present's dimensions, and 0 is the correct answer in that case. Throwing instead of outputting 0 is not allowed. Dec 22, 2022 at 1:22

Python 3, 130 bytes

lambda W,L,H,a:sum(0<=(H:=H-i)for i in sorted(min(h+H*(w>W or l>L)for h,w,l in permutations(b))for b in a));from itertools import*


Try it online!

Python3, 217 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,k=0):
yield k
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,k+1)


Try it online!

• 225 bytes Dec 21, 2022 at 0:50
• @jezza_99 Thanks, updated Dec 21, 2022 at 0:53
• Haha and can save another byte using c[0]>=w>0<l<=c[1] instead of w<=c[0]and l<=c[1] Dec 21, 2022 at 0:54

Charcoal, 72 bytes

Ｆθ«≔Ｅ³Ｅ³§ι⁺κμι≔Φ⁺ιＥι⮌κ⬤κ¬›μ§ηνι¿ι⊞υ⌊Ｅι⊟κ»≔⟦⟧ζＷ⁻υζＦ№υ⌊ι⊞ζ⌊ιＩＬΦζ¬›Σ…ζ⊕κ↨η⁰


Try it online! Link is to verbose version of code. Explanation:

Ｆθ«


Loop over the presents.

≔Ｅ³Ｅ³§ι⁺κμι


Rotate them 120° and 240° around a corner.

≔Φ⁺ιＥι⮌κ⬤κ¬›μ§ηνι


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

¿ι⊞υ⌊Ｅι⊟κ


If there were any then push the shortest such orientation to the predefined empty list.

»≔⟦⟧ζＷ⁻υζＦ№υ⌊ι⊞ζ⌊ι


Sort the list of heights.

ＩＬΦζ¬›Σ…ζ⊕κ↨η⁰


Find the maximum number of presents that will fit.

05AB1E, 21 bytes

εœʒ@¨P}€θß}²Oª{ηÅΔO‹θ


Try it online!

+2 bytes: fixed a bug found by Jonathan Allan

Assumes that all chimney dimensions are positive.

εœʒ@¨P}€θß}
ε         } # map over boxes
œ          #   permutations (all possible rotations)
ʒ   }     #   filter:
@¨P      #     first two dimensions are less than or equal to the
first two dimensions of the chimney
€θ   #   for each get last element (the height)
ß  #   minimum


This gets a list of the smallest height you can get by rotating the box in a way that fits the chimney or "" if it doesn't fit at all.

²Oª{ηÅΔO‹θ
²Oª        # append sum of the second input to the list
{       # sort
η      # prefixes
ÅΔ    # get the index of the first element such that:
O‹θ #   the sum is greater than the last element of second input


The sum of the second input is there to guarantee that there is a prefix with larger sum than the height of the chimney.

• [[6, 10, 9], [10, 7, 6], [10, 7, 5], [10, 7, 4], [5, 10, 10], [1, 6, 7]] and [6, 7, 21] returns 6, but it should be 3. Dec 21, 2022 at 18:40

JavaScript (Node.js)*, 128 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.

-4 thanks to @tsh

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.

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


Try it online!

How?

The way we generate the 6 possible rotations of a present is very hackish but pretty short. It basically goes like that:

for(let n = 42; n;) {
a.sort(_ => -40 % n--);
}


The callback function of sort() ignores its arguments, making the sort independent of the content of the array. The result is solely based on the current value of $$\n\$$, which is decremented after each iteration. More specifically, we get either $$\0\$$ if $$\n\in\{1,2,4,5,8,10,20,40\}\$$ or a negative integer otherwise.

The constants $$\-40\$$ and $$\42\$$ were chosen such that all distinct rotations are eventually generated and we end up with exactly $$\n=0\$$ when the last one has been processed.

You can follow this link to see the different steps of the process.

• Maybe you should specify the version of interpreter instead of claim it as "JavaScript". As behavior of a.sort(_=>3%k++-2) is certainly defined by interpreter.
– tsh
Dec 21, 2022 at 3:43
• 134: (w,l,h,a)=>a.map(a=>(g=H=>m=n?([W,L,H]=a,a=--n%2?[W,H,L]:[H,L,W],W>w|L>l|H>g()?m:H):1/0)(n=6)).sort((a,b)=>a-b).map(v=>n+=(h-=v)>=0)|n
– tsh
Dec 21, 2022 at 5:27
• @tsh Thank you for the suggestions. I've added two examples of engines for which this works as expected. Dec 21, 2022 at 14:08

Japt-h, 28 bytes

Ëá fÈÅí§NÅ eÃmÎÍÎÃÍËT±Z§(XµD


Try it

Ëá fÈÅí§NÅ eÃmÎÍÎÃÍËT±Z§(XµD     :Implicit input of array U=presents and integers V=width, W=depth & X=height
Ë                                :Map U
á                               :  Permutations
f                             :  Filter by
È                            :  Passing each through a function
Å                           :    Slice off first element
í                          :    Interleave with
N                        :      Array of all inputs
Å                       :      Slice off first element (X is ignored)
§                         :      Reducing each pair by <=
e                     :    All true?
Ã                    :  End filter
m                   :  Map
Î                  :    First element (present height)
Í                 :  Sort
Î                :  First element
Ã               :End map
Í              :Sort
Ë             :Map each D
T±           :  Increment T (initially 0) by
Z          :    0
§(        :    <=
XµD     :    X, decremented by D
:Implicit output of last element


Pyth, 29 bytes

K_EsmghK=+Zhhd_#SmSf.AtgVKT.p


Try it online!

Explanation

Uses a simple greedy algorithm, always choosing the shortest present until no more fit.

K_EsmghK=+Zhhd_#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)
s                               # sum of
m                              # map over lambda d
ghK                           # first element of K is greater than or equal to
=+Zhhd                     # Z, assigned to Z + first element of the first element of d