Sinopse : Jimmy está desaparecido; nós temos que encontrá-lo. Nós devemos nos separar.
Trama : Jimmy já está morto.
Mas, nosso elenco não sabe disso, então eles precisam pesquisar toda a área de qualquer maneira. Há uma grade de N colunas x M linhas (1 <= M, N <= 256) de células, marcadas como "S" para o ponto de partida "." para espaço aberto ou "#" para um obstáculo. Este é o mapa .
Existem 0 <= p <= 26 costars , 0 <= q <= 26 extras e 1 estrela . Todo mundo está inicialmente na célula marcada com S.
As regras
Cada pessoa tem um raio de visão mostrado abaixo:
...
.....
..@..
.....
...
A estrela é denotada por "@", os costars por letras maiúsculas, começando com "A", e os extras por letras minúsculas, começando por "a". Inicialmente, o raio da mira em torno do ponto inicial já está marcado como pesquisado. Se isso constitui todo o espaço aberto do mapa, o jogo termina. Cada turno, na seguinte ordem :
- Cada pessoa faz simultaneamente um rei se mover (parado ou movendo-se para uma das oito células vizinhas).
- Todas as células no raio de visão ao redor de cada pessoa são contadas como pesquisadas.
- Se um co-ator não pode ver mais ninguém, ela morre. Se um extra não pode ver um co-estrela, a estrela ou pelo menos dois outros extras, ele morre. Isso acontece simultaneamente - ou seja, não pode haver reação em cadeia das mortes em um único turno; as condições acima são verificadas e todo mundo que morre morre imediatamente.
- Se todo o espaço aberto no mapa tiver sido pesquisado, a pesquisa terminou.
Notas
Várias pessoas podem estar na mesma praça a qualquer momento, e elas podem se ver.
Os obstáculos nunca impedem a visão, apenas o movimento; as pessoas podem se ver através da lava?
Os espaços abertos no mapa são garantidos para serem conectados por movimentos de rei.
O "S" inicial também é considerado espaço aberto, e não um obstáculo.
Qualquer movimento do rei que cair em um espaço aberto é válido. Por exemplo, a seguinte jogada é legal:
.... ....
.@#. ---> ..#.
.#.. .#@.
.... ....
Entrada
A entrada estará no formato
N M p q
[N cols x M rows grid with characters ".", "#", and "S"]
Entradas de amostra:
6 5 0 0
......
......
..S...
......
......
e
9 9 1 1
S.......#
.......##
......##.
..#####..
...##....
...##....
...#.....
....#..#.
.........
p e q são os números de co-figurantes e extras, respectivamente.
Saída
A saída deve ser, para cada turno, os movimentos realizados, com as direções indicadas por
789
456
123
A ordem dos movimentos não importa, pois todos são encenados simultaneamente. Não listar uma jogada para uma pessoa é bom e é equivalente a movê-la na direção 5. As jogadas devem ser listadas no seguinte formato:
@9 A2 a2 B7.
"." indica o final de seus movimentos por um turno.
Depois que o mapa for pesquisado, a linha final de saída deverá ser três números inteiros, separados por espaços: o número de voltas que você levou para terminar de pesquisar no quadro, o número de personagens vivos e o número de extras vivos. Para o primeiro exemplo de entrada
6 5 0 0
......
......
..S...
......
......
o seguinte é saída válida:
@4.
@6.
@6.
@6.
4 0 0
Uma observação final: a estrela não pode morrer e é garantido que o espaço aberto no mapa esteja conectado, portanto a pesquisa sempre será bem-sucedida eventualmente.
Pontuação
Sua pontuação é o número total de turnos realizados em um conjunto de testes de benchmark; você pode enviar seu próprio caso de teste junto com sua resposta. A soma do número de coadjuvantes vivos sobre o conjunto de benchmarks será usada como desempate e, no caso de ainda haver empate, será usada a soma do número de extras vivos.
Conjunto de teste e controlador
Atualmente, 5 mapas estão online em https://github.com/Tudwell/HorrorMovieSearchParty/ . Qualquer pessoa que envie uma resposta também poderá enviar um caso de teste, que me reservo o direito de rejeitar por qualquer motivo (se eu rejeitar seu mapa por algum motivo, você poderá enviar outro). Estes serão adicionados ao conjunto de testes a meu critério.
Um controlador Python (testado no 2.7.5) é fornecido no github como controller.py . Um segundo controlador lá, controller_disp.py , é idêntico, exceto que mostra a saída gráfica durante a pesquisa (requer a biblioteca Pygame).
Uso :
python controller.py <map file> <your execution line>
Ou seja:
python controller.py map1.txt python solver.py map1.txt
O controlador produz uma saída (para o stdin do seu programa ) no formato
Turn 1
@:2,3 A:2,3 B:2,3.
##...##
#ooo..#
ooooo..
ooooo..
ooooo..
#ooo...
##.....
###....
----------------------------------------
Este é o número do turno (o turno 1 é antes de você se mudar), uma lista terminada em '.' De todos os atores e suas coordenadas x, y (o caractere superior esquerdo é (0,0)), uma representação de todo board e uma linha com 40 '-'s. Em seguida, aguarda a entrada (do stdout do seu programa ) do formulário
@9 A2 B7.
Este é o formato de saída especificado acima. O controlador gera um 'o' para o espaço aberto que foi pesquisado, '.' para espaço aberto que não foi pesquisado e '#' para obstáculos. Inclui apenas pessoas vivas em sua lista de pessoas e suas coordenadas e rastreia todas as regras do jogo. O controlador irá sair se uma tentativa ilegal for tentada. Se os movimentos para um determinado turno concluírem a pesquisa, a saída não será a mesma; em vez disso, é da forma
Finished in 4 turns
4 1 0
"4 1 0" aqui indica 4 turnos totais, 1 costar vivo e 0 extras vivos. Você não precisa usar o controlador; fique à vontade para usá-lo ou modificá-lo para sua própria entrada. Se você decidir usá-lo e encontrar problemas, entre em contato.
Agradeço ao @githubphagocyte por me ajudar a escrever o controlador.
Editar: para uma entrada aleatória, você pode escolher qualquer corrida em um mapa específico como sua pontuação para esse mapa. Observe que, devido aos requisitos de pontuação, você sempre deve escolher o menor número de turnos, o menor número de costars mortos e o menor número de extras mortos para cada mapa.
fonte
Respostas:
Ruby, segurança em primeiro lugar + BFS + aleatoriedade, pontuação ≤ 1458
Não tenho certeza de como você receberá pontuações aleatórias. Se todas as respostas tiverem que ser determinísticas, avise-me e eu vou pegar uma semente ou me livrar completamente da aleatoriedade.
Alguns recursos e deficiências desta solução:
map5.txt
leva entre 1 e 13 minutos para ser concluído.Alguns resultados
Agora, aqui está o código:
Existem algumas saídas de depuração comentadas lá. Especialmente, o
if group['@']
bloco é bastante interessante porque imprime uma visualização dos dados BFS.Edit: Melhoria significativa da velocidade, interrompendo o BFS se uma mudança melhor já foi encontrada (que era o ponto de usar o BFS em primeiro lugar).
fonte