Pesquisadores descobriram recentemente uma colônia de abelhas interessante que vive em um campo infinito de favo de mel:
Cada célula pode abrigar uma abelha ou não. De fato, a vida dessas criaturas parece um pouco ... caótica. Pode-se calcular que uma colônia sempre começa com o seguinte padrão:
(Abelha desenhada por Emmanuel Boutet no Wikimedia Commons . Esta imagem de favo de mel e abelhas é divulgada sob CC-By-SA . Resmunga )
Depois disso, os ciclos de vida das abelhas são divididos nas chamadas gerações. Cada geração de abelhas velhas morre e as novas eclodem e depende principalmente dos vizinhos de suas células:
- Se uma abelha tem menos de dois vizinhos, morre devido à solidão.
- Se uma abelha tem mais de três vizinhos, morre devido à superlotação.
- Se uma célula possui duas, três ou quatro abelhas vivas nas células vizinhas, uma nova abelha eclode na próxima geração.
As abelhas moribundas não morrem até o final de uma geração, portanto ainda afetam as células circundantes que podem chocar as abelhas na próxima geração.
Agora que sabemos como essa colônia funciona, podemos simulá-la por várias gerações.
Entrada
A entrada é um número único N , fornecido na entrada padrão, terminado por uma quebra de linha. 0 ≤ N ≤ 150. Este é o número de gerações para simular.
Resultado
A saída é um número único, na saída padrão e, opcionalmente, seguida por uma única quebra de linha, que representa o número de abelhas vivas após N gerações.
Saída adicional com erro padrão é ignorada.
Entradas de Amostra
0
5
42
100
Saídas de amostra
6
44
1029
5296
Condição vencedora
O código mais curto vence, como é habitual no golfe. Em caso de empate, a solução anterior vence.
Casos de teste
Existem dois scripts de teste, contendo casos de teste idênticos:
A invocação ocorre nos dois casos:, <test script> <my program> [arguments]
por exemplo, ./test ruby beehive.rb
ou ./test.ps1 ./beehive.exe
.
Eu sei que existem apenas 22 testes em vez de 151 (principalmente porque as soluções costumam ser bastante lentas). Evite incorporar os casos de teste exatos em vez de resolver a tarefa. Esses scripts são uma conveniência para você testar se uma alteração ainda faz com que o programa se comporte corretamente; não que você possa adaptar seu código aos casos de teste específicos.
Outra nota
Esta tarefa fez parte de um concurso de golfe realizado na minha universidade durante o período 2011-W24. As pontuações e idiomas de nossos concorrentes foram os seguintes:
- 336 - C
- 363 - C
- 387 - C
- 389 - Haskell
- 455 - C
Nossa própria solução foi
- 230 - Ruby
Respostas:
Rubi,
181163153146 caracteresEssa implementação segue uma abordagem padrão usando uma matriz
h
(dimensões200
x200
achatadas), em que cada elemento é0
(sem abelha) ou1
(abelha incluída). A matriz[0,-200,201,202,2,3]
descreve as posições iniciais das abelhas (em relação a qualquer célula inicial).A entrada e saída, conforme especificado acima, passa em todos os casos de teste definidos.
Editar 1: alterado novamente para uma solução de agrupamento em vez da versão "espaço adicional" (que era mais curta em uma versão intermediária, mas agora tem vários caracteres mais).
Edição 2: variável removida
b
completamente.Editar 3: aviso: esta edição tornou o programa terrivelmente lento. Assim, reduzi as dimensões para 200 cada uma, o que ainda é suficiente para até 150 iterações. Em vez de indexar a matriz por uma variável, constantemente giramos a matriz para frente. Design não muito bom, mas agora estamos consideravelmente abaixo dos 150.
fonte
Python, 152 caracteres
Esta solução controla os locais das abelhas com um conjunto de números complexos. É bem lento porque o loop interno é quadrático no número de abelhas. Eu testei até 50 e funciona.
fonte
P={0,2,3,1j,1+1j,1-1j}
e depois usar{p}<P
para testar a associação (poupa 1 caractere)Python,
171169158 caracteresEu modelo o mundo como uma matriz 300 * 300 = 900000 1D (
h
na verdade é maior, mas o final não é usado), onde uma abelha é 1 e vazia é 0. O tamanho de 300 é bom porque, no máximo, o crescimento seria de 2 em cada dimensão para cada geração, e não há mais de 150 gerações.Aqui está uma versão ligeiramente não-gasta e comentada:
fonte