The Sleigh Packing problem

Question

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:-

• Bash
• PowerShell

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.

Answer 1

Haskell, 312 318 chars

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
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 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
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr$if sum(map(π.init)p)>72||null(foldr((=<<).y)[[([9,0],[0..])]].sortBy((.π).compare.π)$p)then"NO"else"YES"

Answer 2

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
for G in sys.stdin.read().split('\n\n'):
 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.

Answer 3

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.