Problem pakowania sań

Elfy Świętego Mikołaja potrzebują pomocy w ustaleniu, czy ich obecna partia prezentów zmieści się w saniach Świętego Mikołaja. Napisz najkrótszy możliwy program w wybranym języku, aby im pomóc.

Ograniczenia

• Sanie Świętego Mikołaja mają 6 stóp szerokości i 12 stóp długości i 4 stopy głębokości.
• Prezenty mogą być delikatne, więc nie można ich ustawiać jeden na drugim.
• Możesz obracać i przerzucać prezenty, jak chcesz, ale Święty Mikołaj jest dość obsesyjno-kompulsywnym facetem, więc utrzymuj obroty do wielokrotności 90 stopni.
• Przepisy dotyczące zdrowia i bezpieczeństwa na Biegunie Północnym stanowią, że prezenty nie mogą wystawać więcej niż 1 metr nad sanie (dlatego nie mogą być wyższe niż 5 stóp).

Wejście

Wejście będzie włączone STDINi będzie jedną liczbą całkowitą reprezentującą liczbę prezentów w partii, a następnie listę wymiarów prezentów - 1 prezent na linię, 3 wymiary (w stopach) oddzielone spacjami.

Przykłady:

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

Wynik

Wyjście powinno być tylko słowem „TAK”, jeśli prezenty można zapakować w sanie, lub „NIE”, jeśli nie mogą.

Dane wyjściowe dla powyższych przykładów:

YES

YES

NO

NO

Skrypty testowe

Tak jak poprzednio, przywłaszczyłem niektóre skrypty testowe napisane przez Joeya i Ventero, aby utworzyć testy dla tego zadania:

• Grzmotnąć
• PowerShell

Stosowanie: ./test [your program and its arguments]

Nagrody

Każdy wpis, który mogę zweryfikować, który spełnia specyfikację, przechodzi testy i oczywiście miał pewne próby gry w golfa, otrzyma ode mnie opinię (więc proszę o podanie instrukcji użytkowania wraz z odpowiedzią). Najkrótsze rozwiązanie do końca 2011 roku zostanie uznane za zwycięzcę.

Haskell, 312 318 znaków

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"

Z jakiegoś powodu, którego w tej chwili nie rozumiem, nie kończy on testów # 9 i # 16 w rozsądnym czasie. Ale nie mówiłeś nic o wydajności, prawda?

373 383 znaków

Ta wersja działa znacznie szybciej w przykładach: najpierw sprawdza, czy nie jest to niemożliwe tylko dlatego, że obszar jest zbyt mały, a następnie zaczyna się od największych paczek, a nie wstawia je w podanej kolejności. Pamiętaj, że wykrywanie obszaru nie jest idealne: nie uwzględnia rotacji, więc może na niektórych wejściach dawać błędne wyniki. Ale działa ze skryptem testowym.

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"

Python, 461 znaków

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'

Lrekurencyjnie sprawdza, czy prostokąty Pmożna umieścić na saniach, gdzie zznajduje się maska ​​bitów komórek, które są już zajęte. SPrzyporządkowanie określa, w jaki sposób jest w górę dla każdego z pakietów (największy wymiar <5 przechodzi pionowo).

Kod jest potencjalnie wykładniczy, ale jest szybki na wszystkich wejściach testowych.

GolfScript, 130 znaków

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

Uruchomienie go w GolfScript zajęło sporo czasu. Każda próba gry w golfa zepsuła niektóre przypadki testowe.

Ostrzegamy, że ta wersja może stać się bardzo wolna, jeśli uruchomisz ją ze zbyt dużą liczbą prezentów.