O jogo
A maioria de nós conhece o Frogger , o jogo de fliperama da década de 80 em que o objetivo é pular um sapo com segurança por uma estrada movimentada e um lago cheio de perigos para chegar com segurança em casa.
Há alguns meses, foi lançado um desafio para o desenvolvimento de um clone Frogger. Mas por que clonar Frogger quando você pode jogar Frogger? :)
Considere a seguinte grade de jogo simplificada:
XXXXXXXXXXXXXXXXXXXXXXX North Safe Zone
-----------------------
| | <<<< Express Lane West (Lane 1)
| | > Gridlock East (Lane 2)
| | << Freeflowing Traffic West (Lane 3)
| | < Gridlock West (Lane 4)
| | >>>> Express Lane East (Lane 5)
-----------------------
XXXXXXXXXXX@XXXXXXXXXXX South Safe Zone
\__________ __________/
'
23 cells horizontally
Temos cinco faixas de tráfego, cada uma com 23 células de largura e duas zonas seguras (onde o sapo pode se mover com segurança para a esquerda e direita), também com 23 células de largura. Você pode ignorar as bordas direita e esquerda, pois são para fins de clareza pictórica.
Nosso sapo começa na zona segura do sul, na célula central (12ª), como indicado por um @na figura acima.
O tempo no jogo é dividido em etapas discretas chamadas frames. Froggy é um sapo rápido e pode saltar uma célula em qualquer direção (cima, baixo, direita, esquerda) por quadro. Ele também pode optar por permanecer parado por qualquer quadro. O tráfego nas cinco faixas se move a velocidades constantes da seguinte maneira:
- o tráfego na pista expressa oeste (pista 1) move 2 células restantes em cada quadro
- o tráfego na pista leste do bloqueio (pista 2) move 1 célula para a direita a cada segundo quadro
- o tráfego na faixa oeste de tráfego livre (faixa 3) move 1 célula restante em cada quadro
- o tráfego na pista oeste do bloqueio (pista 4) move 1 célula restante a cada segundo quadro
- o tráfego na pista expressa leste (pista 5) move 2 células para a direita em cada quadro
O tráfego em si é definido exclusivamente por aprox. 3.000 timesteps neste arquivo de texto . 'Tráfego' consiste em veículos e espaços entre os veículos. Qualquer personagem que não seja um espaço faz parte de um veículo. O arquivo de texto contém cinco linhas, correspondentes às cinco faixas de tráfego (com a mesma ordem).
Para as pistas na direção oeste, no início do quadro 0 (o início do jogo), consideramos o primeiro veículo na pista um pouco além do limite direito da grade de jogo.
Para as faixas para o leste, a sequência de tráfego deve ser considerada "invertida" no sentido de que os veículos aparecem começando no final da sequência. No início do quadro 0, consideramos o primeiro veículo nessas faixas um pouco além da margem esquerda do campo de jogo.
Considere como um exemplo:
Traffic Lane 1: [|==| =
Traffic Lane 2: |) = o
Traffic Lane 3: (|[]-[]:
Traffic Lane 4: <| (oo|
Traffic Lane 5: |==|] :=)
A grade de jogo aparecerá da seguinte maneira:
Start of Frame 0 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 1 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 2 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 3 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Depois que todo o tráfego em uma faixa estiver "esgotado" (ou seja, a sequência acabar), consideraremos todos os caracteres da sequência como espaços.
Nosso sapo é esmagado se ocorrer um dos seguintes:
- o sapo ocupa uma célula ocupada por um veículo, em qualquer estrutura
- o sapo permanece parado em uma via expressa e um veículo de 1 célula de largura passa por ele nesse quadro
- o sapo pula para o leste "através" de um veículo que se dirige para o oeste ou pula para o oeste através de um veículo que se dirige para o leste
- o sapo salta fora da grade de 7 (linha) por 23 (célula), em qualquer quadro
Observe que essas são as únicas condições sob as quais um sapo é esmagado. Em particular, um sapo pulando o tráfego "com" é permitido, assim como um sapo pulando para dentro ou para fora de uma célula em uma faixa expressa que é ultrapassada por um veículo de largura 1 no mesmo quadro.
Objetivo e Pontuação
O objetivo do desafio de programação é colocar o sapo na estrada o maior número de vezes possível antes que o último veículo saia da grade de jogo . Ou seja, o programa termina imediatamente após a conclusão do quadro X , em que o quadro X é o primeiro quadro que leva a grade a um estado em que não há mais veículos presentes.
A saída do seu programa deve ser uma string (ou arquivo de texto) contendo a sequência de movimentos do sapo usando a seguinte codificação:
< frog moves left
> frog moves right
^ frog moves up
v frog moves down
. frog remains stationary
Por exemplo, a corda <<^.^indica que o sapo se move para a esquerda duas vezes, depois para cima, faz uma pausa para um quadro e depois para cima novamente.
Um ponto é marcado sempre que o sapo cruza da zona segura sul para a zona segura norte e um ponto é marcado sempre que o sapo cruza da zona segura norte para a zona segura sul.
Algumas regras importantes:
- O sapo não deve ser esmagado.
- Poste sua solução (sequência de movimentos) junto com o código do programa, em linha ou como um arquivo de texto (por exemplo, usando pastebin.com).
- Nosso sapo é presciente e precognitivo, portanto, seu programa pode usar todos e quaisquer dados de tráfego em qualquer quadro enquanto procura soluções. Isso inclui dados para o tráfego que ainda não atingiu a grade de reprodução.
- A grade não se enrola. Sair da grade fará com que o sapo seja esmagado e, portanto, não é permitido.
- Em nenhum momento o tráfego "reinicia" ou o sapo "se teleporta". A simulação é contínua.
- O sapo pode retornar à zona segura sul depois de sair, mas isso não é contado como um ponto. Da mesma forma para a zona segura norte.
- O vencedor do concurso é o programa que gera a sequência de movimentos que produz o maior número de cruzamentos.
- Para qualquer dúvida ou preocupação adicional, não hesite em perguntar na seção de comentários.
Para obter algum incentivo adicional, adicionarei uma recompensa de +100 representantes ao programa vencedor quando puder.
Bónus
+ 2,5% na pontuação básica * (até + 10%) para todos os cantos da grade de jogo em que o sapo toca. Os quatro cantos da grade são as células mais à esquerda e mais à direita das duas zonas seguras.
+ 25% para a pontuação base * se a sua sequência de movimentos mantiver o sapo confinado a +/- 4 células à esquerda ou à direita da célula inicial durante toda a simulação (é claro que ele pode se mover livremente na vertical).
Não há bônus de pontuação, mas adereços especiais no OP serão direcionados a qualquer pessoa que postar um validador de solução rápido e sujo, para que eu não precise programar um. ;) Um validador simplesmente aceitaria uma sequência de movimentos, garantiria sua legalidade (de acordo com as regras e o arquivo de tráfego) e relataria sua pontuação (ou seja, o número total de cruzamentos).
* A pontuação total é igual à pontuação base mais o bônus, arredondado para o número inteiro mais próximo.
Respostas:
C ++: 176
Resultado:
Existem menos de 8 milhões de combinações de
estadosda posição X tempo X conjunto de cantos visitados, para que possam ser pesquisados exaustivamente em menos de 1 segundo. Se o código não possui bugs, deve ser impossível vencer. A estratégia ideal era usar toda a prancha, pois isso permite que os sapos atravessem a estrada 160 vezes, contra cerca de 120 quando confinados ao centro. Visitar as esquinas não custou nenhuma passagem, pois o tráfego era muito pesado.fonte