El usuario CarpetPython publicó una nueva versión de este problema que pone un enfoque mucho mayor en las soluciones heurísticas, debido a un mayor espacio de búsqueda. Personalmente, creo que ese desafío es mucho mejor que el mío, ¡así que considera intentarlo!
Vector racing es un juego adictivo que se puede jugar con un bolígrafo y una hoja de papel cuadriculado. Dibuja una pista de carreras arbitraria en el papel, define un inicio y un final y luego dirige su automóvil de tamaño de punto de una manera por turnos. ¡Llega al final lo más rápido que puedas, pero ten cuidado de no terminar en una pared!
La pista
- El mapa es una cuadrícula bidimensional, donde cada celda tiene coordenadas enteras.
- Te mueves en las celdas de la cuadrícula.
- Cada celda de la cuadrícula es parte de la pista o es un muro.
- Exactamente una celda de seguimiento es la coordenada inicial.
- Al menos una celda de seguimiento se designa como el objetivo. Aterrizar en cualquiera de estos completa la carrera. Las celdas de objetivos múltiples no están necesariamente conectadas.
Dirigir el coche
Su automóvil comienza en una coordenada dada y con un vector de velocidad (0, 0)
. En cada turno, puede ajustar cada componente de la velocidad ±1
o dejarlo como está. Luego, el vector de velocidad resultante se agrega a la posición de su automóvil.
¡Una imagen puede ayudar! El círculo rojo era tu posición el último turno. El círculo azul es tu posición actual. Su velocidad es el vector del círculo rojo al azul. En este turno, dependiendo de cómo ajuste su velocidad, puede moverse a cualquiera de los círculos verdes.
Si aterrizas en una pared, pierdes de inmediato.
Tu tarea
Lo has adivinado: escribe un programa que, dada una pista de carreras como entrada, dirige el automóvil a una de las celdas de meta en el menor número de giros posible. Su solución debería poder tratar razonablemente bien con pistas arbitrarias y no estar específicamente optimizada para los casos de prueba proporcionados.
Entrada
Cuando se invoca su programa, lea de stdin :
target
n m
[ASCII representation of an n x m racetrack]
time
target
es el número máximo de turnos que puede tomar para completar la pista, y time
es su presupuesto de tiempo total para la pista, en segundos (no necesariamente entero). Vea a continuación los detalles sobre el tiempo.
Para la pista delimitada por nueva línea, se utilizan los siguientes caracteres:
#
- paredS
- el comienzo*
- un gol.
- todas las demás celdas de seguimiento (es decir, carretera)
n x m
Se supone que todas las celdas fuera de la cuadrícula provistas son paredes.
El origen de coordenadas está en la esquina superior izquierda.
Aquí hay un ejemplo simple:
8
4.0
9 6
###...***
###...***
###...***
......###
S.....###
......###
Usando indexación basada en 0, la coordenada inicial sería (0,4)
.
Después de cada movimiento, recibirás más información:
x y
u v
time
Donde x
, y
, u
, v
son todos los enteros 0 a base de. (x,y)
es tu posición actual y (u,v)
es tu velocidad actual. Tenga en cuenta que x+u
y / o y+v
podría estar fuera de los límites.
time
es lo que queda de su presupuesto de tiempo, en segundos. Siéntase libre de ignorar esto. Esto es solo para los participantes que realmente quieren llevar su implementación al límite de tiempo.
Cuando termine el juego (porque aterrizaste en una pared, te saliste de los límites, superaste los target
giros, se te acabó el tiempo o alcanzaste la meta), recibirás una línea vacía.
Salida
Para cada turno, escribe en stdout :
Δu Δv
donde Δu
y Δv
son cada uno uno de -1
, 0
, 1
. Esto se agregará (u,v)
para determinar su nueva posición. Solo para aclarar, las instrucciones son las siguientes
(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 0, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)
Una solución óptima para el ejemplo anterior sería
1 0
1 -1
1 0
Tenga en cuenta que el controlador no se adjunta a stderr , por lo que puede usarlo para cualquier tipo de salida de depuración que pueda necesitar al desarrollar su bot. Sin embargo, elimine / comente cualquier salida de ese tipo en su código enviado.
Tu bot puede tardar medio segundo en responder en cada turno. Para los turnos que tardan más, tendrá un presupuesto de tiempo (por pista) de target/2
segundos. Cada vez que un turno demore más de medio segundo, el tiempo adicional se restará de su presupuesto de tiempo. Cuando su presupuesto de tiempo llegue a cero, la carrera actual será abortada.
Nuevo: por razones prácticas, tengo que establecer un límite de memoria (ya que la memoria parece ser más limitante que el tiempo para tamaños de pista razonables). Por lo tanto, tendré que abortar cualquier ejecución de prueba en la que el corredor use más de 1 GB de memoria, medida por Process Explorer como Bytes privados .
Tanteo
Hay un punto de referencia de 20 pistas. Para cada pista:
- Si completa la pista, su puntaje es el número de movimientos que necesita para alcanzar una celda de gol dividido por
target
. - Si te quedas sin tiempo / memoria o no alcanzas la meta antes de que
target
hayan transcurrido los turnos o si caes en una pared / fuera de límites en cualquier momento, tu puntaje es2
. - Si su programa no es determinista, su puntaje es el promedio de más de 10 carreras en esa pista (indique esto en su respuesta).
Su puntaje general es la suma de los puntajes de las pistas individuales. ¡La puntuación más baja gana!
Además, cada participante puede (y se recomienda encarecidamente) proporcionar una pista de referencia adicional , que se agregará a la lista oficial. Las respuestas anteriores se volverán a evaluar, incluida esta nueva pista. Esto es para asegurarse de que ninguna solución se adapte demasiado a los casos de prueba existentes y para tener en cuenta los casos límite interesantes que podría haber pasado por alto (pero que puede detectar).
Desempate
Ahora que ya existe una solución óptima, este será probablemente el factor principal para los puntajes de los participantes.
Si hay un empate (debido a varias respuestas que resuelven todas las pistas de manera óptima o no), agregaré casos de prueba adicionales (más grandes) para romper el empate. Para evitar cualquier sesgo humano al crear esos desempates, estos se generarán de manera fija:
- Aumentaré la longitud del lado
n
en10
comparación con la última pista generada de esta manera. (Puedo omitir tamaños si no rompen la corbata). - La base es este gráfico vectorial
- Esto se rasterizará a la resolución deseada usando este fragmento de Mathematica .
- El inicio está en la esquina superior izquierda. En particular, será la celda más a la izquierda de la fila superior de ese extremo de la pista.
- El objetivo está en la esquina inferior derecha. En particular, será la celda más a la derecha de la fila más inferior de ese extremo de la pista.
- La
target
voluntad4*n
.
La pista final del punto de referencia inicial ya se generó así, con n = 50
.
El controlador
El programa que prueba las presentaciones está escrito en Ruby y se puede encontrar en GitHub junto con el archivo de referencia que usaré. También hay un bot de ejemplo llamado randomracer.rb
allí, que simplemente selecciona movimientos aleatorios. Puede usar su estructura básica como punto de partida para que su bot vea cómo funciona la comunicación.
Puede ejecutar su propio bot contra un archivo de seguimiento de su elección de la siguiente manera:
ruby controller.rb track_file_name command to run your racer
p.ej
ruby controller.rb benchmark.txt ruby randomracer.rb
El repositorio también contiene dos clases Point2D
y Track
. Si su envío está escrito en Ruby, no dude en reutilizarlos para su conveniencia.
Interruptores de línea de comando
Se pueden añadir modificadores de línea de comandos -v
, -s
, -t
antes del nombre de archivo del índice de referencia. Si desea utilizar varios interruptores, también se puede hacer, por ejemplo, -vs
. Esto es lo que ellos hacen:
-v
(detallado): use esto para producir un poco más de salida de depuración del controlador.
-s
(silencio): si prefiere realizar un seguimiento de su posición y velocidad usted mismo y no le importa el presupuesto de tiempo, puede desactivar esas tres líneas de salida cada turno (enviado a su envío) con esta bandera.
-t
(pistas): le permite seleccionar pistas individuales para probar. Por ejemplo -t "1,2,5..8,15"
, probaría las pistas 1, 2, 5, 6, 7, 8 y 15 solamente. Muchas gracias a Ventero por esta función y el analizador de opciones.
Su sumisión
En resumen, incluya lo siguiente en su respuesta:
- Tu puntuación.
- Si usa la aleatoriedad, indíquelo, para que pueda promediar su puntaje en varias ejecuciones.
- El código para su envío.
- La ubicación de un compilador o intérprete gratuito para su idioma de elección que se ejecuta en una máquina con Windows 8.
- Instrucciones de compilación si es necesario.
- Una cadena de línea de comandos de Windows para ejecutar su envío.
- Si su envío requiere la
-s
bandera o no. - (opcionalmente) Una nueva pista solucionable que se agregará al punto de referencia. Determinaré un razonable
target
para tu pista manualmente. Cuando la pista se agrega al punto de referencia, la editaré a partir de su respuesta. Me reservo el derecho de pedirle una pista diferente (en caso de que agregue una pista desproporcionadamente grande, incluya arte obsceno ASCII en la pista, etc.). Cuando agregue el caso de prueba al conjunto de referencia, reemplazaré la pista en su respuesta con un enlace a la pista en el archivo de referencia para reducir el desorden en esta publicación.
Como puede ver, probaré todas las presentaciones en una máquina con Windows 8. Si no hay absolutamente ninguna manera de que su envío se ejecute en Windows, también puedo probar en una máquina virtual de Ubuntu. Sin embargo, esto será considerablemente más lento, por lo que si desea maximizar el límite de tiempo, asegúrese de que su programa se ejecute en Windows.
¡Que el mejor conductor emerja vectorious!
Pero me Quiera jugar!
Si quieres probar el juego tú mismo para tener una mejor idea, existe esta implementación . Las reglas utilizadas allí son ligeramente más sofisticadas, pero creo que son lo suficientemente similares como para ser útiles.
Tabla de clasificación
Última actualización: 01/09/2014, 21:29 UTC
Pistas en el punto de referencia: 25
Tamaños de desempate: 290, 440
- 6.86688 - Kuroi Neko
- 8.73108 - usuario2357112 - 2da presentación
- 9.86627 - nneonneo
- 10.66109 - usuario2357112 - 1er envío
- 12.49643 - Rayo
- 40.0759 - seudónimo117 (probabilístico)
Resultados detallados de la prueba . (Los puntajes para los envíos probabilísticos se han determinado por separado).
fuente
400
, ya que está en línea con la forma en que determiné todos los otros objetivos (excepto el desempate). Actualizaré la publicación principal una vez que haya revisado todas las otras presentaciones.C ++, 5.4 (determinista, óptimo)
Solución de programación dinámica. Probablemente óptimo. Muy rápido: resuelve los 20 casos de prueba en 0.2s. Debería ser especialmente rápido en máquinas de 64 bits. Asume que el tablero tiene menos de 32,000 lugares en cada dirección (lo cual debería ser cierto).
Este corredor es un poco inusual. Calcula la ruta óptima en la línea de inicio, y luego ejecuta la ruta calculada al instante. Ignora el control de tiempo y supone que puede finalizar el paso de optimización a tiempo (lo que debería ser cierto para cualquier hardware razonablemente moderno). En los mapas excesivamente grandes, hay una pequeña posibilidad de que el corredor pueda fallar. Si puede convencerlo de que no tenga seguridad, obtendrá un punto de brownie y lo arreglaré para usar un bucle explícito.
Compilar con
g++ -O3
. Puede requerir C ++ 11 (para<unordered_map>
). Para ejecutar, simplemente ejecute el ejecutable compilado (no se admiten banderas u opciones; toda la entrada se toma en stdin)Resultados
Nuevo caso de prueba
fuente
Python 2 , determinista, óptimo
Aquí está mi corredor. No lo he probado en el punto de referencia (todavía no sé qué versión e instalador de Ruby instalar), pero debería resolver todo de manera óptima y dentro del límite de tiempo. El comando para ejecutarlo es
python whateveryoucallthefile.py
. Necesita la-s
bandera del controlador.Después de inspeccionar el corredor de nneonneo (pero en realidad no lo probé, ya que tampoco tengo un compilador de C ++), descubrí que parece realizar una búsqueda casi exhaustiva del espacio de estado, sin importar cuán cerca esté el objetivo o cuán corto Ya se ha encontrado un camino. También descubrí que las reglas de tiempo significan que construir un mapa con una solución larga y compleja requiere un límite de tiempo largo y aburrido. Por lo tanto, mi envío de mapas es bastante simple:
Nuevo caso de prueba
(GitHub no puede mostrar la línea larga. La pista es
*S.......[and so on].....
)Presentación adicional: Python 2, búsqueda bidireccional
Este es un enfoque que escribí hace unos dos meses, cuando trataba de optimizar mi primer envío. Para los casos de prueba que existían en ese momento, no ofrecía una mejora, por lo que no lo envié, pero para el nuevo mapa de Kuroi, parece que apenas se aprieta debajo del límite de memoria. Todavía espero que el solucionador de Kuroi supere esto, pero estoy interesado en cómo se mantiene.
fuente
n = 400
). Avíseme si aplica alguna optimización, para que pueda volver a ejecutar las pruebas.Python 3: 6.49643 (Óptimo, BFS)
Para el antiguo archivo de referencia de 20 casos, obtuvo una puntuación de 5.35643. La solución de @nneonneo no es óptima ya que obtuvo 5.4. Algunos errores tal vez.
Esta solución utiliza BFS para buscar en el gráfico, cada estado de búsqueda tiene la forma de (x, y, dx, dy). Luego uso un mapa para mapear de estados a distancias. En el peor de los casos, su complejidad de tiempo y espacio es O (n ^ 2 m ^ 2). Esto rara vez sucederá ya que la velocidad no será demasiado alta o el piloto se estrellará. En realidad, me costó 3 segundos en mi máquina completar los 22 casos de prueba.
# Resultados
fuente
O(√n)
lo que haría su implementaciónO(n³)
en cuadrículas cuadradas (igual que las otras, supongo). Agregaré un desempate para calificar su envío versus el usuario2357112 más tarde hoy.n=270
, por lo que ahora está detrás de los otros dos envíos "óptimos". Dicho esto, su presentación también es la más lenta de las tres, por lo que habría sido tercero de todos modos, solo con un desempate más grande.RandomRacer, ~ 40.0 (promedio de más de 10 carreras)
No es que este bot nunca termine una pista, pero definitivamente es mucho menos frecuente que una vez en 10 intentos. (Obtengo un puntaje que no es el peor de los casos cada 20 a 30 simulaciones más o menos).
Esto es principalmente para actuar como un caso de referencia y para demostrar una posible implementación (Ruby) para un piloto:
Ejecútalo con
fuente
Random Racer 2.0, ~ 31
Bueno, esto no va a vencer al solucionador óptimo publicado, pero es una ligera mejora en un corredor aleatorio. La principal diferencia es que este corredor solo considerará ir al azar donde no hay un muro, a menos que se quede sin lugares válidos para moverse, y si puede moverse a una meta ese turno, lo hará. Tampoco se moverá para permanecer en el mismo lugar, a menos que no haya otro movimiento disponible (improbable, pero posible).
Implementado en Java, compilado con java8, pero Java 6 debería estar bien. No hay parámetros de línea de comando. Hay un grupo bastante bueno de jerarquía, así que creo que estoy haciendo bien Java.
Los resultados (el mejor caso que he visto)
fuente
.class
archivo por alguna razón (en lugar del directorio donde está el controlador). Haga ping (con un comentario) si decide agregar un caso de prueba, para que pueda agregarlo al punto de referencia. Su puntaje fue de aproximadamente 33 en 10 carreras (ver tabla de clasificación), pero esto bien podría cambiar con cada nueva pista de prueba que se agregue al punto de referencia.java -cp path/to/class/file VectorRacing