# The Sleigh Packing problem

Santa's elves need help in determining if their current batch of presents will fit into santa's sleigh. Write the shortest program possible in the language of your choice to help them out.

## Constraints

• Santa's sleigh measures 6ft wide by 12ft long and is 4ft deep.
• Presents may be fragile, so they may not be stacked on top of each other.
• You can rotate and flip the presents as you wish, but Santa's quite an obsessive-compulsive chap so keep the rotations to multiples of 90 degrees.
• North Pole health and safety regulations stipulate that presents may not stick out more than 1ft above the top of a sleigh (therefore they may not be more than 5ft high).

## Input

Input will be on `STDIN` and will be one integer representing the number of presents in the batch followed by a list of the presents' dimensions - 1 present per line, 3 dimensions (in feet) separated by spaces.

Examples:

``````1
6 12 5

6
1 12 3
1 12 4
1 12 1
1 12 5
1 12 3
1 12 5

1
4 3 13

1
6 12 6
``````

## Output

Output should just be the word 'YES' if the presents can be packed into the sleigh or 'NO' if they cannot.

Output for the above examples:

``````YES

YES

NO

NO
``````

## Test scripts

As before, I've appropriated some test scripts written by Joey and Ventero to create some tests for this task:-

Usage: `./test [your program and its arguments]`

## Rewards

Each entry which I can verify that meets the spec, passes the tests and has obviously had some attempt at golfing will receive an upvote from me (so please provide usage instructions with your answer). The shortest solution by the end of the 2011 will be accepted as the winner.

-
Are we allowed to rotate the presents? Flip them on their side? Rotate them by an angle that's not a multiple of 90°? –  Ilmari Karonen Dec 24 '11 at 4:44
@IlmariKaronen Yes, you can rotate the presents to any orientation you wish as long as they fit. I think the the maths involved in fitting boxes in at an angle that's not a multiple of 90 would be over-complicated wouldn't it? I've assumed only rotations of 90 degrees for the tests. –  Gareth Dec 24 '11 at 8:17
@IlmariKaronen Upon further thought, I think I need to eliminate rotations other multiples of 90 degrees to avoid over-complicating the question, and to ensure that the tests give correct answers. I'll add an extra constraint. –  Gareth Dec 24 '11 at 10:16
Why is example 3 a no when example 1 is a yes? 6x12x5 is bigger than 6x12x4 so are present allowed to poke out the top? In which case why is 3 a no as that too can stick out the top? –  Skizz Dec 24 '11 at 11:41
@Skizz: It's confusingly phrased, but see the fourth constraint: presents may stick 1ft out the top. So the effective depth of the sleigh is 5ft, not 4ft. –  Ilmari Karonen Dec 24 '11 at 12:11

``````import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
main=do
putStr.r\$foldr((=<<).y)[[([9,0],[0..])]]p
r[]="NO"
r _="YES"
``````

For some reason that I don't fully understand at the moment, it doesn't finish your tests #9 and #16 in reasonable time. But you didn't say anything about performance, did you?

## 373 383 chars

This version runs much faster for the examples: it first checks if it's not impossible simply because the area is too small, and then it starts with the largest parcels rather then inserting them in the given order. Note that the area detection is not perfect: it doesn't consider rotations, so it may on some inputs give wrong results. But it does work with the test script.

``````import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
π=product
main=do
putStr\$if sum(map(π.init)p)>72||null(foldr((=<<).y)[[([9,0],[0..])]].sortBy((.π).compare.π)\$p)then"NO"else"YES"
``````
-
No, I wasn't concerned with performance, but the program does have to pass all the tests to get my upvote. It's currently working on test 9. I'll leave it awhile to see if it finishes. –  Gareth Dec 28 '11 at 9:44
@Gareth I shall have to optimize it yet a bit. –  leftaroundabout Dec 28 '11 at 10:54
Ok. It's still working on test 9 here. –  Gareth Dec 28 '11 at 11:02

## Python, 461 chars

``````import sys
def L(P,z):
if not P:return 1
for w,h in[P[0],P[0][::-1]]:
m=sum((2**w-1)<<i*6for i in range(h))
for x in range(7-w):
for y in range(13-h):
n=m<<y*6+x
if z&n==0and L(P[1:],z|n):return 1
return 0
S=[(x,y)if z<6 else(x,z)if y<6 else(y,z)if x<6 else(9,9)for x,y,z in[sorted(eval(g.replace(' ',',')))for g in G.split('\n')[1:]if g]]
print'YES\n'if sum(x*y for x,y in S)<73and L(S,0)else'NO\n'
``````

`L` recursively checks if the rectangles in `P` can be put in the sleigh, where `z` is a bitmask of cells that are already occupied. The `S` assignment determines which way is up for each of the packages (largest dimension <= 5 goes vertically).

The code is potentially exponential, but it is quick on all the test inputs.

-

## GolfScript, 130 characters

``````"NO":g;~](;3/127{128*64+}12*\{.,0>.!{"YES":g;}*{([{[~@]..[~\]\}3*;]{)6<{~[2\?(]*128base 83,{2\?1\$*.4\$&0={3\$|2\$f}*}%;}*}%;}*;;}:f~g
``````

It took quite some time to get it running in GolfScript. Any attempt to golf it further broke some of the test cases.

Please be warned that this version may become incredibly slow if you run it with too many presents.

-
I always have trouble with golfscript ones. I'm trying `./test ruby golfscript.rb howard.gs` but it's giving me errors. How should I be invoking it? –  Gareth Dec 28 '11 at 14:45
@Gareth You might just prepend semicolon followed by the input (e.g. `;"1\n6 12 5"`) to the given script. –  Howard Dec 28 '11 at 15:03
Wow, you weren't kidding about it being slow on some cases. I may have to leave it all night on the two last test cases (72 and 73 presents respectively ;-) –  Gareth Dec 28 '11 at 16:10
Sorry, it won't go past test 5 in the test script. I can't upvote until it passes all the tests. –  Gareth Dec 29 '11 at 13:47
@Gareth Well, then this one won't get an upvote from your side ;-) It implements the full exponential approach in order to be short. I am working on a faster algorithm but it is not yet ready for submission. It needs considerably more space already and I still have some cases left for implementation. –  Howard Dec 29 '11 at 13:58