Sua vida pode depender disso. Não pisque. Nem pisque. Pisque e você está morto. Eles são rápidos. Mais rápido do que você pode acreditar. Não vire as costas, não desvie o olhar e não pisque! Boa sorte.
Anjos chorando são uma raça alienígena que não pode se mover enquanto é observada por outro ser (até outro anjo). Eles se alimentam enviando suas vítimas de volta no tempo. Você ( o médico ) está preso em uma sala com alguns e precisa chegar ao seu TARDIS.
Tarefa
Escreva um programa que, dada uma representação ASCII de uma sala retangular, produza um caminho que o levará à segurança. Se algum anjo puder atacar - a qualquer momento durante o seu progresso - esse caminho não será seguro. Um anjo pode atacar se conseguir vê-lo sem ser visto por você ou por outro anjo.
Entrada
Entrada é duas partes. Primeiro, a direção que você está seguindo (NSEW). Em seguida, nas linhas seguintes, uma representação da sala, mostrando os locais de início / fim e a localização / face de todos os Anjos.
A amostra abaixo mostra que existe um anjo voltado para o oeste e você começa para o sul.
S
..........
....D.....
..........
..........
..........
..........
..........
..........
.........W
..........
...T......
.
- Espaço vazioD
- O médico (posição inicial)T
- O TARDIS (posição final)N,S,E,W
- Um anjo, de frente para a direção especificada (norte, sul, leste, oeste)
Linha de visão
Você pode ver qualquer espaço a 45 graus da direção em que está voltado. A linha de visão é obstruída se houver outra entidade ao longo de uma diagonal direta horizontal, vertical ou 45 graus. Qualquer outra diagonal não obstrui a visualização. A linha de visão dos anjos funciona da mesma maneira. Por exemplo, a seguir, -
representa seu campo de visão, supondo que você esteja voltado para o sul.
........
...D....
..---...
.-----..
-------.
---N----
---.--N-
---.----
Resultado
A saída é uma sequência que representa o caminho que você seguirá para sair. Se houver vários caminhos seguros, escolha qualquer um. Se nenhum caminho estiver seguro, faça a saída 0
. Se o mapa estiver malformado, faça o que quiser, incluindo falhas. Considere-o malformado se a sala não for retangular, não houver saída etc. Se não houver Anjos, não será mal formado, simplesmente fácil.
Para cada etapa, você pode fazer uma de duas coisas: mover-se em uma direção NSEW ou girar para uma direção NSEW (sem alterar as posições). Para mover, basta imprimir a letra nessa direção. Para virar para enfrentar uma direção, faça a saída F
seguida pela letra apropriada. Por exemplo, a seguinte saída:
SSFESSSSSSSW
é um caminho seguro para a amostra fornecida na seção de entrada. Você se move para o sul duas vezes, enfrenta o leste para manter o anjo à vista, depois se move para o sul mais sete vezes e para o oeste uma vez para entrar na TARDIS.
Casos de teste
1) Você pode dar a volta no anjo voltado para o leste para chegar ao TARDIS. A menos que você pise diretamente entre eles, eles travam um ao outro no lugar, então não importa para que lado você esteja diante.
W
...D....
........
........
........
.E.....W
........
........
...T....
2) Você perde. Não há como passar por eles. Eles podem se ver até você se colocar entre eles. Nesse ponto, você não pode enfrentar os dois e pronto. É melhor fechar os olhos e acabar logo com isso.
S
...D....
........
........
........
E......W
........
........
...T....
Ganhando
Aplicam-se regras e brechas de golfe padrão , menos bytes ganhos. Em breve, tentarei obter mais casos de teste, mas fique à vontade para sugerir o seu.
Imagem e citações do Doctor Who.
J
).Respostas:
Python -
559 565 644633A entrada deve ser fornecida assim:
Essencialmente, é essa abordagem aplicada para encontrar todos os estados (posição e direção) que o médico pode alcançar com segurança, armazenando como chegou lá e imprimindo o caminho em caso de sucesso. Posições e direções são realizadas com números complexos.
Provavelmente eu poderia guardar alguns caracteres usando a aritmética complexa de números de Sage, mas isso seria extremamente longo.
Primeiro, pensei que poderia salvar seis caracteres, fazendo com que o médico se transformasse em uma direção específica depois de chegar ao Tardis, mas percebi que isso poderia resultar em soluções erradas. Também primeiro li mal as regras.
Aqui está uma versão praticamente não destruída:
Casos de teste
Caso de teste 1:
Caso de teste 2:
Caso de teste do VisualMelon:
fonte
C #
17712034196218871347 bytesReescreveu a verificação de bloqueio do LOS em um loop, tornando-o muito mais organizado e cerca de 450 bytes mais curto
Este é um programa completo que espera que a entrada termine com um EOF e seja passada para STDIN. (Espero) imprime o caminho mais curto para o TARDIS, ou "0" se não houver caminho. Ele usa uma pesquisa de largura de primeira qualidade para seguir todas as rotas possíveis, depois recua do TARDIS ao The Doctor para montar a saída.
Código formatado:
Saída, por exemplo, entrada
Saída para o caso de teste 1)
Saída para o caso de teste 2)
Apresento, conforme solicitado, um novo caso de teste:
Meu programa gera
Caso de teste 1 do WozzeC:
Caso de teste 2 do WozzeC:
fonte
C #
1454, 1396, 1373, 13031279Direito. Então eu decidi tentar e rapaz demorou um pouco. Ele é construído principalmente usando operadores lógicos.
Para evitar ter que procurar Nulo etc., decidi usar um campo de [MAX_SIZE * 3] * [MAX_SIZE] * 3 e colocar o tabuleiro de jogo próximo ao centro.
As verificações de loop são feitas por dentro e por fora até 50 (MAX_SIZE). Então, algo como isto:
Quando um EWS ou N é encontrado, faço a mesma verificação por parte deles. Se alguma coisa é encontrada olhando para os anjos (não o médico), eles retornam 15 como passagem livre. Se não forem observados, retornam de que maneira o médico deve enfrentar para estar seguro. isto é, N retornaria 2 para o sul. A menos que seja NW ou NE, nesse caso, retornaria 6 (2 + 4) e 10 (2 + 8), respectivamente.
Se dois anjos estiverem observando o médico, os valores retornados serão "ANDed", portanto, no exemplo de teste 2, as posições 4 e 8 se transformarão em 0. Isso significa que a posição é ruim e deve ser evitada.
Código expandido:
Resultado dos testes
1 Exemplo: FNSSSWNNNWSSSWSSSSENNESES
2 Exemplo: Sem saída
Exemplo de VisualMelon: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE
Meu caso de teste1: FSSENEEEFWSSFNSWWN
Meu caso de teste2: FSEEEESFWSSSSFNWWWWNFENNFSEES
Como pode ser visto, meu médico adora andar como um idiota para mostrar aos anjos como é divertido se movimentar. Posso fazer com que o software encontre o caminho mais curto, mas leva mais tempo e precisa de mais código.
Casos de teste para vocês
Outro:
fonte
using S=System.Console;
, ou você pode simplesmente remover completamente o S no seu código e economizar 6 bytes porusing System
. Agora eu vou ter que tentar e cortar minha abordagem ingênua para baixo um pouco mais ...;)