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 STDIN
e 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.
Respostas:
Haskell, 312
318caracteresPor 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
383caracteresEsta 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.
fonte
Python, 461 caracteres
L
verifica recursivamente se os retângulosP
podem ser colocados no trenó, ondez
há uma máscara de bits de células que já estão ocupadas. AS
atribuiçã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.
fonte
GolfScript, 130 caracteres
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.
fonte
./test ruby golfscript.rb howard.gs
mas está me dando erros. Como devo invocá-lo?;"1\n6 12 5"
) no script fornecido.