El juego
La mayoría de nosotros conocemos a Frogger , el juego de arcade de la era de los 80 en el que el objetivo es saltar a una rana de forma segura a través de una carretera concurrida y un estanque lleno de peligros para llegar a salvo a casa.
Hace unos meses se lanzó un desafío para desarrollar un clon de Frogger. Pero, ¿por qué clonar Frogger cuando puedes jugar a Frogger? :)
Considere la siguiente cuadrícula de juego 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
Tenemos cinco carriles de tráfico, cada uno de 23 celdas de ancho, y dos zonas seguras (donde la rana puede moverse con seguridad de izquierda a derecha), también de 23 celdas de ancho. Puede ignorar los bordes derecho e izquierdo, ya que estos son para mayor claridad pictórica.
Nuestra rana comienza en la zona segura del sur, en la celda central (12), como se indica con a @en la figura anterior.
El tiempo en el juego se divide en pasos discretos llamados marcos. Froggy es una rana rápida y puede saltar una celda en cualquier dirección (arriba, abajo, derecha, izquierda) por cuadro. También puede optar por permanecer estacionario para cualquier cuadro. El tráfico en los cinco carriles se mueve a velocidades constantes de la siguiente manera:
- el tráfico en el carril expreso oeste (carril 1) mueve 2 celdas a la izquierda de cada cuadro
- el tráfico en el carril este del embotellamiento (carril 2) se mueve 1 celda a la derecha cada segundo cuadro
- el tráfico en el carril oeste de tráfico libre (carril 3) se mueve 1 celda a la izquierda de cada cuadro
- el tráfico en el carril oeste del embotellamiento (carril 4) se mueve 1 celda a la izquierda cada segundo cuadro
- el tráfico en el carril expreso este (carril 5) mueve 2 celdas a la derecha en cada cuadro
El tráfico en sí está definido de manera única por aprox. 3.000 pasos en este archivo de texto . El 'tráfico' consiste en vehículos y espacios entre los vehículos. Cualquier personaje que no sea un espacio es parte de un vehículo. El archivo de texto contiene cinco líneas, correspondientes a los cinco carriles de tráfico (con el mismo orden).
Para los carriles hacia el oeste, al comienzo del cuadro 0 (el inicio del juego), consideramos que el primer vehículo en el carril está más allá del borde derecho de la cuadrícula de juego.
Para los carriles hacia el este, la cadena de tráfico debe considerarse "hacia atrás" en el sentido de que los vehículos aparecen comenzando al final de la cadena. Al comienzo del cuadro 0, consideramos que el primer vehículo en estos carriles está más allá del borde izquierdo del campo de juego.
Considere como un ejemplo:
Traffic Lane 1: [|==| =
Traffic Lane 2: |) = o
Traffic Lane 3: (|[]-[]:
Traffic Lane 4: <| (oo|
Traffic Lane 5: |==|] :=)
Entonces la cuadrícula de juego aparecerá de la siguiente manera:
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
Después de que todo el tráfico en un carril se "agota" (es decir, la cadena se agota), consideramos que todos los caracteres de la cadena son espacios.
Nuestra rana se aplasta si ocurre algo de lo siguiente:
- la rana ocupa una celda ocupada por un vehículo, en cualquier marco
- la rana permanece estacionaria en un carril rápido y un vehículo de 1 celda de ancho pasa sobre él en ese marco
- la rana salta al este "a través" de un vehículo que se dirige hacia el oeste, o salta al oeste a través de un vehículo que se dirige al este
- la rana salta fuera de la cuadrícula de juego 7 (línea) por 23 (celda), en cualquier cuadro
Tenga en cuenta que estas son las únicas condiciones bajo las cuales se aplasta una rana. En particular, una rana que salta junto con el tráfico "con" es permisible, como lo es una rana que salta dentro o fuera de una celda en un carril expreso que es pasado por un vehículo de ancho 1 en el mismo marco.
Objetivo y puntuación
El objetivo del desafío de programación es hacer que la rana cruce la carretera tantas veces como sea posible antes de que el último vehículo salga de la parrilla de juego . Es decir, el programa termina inmediatamente después de completar el cuadro X , donde el cuadro X es el primer cuadro que lleva la cuadrícula a un estado en el que no hay más vehículos presentes.
La salida de su programa debe ser una cadena (o archivo de texto) que contenga la secuencia de movimientos para la rana usando la siguiente codificación:
< frog moves left
> frog moves right
^ frog moves up
v frog moves down
. frog remains stationary
Por ejemplo, la cadena <<^.^indica que la rana se mueve hacia la izquierda dos veces, luego hacia arriba, luego hace una pausa por un cuadro y luego se mueve hacia arriba nuevamente.
Se puntúa un punto cada vez que la rana cruza desde la zona segura del sur hacia la zona segura del norte, y un punto se puntúa cuando la rana cruza desde la zona segura del norte hacia la zona segura del sur.
Algunas reglas importantes:
- La rana no debe ser aplastada.
- Publique su solución (secuencia de movimientos) junto con su código de programa, ya sea en línea o como un archivo de texto (por ejemplo, usando pastebin.com).
- Nuestra rana es premonitoria y precognitiva, por lo tanto, su programa puede utilizar todos los datos de tráfico en cualquier marco mientras busca soluciones. Esto incluye datos para el tráfico que aún no ha llegado a la grilla de juego.
- La cuadrícula no se ajusta. Salir de la cuadrícula hará que la rana se aplaste y, por lo tanto, no está permitido.
- En ningún momento el tráfico se "reinicia" o la rana se "teletransporta". La simulación es continua.
- La rana puede regresar a la zona segura del sur después de salir, pero esto no se cuenta como un punto. Asimismo para la zona segura norte.
- El ganador del concurso es el programa que genera la secuencia de movimiento que produce el mayor número de cruces.
- Para cualquier pregunta o inquietud adicional, no dude en preguntar en la sección de comentarios.
Para un incentivo adicional, agregaré una recompensa de +100 repeticiones al programa ganador cuando pueda hacerlo.
Bonos
+ 2.5% al puntaje base * (hasta + 10%) por cada esquina de la cuadrícula de juego que toque la rana. Las cuatro esquinas de la cuadrícula son las celdas más a la izquierda y a la derecha de las dos zonas seguras.
+ 25% al puntaje base * si su secuencia de movimientos mantiene a la rana confinada dentro de +/- 4 celdas a la izquierda o derecha de su celda inicial durante toda la simulación (por supuesto, puede moverse libremente verticalmente).
No hay bonificación de puntuación, pero los accesorios especiales en el OP irán a cualquiera que publique un validador de solución rápida y sucia para que no tenga que programar uno. ;) Un validador simplemente aceptaría una secuencia de movimientos, garantizaría su legalidad (según las reglas y el archivo de tráfico) e informaría su puntaje (es decir, el número total de cruces).
* El puntaje total es igual al puntaje base más el bono, redondeado al entero más cercano.
Respuestas:
C ++: 176
Salida:
Hay menos de 8 millones de combinaciones de
estadosde posición X tiempo X conjunto de esquinas visitadas, por lo que se pueden buscar exhaustivamente en menos de 1 segundo. Si el código no tiene errores, debería ser imposible de superar. La estrategia óptima era usar toda la tabla, ya que eso permite que la rana cruce la carretera 160 veces, frente a aproximadamente 120 cuando está confinada al centro. Visitar las esquinas no costó ningún cruce ya que el tráfico era muy pesado.fuente