O problema da embalagem do trenó

11

Os elfos do Papai Noel precisam de ajuda para determinar se o lote atual de presentes vai caber no trenó do Papai Noel. Escreva o programa mais curto possível no idioma de sua escolha para ajudá-los.

Restrições

  • O trenó do Papai Noel mede 6 pés de largura por 12 pés de comprimento e tem 4 pés de profundidade.
  • Os presentes podem ser frágeis e, portanto, não podem ser empilhados uns sobre os outros.
  • Você pode girar e virar os presentes como quiser, mas o Papai Noel é um sujeito obsessivo-compulsivo, então mantenha as rotações em múltiplos de 90 graus.
  • Os regulamentos de saúde e segurança do Pólo Norte estipulam que os presentes não podem ficar acima de um metro acima do topo de um trenó (portanto, eles não podem ter mais de um metro e meio de altura).

Entrada

A entrada estará ativada STDINe será um número inteiro representando o número de presentes no lote seguido por uma lista das dimensões dos presentes - 1 presente por linha, 3 dimensões (em pés) separadas por espaços.

Exemplos:

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

Resultado

A saída deve ser apenas a palavra 'SIM' se os presentes puderem ser embalados no trenó ou 'NÃO' se não puderem.

Saída para os exemplos acima:

YES

YES

NO

NO

Scripts de teste

Como antes, eu me apropriei de alguns scripts de teste escritos por Joey e Ventero para criar alguns testes para esta tarefa: -

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

Recompensas

Cada entrada que eu possa verificar que atenda às especificações, passa nos testes e obviamente teve alguma tentativa de jogar golfe receberá um voto positivo de mim (por isso, forneça instruções de uso com sua resposta). A solução mais curta até o final de 2011 será aceita como vencedora.

Gareth
fonte
Estamos autorizados a rodar os presentes? Virá-los de lado? Gire-os em um ângulo que não seja múltiplo de 90 °?
Ilmari Karonen
@IlmariKaronen Sim, você pode girar os presentes para qualquer orientação que desejar, desde que eles se encaixem. Eu acho que a matemática envolvida na montagem de caixas em um ângulo que não é múltiplo de 90 seria muito complicada, não é? Eu assumi apenas rotações de 90 graus para os testes.
Gareth
@IlmariKaronen Pensando melhor, acho que preciso eliminar rotações outros múltiplos de 90 graus para evitar complicar demais a pergunta e garantir que os testes dêem respostas corretas. Vou adicionar uma restrição extra.
Gareth
Por que o exemplo 3 é não quando o exemplo 1 é sim? 6x12x5 é maior que 6x12x4; portanto, o presente pode sair do topo? Nesse caso, por que o 3 um não, também pode ser destacado?
Skizz
1
@ Skizz: É redigido de maneira confusa, mas veja a quarta restrição: os presentes podem ficar a um metro do topo. Portanto, a profundidade efetiva do trenó é de 5 pés, não 4 pés.
Ilmari Karonen

Respostas:

3

Haskell, 312 318 caracteres

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"

Por alguma razão que eu não entendo completamente no momento, ele não termina seus testes # 9 e # 16 em tempo razoável. Mas você não disse nada sobre desempenho, disse?


373 383 caracteres

Esta versão é muito mais rápida para os exemplos: primeiro verifica se não é impossível simplesmente porque a área é muito pequena e, em seguida, começa com as maiores parcelas, em vez de inseri-las na ordem especificada. Observe que a detecção de área não é perfeita: ela não considera rotações, portanto, em algumas entradas, pode dar resultados incorretos. Mas funciona com o script de teste.

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"
deixou de girar contra-relógio
fonte
Não, eu não estava preocupado com o desempenho, mas o programa precisa passar em todos os testes para obter meu voto positivo. Atualmente, ele está trabalhando no teste 9. Vou deixar um pouco para ver se ele termina.
Gareth
@Gareth terei que otimizá-lo ainda um pouco.
deixou de girar no sentido anti-horáriowis
Está bem. Ainda está trabalhando no teste 9 aqui.
Gareth
2

Python, 461 caracteres

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'

Lverifica recursivamente se os retângulos Ppodem ser colocados no trenó, onde zhá uma máscara de bits de células que já estão ocupadas. A Satribuição determina qual o caminho a seguir para cada um dos pacotes (a maior dimensão <= 5 ocorre verticalmente).

O código é potencialmente exponencial, mas é rápido em todas as entradas de teste.

Keith Randall
fonte
1

GolfScript, 130 caracteres

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

Demorou algum tempo para rodar no GolfScript. Qualquer tentativa de golfe quebrou ainda mais alguns dos casos de teste.

Esteja avisado de que esta versão pode ficar incrivelmente lenta se você a executar com muitos presentes.

Howard
fonte
Eu sempre tenho problemas com os de golfe. Estou tentando, ./test ruby golfscript.rb howard.gsmas está me dando erros. Como devo invocá-lo?
Gareth
@Gareth Você pode apenas acrescentar ponto e vírgula seguido da entrada (por exemplo ;"1\n6 12 5") no script fornecido.
28511 Howard
Uau, você não estava brincando sobre isso ser lento em alguns casos. Eu posso ter que deixá-lo durante toda a noite sobre os dois casos de teste últimos (72 e 73 apresenta respectivamente ;-)
Gareth
Desculpe, ele não passou no teste 5 no script de teste. Não posso votar até que passe em todos os testes.
Gareth
@ Gareth Bem, então este não receberá um voto positivo do seu lado ;-) Implementa a abordagem exponencial completa para ser breve. Estou trabalhando em um algoritmo mais rápido, mas ainda não está pronto para o envio. Ele precisa de consideravelmente mais espaço e ainda tenho alguns casos restantes para implementação.
Howard