A Vectory! - El Gran Premio de Vector Racing

39

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 ±1o 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.

                                    ingrese la descripción de la imagen aquí

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

targetes el número máximo de turnos que puede tomar para completar la pista, y timees 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:

  • # - pared
  • S- el comienzo
  • *- un gol
  • . - todas las demás celdas de seguimiento (es decir, carretera)

n x mSe 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, vson 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+uy / o y+vpodría estar fuera de los límites.

timees 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 targetgiros, 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 Δuy Δvson 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/2segundos. 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 portarget .
  • Si te quedas sin tiempo / memoria o no alcanzas la meta antes de que targethayan transcurrido los turnos o si caes en una pared / fuera de límites en cualquier momento, tu puntaje es 2.
  • 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 nen 10comparació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 targetvoluntad 4*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.rballí, 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 Point2Dy 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, -tantes 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 -sbandera o no.
  • (opcionalmente) Una nueva pista solucionable que se agregará al punto de referencia. Determinaré un razonable targetpara 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

  1. 6.86688 - Kuroi Neko
  2. 8.73108 - usuario2357112 - 2da presentación
  3. 9.86627 - nneonneo
  4. 10.66109 - usuario2357112 - 1er envío
  5. 12.49643 - Rayo
  6. 40.0759 - seudónimo117 (probabilístico)

Resultados detallados de la prueba . (Los puntajes para los envíos probabilísticos se han determinado por separado).

Martin Ender
fuente

Respuestas:

5

C ++ 11 - 6.66109

Otra implementación más amplia de primera búsqueda, solo optimizada.

Debe ejecutarse con la opción -s .
Su entrada no está desinfectada en absoluto, por lo que las pistas incorrectas podrían convertirla en una calabaza.

Lo probé con Microsoft Visual C ++ 2013, lanzamiento de compilación con el indicador predeterminado / O2 (optimizar para la velocidad).
Construye bien con g ++ y el IDE de Microsoft.
Mi asignador de memoria barebone es una mierda, ¡así que no esperes que funcione con otras implementaciones de STL de unordered_set!

#include <cstdint>
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
#include <unordered_set>

#define MAP_START 'S'
#define MAP_WALL  '#'
#define MAP_GOAL  '*'

#define NODE_CHUNK_SIZE   100 // increasing this will not improve performances
#define VISIT_CHUNK_SIZE 1024 // increasing this will slightly reduce mem consumption at the (slight) cost of speed

#define HASH_POS_BITS 8 // number of bits for one coordinate
#define HASH_SPD_BITS (sizeof(size_t)*8/2-HASH_POS_BITS)

typedef int32_t tCoord; // 32 bits required to overcome the 100.000 cells (insanely) long challenge

// basic vector arithmetics
struct tPoint {
    tCoord x, y;
    tPoint(tCoord x = 0, tCoord y = 0) : x(x), y(y) {}
    tPoint operator+ (const tPoint & p) { return tPoint(x + p.x, y + p.y); }
    tPoint operator- (const tPoint & p) { return tPoint(x - p.x, y - p.y); }
    bool operator== (const tPoint & p) const { return p.x == x && p.y == y;  }
};

// a barebone block allocator. Improves speed by about 30%
template <class T, size_t SIZE> class tAllocator
{
    T * chunk;
    size_t i_alloc;
    size_t m_alloc;
public:
    typedef T                 value_type;
    typedef value_type*       pointer;
    typedef const value_type* const_pointer;
    typedef std::size_t       size_type;
    typedef value_type&       reference;
    typedef const value_type& const_reference;
    tAllocator()                                              { m_alloc = i_alloc = SIZE; }
    template <class U> tAllocator(const tAllocator<U, SIZE>&) { m_alloc = i_alloc = SIZE; }
    template <class U> struct rebind { typedef tAllocator<U, SIZE> other; };
    pointer allocate(size_type n, const_pointer = 0)
    {
        if (n > m_alloc) { i_alloc = m_alloc = n; }      // grow max size if request exceeds capacity
        if ((i_alloc + n) > m_alloc) i_alloc = m_alloc;  // dump current chunk if not enough room available
        if (i_alloc == m_alloc) { chunk = new T[m_alloc]; i_alloc = 0; } // allocate new chunk when needed
        T * mem = &chunk[i_alloc];
        i_alloc += n;
        return mem;
    }
    void deallocate(pointer, size_type) { /* memory is NOT released until process exits */ }
    void construct(pointer p, const value_type& x) { new(p)value_type(x); }
    void destroy(pointer p) { p->~value_type(); }
};

// a node in our search graph
class tNode {
    static tAllocator<tNode, NODE_CHUNK_SIZE> mem; // about 10% speed gain over a basic allocation
    tNode * parent;
public:
    tPoint pos;
    tPoint speed;
    static tNode * alloc (tPoint pos, tPoint speed, tNode * parent) { return new (mem.allocate(1)) tNode(pos, speed, parent); }
    tNode (tPoint pos = tPoint(), tPoint speed = tPoint(), tNode * parent = nullptr) : parent(parent), pos(pos), speed(speed) {}
    bool operator== (const tNode& n) const { return n.pos == pos && n.speed == speed; }
    void output(void)
    {
        std::string output;
        tPoint v = this->speed;
        for (tNode * n = this->parent ; n != nullptr ; n = n->parent)
        {
            tPoint a = v - n->speed;
            v = n->speed;
            std::ostringstream ss;  // a bit of shitty c++ text I/O to print elements in reverse order
            ss << a.x << ' ' << a.y << '\n';
            output = ss.str() + output;
        }
        std::cout << output;
    }
};
tAllocator<tNode, NODE_CHUNK_SIZE> tNode::mem;

// node queueing and storing
static int num_nodes = 0;
class tNodeJanitor {
    // set of already visited nodes. Block allocator improves speed by about 20%
    struct Hasher { size_t operator() (tNode * const n) const 
    {
        int64_t hash = // efficient hashing is the key of performances
            ((int64_t)n->pos.x   << (0 * HASH_POS_BITS))
          ^ ((int64_t)n->pos.y   << (1 * HASH_POS_BITS))
          ^ ((int64_t)n->speed.x << (2 * HASH_POS_BITS + 0 * HASH_SPD_BITS))
          ^ ((int64_t)n->speed.y << (2 * HASH_POS_BITS + 1 * HASH_SPD_BITS));
        return (size_t)((hash >> 32) ^ hash);
        //return (size_t)(hash);
    }
    };
    struct Equalizer { bool operator() (tNode * const n1, tNode * const n2) const
        { return *n1 == *n2; }};
    std::unordered_set<tNode *, Hasher, Equalizer, tAllocator<tNode *, VISIT_CHUNK_SIZE>> visited;
    std::queue<tNode *> queue; // currently explored nodes queue
public:
    bool empty(void) { return queue.empty();  }
    tNode * dequeue() { tNode * n = queue.front(); queue.pop(); return n; }
    tNode * enqueue_if_new (tPoint pos, tPoint speed = tPoint(0,0), tNode * parent = nullptr)
    {
        tNode signature (pos, speed);
        tNode * n = nullptr;
        if (visited.find (&signature) == visited.end()) // the classy way to check if an element is in a set
        {
            n = tNode::alloc(pos, speed, parent);
            queue.push(n);
            visited.insert (n);
num_nodes++;
        }
        return n;
    }
};

// map representation
class tMap {
    std::vector<char> cell;
    tPoint dim; // dimensions
public:
    void set_size(tCoord x, tCoord y) { dim = tPoint(x, y); cell.resize(x*y); }
    void set(tCoord x, tCoord y, char c) { cell[y*dim.x + x] = c; }
    char get(tPoint pos)
    {
        if (pos.x < 0 || pos.x >= dim.x || pos.y < 0 || pos.y >= dim.y) return MAP_WALL;
        return cell[pos.y*dim.x + pos.x];
    }
    void dump(void)
    {
        for (int y = 0; y != dim.y; y++)
        {
            for (int x = 0; x != dim.x; x++) fprintf(stderr, "%c", cell[y*dim.x + x]);
            fprintf(stderr, "\n");
        }
    }
};

// race manager
class tRace {
    tPoint start;
    tNodeJanitor border;
    static tPoint acceleration[9];
public:
    tMap map;
    tRace ()
    {
        int target;
        tCoord sx, sy;
        std::cin >> target >> sx >> sy;
        std::cin.ignore();
        map.set_size (sx, sy);
        std::string row;
        for (int y = 0; y != sy; y++)
        {
            std::getline(std::cin, row);
            for (int x = 0; x != sx; x++)
            {
                char c = row[x];
                if (c == MAP_START) start = tPoint(x, y);
                map.set(x, y, c);
            }
        }
    }

    // all the C++ crap above makes for a nice and compact solver
    tNode * solve(void)
    {
        tNode * initial = border.enqueue_if_new (start);
        while (!border.empty())
        {
            tNode * node = border.dequeue();
            tPoint p = node->pos;
            tPoint v = node->speed;
            for (tPoint a : acceleration)
            {
                tPoint nv = v + a;
                tPoint np = p + nv;
                char c = map.get(np);
                if (c == MAP_WALL) continue;
                if (c == MAP_GOAL) return new tNode (np, nv, node);
                border.enqueue_if_new (np, nv, node);
            }
        }
        return initial; // no solution found, will output nothing
    }
};
tPoint tRace::acceleration[] = {
    tPoint(-1,-1), tPoint(-1, 0), tPoint(-1, 1),
    tPoint( 0,-1), tPoint( 0, 0), tPoint( 0, 1),
    tPoint( 1,-1), tPoint( 1, 0), tPoint( 1, 1)};

#include <ctime>
int main(void)
{
    tRace race;
    clock_t start = clock();
    tNode * solution = race.solve();
    std::cerr << "time: " << (clock()-start)/(CLOCKS_PER_SEC/1000) << "ms nodes: " << num_nodes << std::endl;
    solution->output();
    return 0;
}

Resultados

 No.       Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1       37 x 1        36   0.22222   Racer reached goal at ( 36, 0) in 8 turns.
  2       38 x 1        37   0.24324   Racer reached goal at ( 37, 0) in 9 turns.
  3       33 x 1        32   0.25000   Racer reached goal at ( 32, 0) in 8 turns.
  4       10 x 10       10   0.40000   Racer reached goal at ( 7, 7) in 4 turns.
  5        9 x 6         8   0.37500   Racer reached goal at ( 6, 0) in 3 turns.
  6       15 x 7        16   0.37500   Racer reached goal at ( 12, 4) in 6 turns.
  7       17 x 8        16   0.31250   Racer reached goal at ( 14, 0) in 5 turns.
  8       19 x 13       18   0.27778   Racer reached goal at ( 0, 11) in 5 turns.
  9       60 x 10      107   0.14953   Racer reached goal at ( 0, 6) in 16 turns.
 10       31 x 31      106   0.23585   Racer reached goal at ( 27, 0) in 25 turns.
 11       31 x 31      106   0.24528   Racer reached goal at ( 15, 15) in 26 turns.
 12       50 x 20       50   0.24000   Racer reached goal at ( 49, 10) in 12 turns.
 13      100 x 100    2600   0.01385   Racer reached goal at ( 50, 0) in 36 turns.
 14       79 x 63      242   0.24380   Racer reached goal at ( 3, 42) in 59 turns.
 15       26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16       17 x 1        19   0.52632   Racer reached goal at ( 16, 0) in 10 turns.
 17       50 x 1        55   0.34545   Racer reached goal at ( 23, 0) in 19 turns.
 18       10 x 7        23   0.34783   Racer reached goal at ( 1, 3) in 8 turns.
 19       55 x 55       45   0.17778   Racer reached goal at ( 50, 26) in 8 turns.
 20      101 x 100     100   0.14000   Racer reached goal at ( 99, 99) in 14 turns.
 21   100000 x 1         1   1.00000   Racer reached goal at ( 0, 0) in 1 turns.
 22       50 x 50      200   0.05500   Racer reached goal at ( 47, 46) in 11 turns.
 23      290 x 290    1160   0.16466   Racer reached goal at ( 269, 265) in 191 turns.
-------------------------------------------------------------------------------------
TOTAL SCORE:                 6.66109

Actuaciones

Ese horrible lenguaje C ++ tiene una habilidad especial para hacerte saltar a través de aros solo para mover un fósforo. Sin embargo, puede utilizarlo para producir código relativamente rápido y eficiente en la memoria.

Hashing

Aquí la clave es proporcionar una buena tabla hash para los nodos. Ese es, con mucho, el factor dominante para la velocidad de ejecución.
Dos implementaciones de unordered_set(GNU y Microsoft) arrojaron una diferencia de velocidad de ejecución del 30% (¡a favor de GNU, yay!).

La diferencia no es realmente sorprendente, con las cargas de código ocultas detrás unordered_set.

Por curiosidad, hice algunas estadísticas sobre el estado final de la tabla hash.
Ambos algoritmos terminan con casi la misma relación cubo / elementos, pero
la distribución varía: para el desempate 290x290, GNU obtiene un promedio de 1.5 elementos por cubo no vacío, mientras que Microsoft está en 5.8 (!).

Parece que Microsoft no aleatoriza muy bien mi función de hashing ... Me pregunto si los chicos de Redmond realmente compararon su STL, o tal vez mi caso de uso simplemente favorece la implementación de GNU ...

Claro, mi función de hash no es ni mucho menos óptima. Podría haber usado la mezcla de enteros habitual basada en desplazamiento múltiple / muls, pero una función eficiente de hash requiere tiempo para calcular.

Parece que el número de consultas de la tabla hash es muy alto en comparación con el número de inserciones. Por ejemplo, en el desempate 290x290, tiene alrededor de 3.6 millones de inserciones para 22.7 millones de consultas.
En este contexto, un hash subóptimo pero rápido produce mejores rendimientos.

Asignación de memoria

Proporcionar un asignador de memoria eficiente es lo segundo. Mejoró el rendimiento en aproximadamente un 30%. Si vale la pena el código basura añadido es discutible :).

La versión actual usa entre 40 y 55 bytes por nodo.
Los datos funcionales requieren 24 bytes para un nodo (4 coordenadas y 2 punteros).
Debido al loco caso de prueba de 100.000 líneas, las coordenadas deben almacenarse en palabras de 4 bytes, de lo contrario, podría ganar 8 bytes usando cortos (con un valor de coordenadas máximo de 32767). Los bytes restantes son consumidos principalmente por la tabla hash del conjunto desordenado. Significa que el manejo de datos en realidad consume un poco más que la carga útil "útil".

Y el ganador es...

En mi PC con Win7, el desempate (caso 23, 290x290) se resuelve con la peor versión (es decir, compilada por Microsoft) en aproximadamente 2.2 segundos, con un consumo de memoria de aproximadamente 185 Mb.
A modo de comparación, el líder actual (código python por user2357112) tarda un poco más de 30 segundos y consume alrededor de 780 Mb.

Problemas de controlador

No estoy seguro de poder codificar en Ruby para salvar mi vida.
Sin embargo, descubrí y pirateé dos problemas del código del controlador:

1) lectura de mapas en track.rb

Con Ruby 1.9.3 instalado, el lector de pistas se burlaría de shift.to_ino estar disponible string.lines.
Después de leer un poco la documentación en línea de Ruby, abandoné las cadenas y usé una matriz intermedia en su lugar, así (justo al comienzo del archivo):

def initialize(string)
    @track = Array.new;
    string.lines.each do |line|
        @track.push (line.chomp)
    end

2) matando fantasmas en controller.rb

Como otros carteles ya han señalado, el controlador a veces intenta matar procesos que ya han salido. Para evitar estas salidas de error vergonzosas, simplemente manejé la excepción, así (alrededor de la línea 134):

if silent
    begin # ;!;
        Process.kill('KILL', racer.pid)
    rescue Exception => e
    end

Caso de prueba

Para vencer el enfoque de la fuerza bruta de los solucionadores de BFS, la peor pista es lo opuesto al mapa de 100.000 células: un área completamente libre con el objetivo lo más lejos posible desde el principio.

En este ejemplo, un mapa de 100x400 con el objetivo en la esquina superior izquierda y el inicio en la esquina inferior derecha.

Este mapa tiene una solución en 28 turnos, pero un solucionador de BFS explorará millones de estados para encontrarlo (¡el mío contó con 10.022.658 estados visitados, tomó aproximadamente 12 segundos y alcanzó un máximo de 600 Mb!).

Con menos de la mitad de la superficie del disyuntor de 290x290, requiere aproximadamente 3 veces más visitas a los nodos. Por otro lado, un solucionador heurístico / basado en A * debería vencerlo fácilmente.

30
100 400
*...................................................................................................
....................................................................................................
                          < 400 lines in all >
....................................................................................................
....................................................................................................
...................................................................................................S

Bonificación: una versión PHP equivalente (pero algo menos eficiente)

Esto es con lo que comencé, antes de que la lentitud inherente del lenguaje me convenciera de usar C ++.
Las tablas hash internas de PHP no parecen tan eficientes como las de Python, al menos en este caso particular :).

<?php

class Trace {
    static $file;
    public static $state_member;
    public static $state_target;
    static function msg ($msg)
    {
        fputs (self::$file, "$msg\n");
    }

    static function dump ($var, $msg=null)
    {
        ob_start();
        if ($msg) echo "$msg ";
        var_dump($var);
        $dump=ob_get_contents();
        ob_end_clean();
        fputs (self::$file, "$dump\n");
    }

    function init ($fname)
    {
        self::$file = fopen ($fname, "w");
    }
}
Trace::init ("racer.txt");

class Point {
    public $x;
    public $y;

    function __construct ($x=0, $y=0)
    {
        $this->x = (float)$x;
        $this->y = (float)$y;
    }

    function __toString ()
    {
        return "[$this->x $this->y]";
    }

    function add ($v)
    {
        return new Point ($this->x + $v->x, $this->y + $v->y);
    }

    function vector_to ($goal)
    {
        return new Point ($goal->x - $this->x, $goal->y - $this->y);
    }
}

class Node {
    public $posx  , $posy  ;
    public $speedx, $speedy;
    private $parent;

    public function __construct ($posx, $posy, $speedx, $speedy, $parent)
    {
        $this->posx = $posx;
        $this->posy = $posy;
        $this->speedx = $speedx;
        $this->speedy = $speedy;
        $this->parent = $parent;
    }

    public function path ()
    {
        $res = array();
        $v = new Point ($this->speedx, $this->speedy);
        for ($node = $this->parent ; $node != null ; $node = $node->parent)
        {
            $nv = new Point ($node->speedx, $node->speedy);
            $a = $nv->vector_to ($v);
            $v = new Point ($node->speedx, $node->speedy);
            array_unshift ($res, $a);
        }
        return $res;
    }
}

class Map {

    private static $target;       // maximal number of turns
    private static $time;         // time available to solve
    private static $sx, $sy;      // map dimensions
    private static $cell;         // cells of the map
    private static $start;        // starting point
    private static $acceleration; // possible acceleration values

    public static function init ()
    {
        // read map definition
        self::$target = trim(fgets(STDIN));
        list (self::$sx, self::$sy) = explode (" ", trim(fgets(STDIN)));
        self::$cell = array();
        for ($y = 0 ; $y != self::$sy ; $y++) self::$cell[] = str_split (trim(fgets(STDIN)));
        self::$time = trim(fgets(STDIN));

        // get starting point
        foreach (self::$cell as $y=>$row)
        {
            $x = array_search ("S", $row);
            if ($x !== false)
            {
                self::$start = new Point ($x, $y);
Trace::msg ("start ".self::$start);
                break;
            }
        }

        // compute possible acceleration values
        self::$acceleration = array();
        for ($x = -1 ; $x <= 1 ; $x++)
        for ($y = -1 ; $y <= 1 ; $y++)
        {
            self::$acceleration[] = new Point ($x, $y);
        }
    }

    public static function solve ()
    {
        $now = microtime(true);
        $res = array();
        $border = array (new Node (self::$start->x, self::$start->y, 0, 0, null));
        $present = array (self::$start->x." ".self::$start->y." 0 0" => 1);
        while (count ($border))
        {
if ((microtime(true) - $now) > 1)
{
Trace::msg (count($present)." nodes, ".round(memory_get_usage(true)/1024)."K");
$now = microtime(true);
}
            $node = array_shift ($border);
//Trace::msg ("node $node->pos $node->speed");
            $px = $node->posx;
            $py = $node->posy;
            $vx = $node->speedx;
            $vy = $node->speedy;
            foreach (self::$acceleration as $a)
            {
                $nvx = $vx + $a->x;
                $nvy = $vy + $a->y;
                $npx = $px + $nvx;
                $npy = $py + $nvy;
                if ($npx < 0 || $npx >= self::$sx || $npy < 0 || $npy >= self::$sy || self::$cell[$npy][$npx] == "#")
                {
//Trace::msg ("invalid position $px,$py $vx,$vy -> $npx,$npy");
                    continue;
                }
                if (self::$cell[$npy][$npx] == "*")
                {
Trace::msg ("winning position $px,$py $vx,$vy -> $npx,$npy");
                    $end = new Node ($npx, $npy, $nvx, $nvy, $node);
                    $res = $end->path ();
                    break 2;
                }
//Trace::msg ("checking $np $nv");
                $signature = "$npx $npy $nvx $nvy";
                if (isset ($present[$signature])) continue;
//Trace::msg ("*** adding $np $nv");
                $border[] = new Node ($npx, $npy, $nvx, $nvy, $node);
                $present[$signature] = 1;
            }
        }
        return $res;
    }
}

ini_set("memory_limit","1000M");
Map::init ();
$res = Map::solve();
//Trace::dump ($res);
foreach ($res as $a) echo "$a->x $a->y\n";
?>

fuente
erf ... Mi asignador de barebone es demasiado básico. Agregaré la basura necesaria para que funcione con g ++, entonces. Lo siento por eso.
OK, eso está arreglado. La versión g ++ incluso funciona en realidad un 30% más rápido. Ahora genera algunas estadísticas en stderr. Siéntase libre de comentarlo (desde las últimas líneas de la fuente). Perdón por el error.
Bien, funciona ahora y reproduje tu puntaje. ¡Es muy rápido! :) Agregaré su caso de prueba al punto de referencia, pero cambiaré el objetivo a 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.
Martin Ender
Actualizados los resultados. No hubo necesidad de un desempate, porque todas las demás presentaciones exceden el límite de memoria en su pista de prueba. ¡Felicidades por eso! :)
Martin Ender
Gracias. En realidad, este desafío me dio la oportunidad de profundizar en estas tablas hash STL. Aunque odio las agallas de C ++, no puedo evitar ser asesinado por mi curiosidad. ¡Maullar! :).
10

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)

#include <unordered_map>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

#include <cstdint>

#define MOVES_INF (1<<30)

union state {
    struct {
        short px, py, vx, vy;
    };
    uint64_t val;
};

struct result {
    int nmoves;
    short dvx, dvy;
};

typedef std::unordered_map<uint64_t, result> cache_t;
int target, n, m;
std::vector<std::string> track;
cache_t cache;

static int solve(uint64_t val) {
    cache_t::iterator it = cache.find(val);
    if(it != cache.end())
        return it->second.nmoves;

    // prevent recursion
    result res;
    res.nmoves = MOVES_INF;
    cache[val] = res;

    state cur;
    cur.val = val;
    for(int dvx = -1; dvx <= 1; dvx++) for(int dvy = -1; dvy <= 1; dvy++) {
        state next;
        next.vx = cur.vx + dvx;
        next.vy = cur.vy + dvy;
        next.px = cur.px + next.vx;
        next.py = cur.py + next.vy;
        if(next.px < 0 || next.px >= n || next.py < 0 || next.py >= m)
            continue;
        char c = track[next.py][next.px];
        if(c == '*') {
            res.nmoves = 1;
            res.dvx = dvx;
            res.dvy = dvy;
            break;
        } else if(c == '#') {
            continue;
        } else {
            int score = solve(next.val) + 1;
            if(score < res.nmoves) {
                res.nmoves = score;
                res.dvx = dvx;
                res.dvy = dvy;
            }
        }
    }

    cache[val] = res;
    return res.nmoves;
}

bool solve_one() {
    std::string line;
    float time;

    std::cin >> target;
    // std::cin >> time; // uncomment to use "time" control
    std::cin >> n >> m;
    if(!std::cin)
        return false;
    std::cin.ignore(); // skip newline at end of "n m" line

    track.clear();
    track.reserve(m);

    for(int i=0; i<m; i++) {
        std::getline(std::cin, line);
        track.push_back(line);
    }

    cache.clear();

    state cur;
    cur.vx = cur.vy = 0;
    for(int y=0; y<m; y++) for(int x=0; x<n; x++) {
        if(track[y][x] == 'S') {
            cur.px = x;
            cur.py = y;
            break;
        }
    }

    solve(cur.val);

    int sol_len = 0;
    while(track[cur.py][cur.px] != '*') {
        cache_t::iterator it = cache.find(cur.val);
        if(it == cache.end() || it->second.nmoves >= MOVES_INF) {
            std::cerr << "Failed to solve at p=" << cur.px << "," << cur.py << " v=" << cur.vx << "," << cur.vy << std::endl;
            return true;
        }

        int dvx = it->second.dvx;
        int dvy = it->second.dvy;
        cur.vx += dvx;
        cur.vy += dvy;
        cur.px += cur.vx;
        cur.py += cur.vy;
        std::cout << dvx << " " << dvy << std::endl;
        sol_len++;
    }

    //std::cerr << "Score: " << ((float)sol_len) / target << std::endl;

    return true;
}

int main() {
    /* benchmarking: */
    //while(solve_one())
    //    ;

    /* regular running */
    solve_one();
    std::string line;
    while(std::cin) std::getline(std::cin, line);

    return 0;
}

Resultados

 No.    Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1    37 x 1        36   0.22222   Racer reached goal at ( 36, 0) in 8 turns.
  2    38 x 1        37   0.24324   Racer reached goal at ( 37, 0) in 9 turns.
  3    33 x 1        32   0.25000   Racer reached goal at ( 32, 0) in 8 turns.
  4    10 x 10       10   0.40000   Racer reached goal at ( 7, 7) in 4 turns.
  5     9 x 6         8   0.37500   Racer reached goal at ( 6, 0) in 3 turns.
  6    15 x 7        16   0.37500   Racer reached goal at ( 12, 4) in 6 turns.
  7    17 x 8        16   0.31250   Racer reached goal at ( 15, 0) in 5 turns.
  8    19 x 13       18   0.27778   Racer reached goal at ( 1, 11) in 5 turns.
  9    60 x 10      107   0.14953   Racer reached goal at ( 2, 6) in 16 turns.
 10    31 x 31      106   0.25472   Racer reached goal at ( 28, 0) in 27 turns.
 11    31 x 31      106   0.24528   Racer reached goal at ( 15, 15) in 26 turns.
 12    50 x 20       50   0.24000   Racer reached goal at ( 49, 10) in 12 turns.
 13   100 x 100    2600   0.01385   Racer reached goal at ( 50, 0) in 36 turns.
 14    79 x 63      242   0.26860   Racer reached goal at ( 3, 42) in 65 turns.
 15    26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16    17 x 1        19   0.52632   Racer reached goal at ( 16, 0) in 10 turns.
 17    50 x 1        55   0.34545   Racer reached goal at ( 23, 0) in 19 turns.
 18    10 x 7        23   0.34783   Racer reached goal at ( 1, 3) in 8 turns.
 19    55 x 55       45   0.17778   Racer reached goal at ( 52, 26) in 8 turns.
 20    50 x 50      200   0.05500   Racer reached goal at ( 47, 46) in 11 turns.
-------------------------------------------------------------------------------------
TOTAL SCORE:              5.40009

Nuevo caso de prueba

nneonneo
fuente
1
Bueno, algo como esto era bastante esperado. Simplemente no hay suficiente estado en el rompecabezas para hacer inviable la programación dinámica. Si ingreso, tendré que enviar un mapa que requiera estrategias de búsqueda más sofisticadas para resolver.
user2357112 es compatible con Monica el
¿Cómo se desempeña tu piloto en tu caso de prueba?
user2357112 es compatible con Monica el
0.14 (14 movimientos)
nneonneo
¿Se toma ese tiempo o se mueve / objetivo? Si se trata de movimientos / objetivo, ¿cómo funciona en términos de tiempo?
user2357112 es compatible con Monica el
1
Creo que he encontrado un error en el código de prevención del ciclo. Se supone que para cada estado de los alcances de búsqueda de un estado S, una ruta óptima no puede ser para volver a S. Podría parecer que si un camino óptimo no retorno a S, entonces el estado no puede estar en un camino óptimo (ya que podía simplemente elimine el bucle en el que está activado y obtenga un camino más corto), por lo que no nos importa si obtenemos un resultado demasiado alto para ese estado. Sin embargo, si una ruta óptima pasa por los estados A y B en ese orden, pero la búsqueda primero encuentra A mientras B todavía está en la pila, los resultados de A están envenenados por la prevención de bucle.
user2357112 es compatible con Monica el
6

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 -sbandera del controlador.

# Breadth-first search.
# Future directions: bidirectional search and/or A*.

import operator
import time

acceleration_options = [(dvx, dvy) for dvx in [-1, 0, 1] for dvy in [-1, 0, 1]]

class ImpossibleRaceError(Exception): pass

def read_input(line_source=raw_input):
    # We don't use the target.
    target = int(line_source())

    width, height = map(int, line_source().split())
    input_grid = [line_source() for _ in xrange(height)]

    start = None
    for i in xrange(height):
        for j in xrange(width):
            if input_grid[i][j] == 'S':
                start = i, j
                break
        if start is not None:
            break

    walls = [[cell == '#' for cell in row] for row in input_grid]
    goals = [[cell == '*' for cell in row] for row in input_grid]

    return start, walls, goals

def default_bfs_stop_threshold(walls, goals):
    num_not_wall = sum(sum(map(operator.not_, row)) for row in walls)
    num_goals = sum(sum(row) for row in goals)
    return num_goals * num_not_wall

def bfs(start, walls, goals, stop_threshold=None):
    if stop_threshold is None:
        stop_threshold = default_bfs_stop_threshold(walls, goals)

    # State representation is (x, y, vx, vy)
    x, y = start
    initial_state = (x, y, 0, 0)
    frontier = {initial_state}
    # Visited set is tracked by a map from each state to the last move taken
    # before reaching that state.
    visited = {initial_state: None}

    while len(frontier) < stop_threshold:
        if not frontier:
            raise ImpossibleRaceError

        new_frontier = set()
        for x, y, vx, vy in frontier:
            for dvx, dvy in acceleration_options:
                new_vx, new_vy = vx+dvx, vy+dvy
                new_x, new_y = x+new_vx, y+new_vy
                new_state = (new_x, new_y, new_vx, new_vy)

                if not (0 <= new_x < len(walls) and 0 <= new_y < len(walls[0])):
                    continue
                if walls[new_x][new_y]:
                    continue
                if new_state in visited:
                    continue

                new_frontier.add(new_state)
                visited[new_state] = dvx, dvy

                if goals[new_x][new_y]:
                    return construct_path_from_bfs(new_state, visited)
        frontier = new_frontier

def construct_path_from_bfs(goal_state, best_moves):
    reversed_path = []
    current_state = goal_state
    while best_moves[current_state] is not None:
        move = best_moves[current_state]
        reversed_path.append(move)

        x, y, vx, vy = current_state
        dvx, dvy = move
        old_x, old_y = x-vx, y-vy # not old_vx or old_vy
        old_vx, old_vy = vx-dvx, vy-dvy
        current_state = (old_x, old_y, old_vx, old_vy)
    return reversed_path[::-1]

def main():
    t = time.time()

    start, walls, goals = read_input()
    path = bfs(start, walls, goals, float('inf'))
    for dvx, dvy in path:
        # I wrote the whole program with x pointing down and y pointing right.
        # Whoops. Gotta flip things for the output.
        print dvy, dvx

if __name__ == '__main__':
    main()

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.

# Bidirectional search.
# Future directions: A*.

import operator
import time

acceleration_options = [(dvx, dvy) for dvx in [-1, 0, 1] for dvy in [-1, 0, 1]]

class ImpossibleRaceError(Exception): pass

def read_input(line_source=raw_input):
    # We don't use the target.
    target = int(line_source())

    width, height = map(int, line_source().split())
    input_grid = [line_source() for _ in xrange(height)]

    start = None
    for i in xrange(height):
        for j in xrange(width):
            if input_grid[i][j] == 'S':
                start = i, j
                break
        if start is not None:
            break

    walls = [[cell == '#' for cell in row] for row in input_grid]
    goals = [[cell == '*' for cell in row] for row in input_grid]

    return start, walls, goals

def bfs_to_bidi_threshold(walls, goals):
    num_not_wall = sum(sum(map(operator.not_, row)) for row in walls)
    num_goals = sum(sum(row) for row in goals)
    return num_goals * (num_not_wall - num_goals)

class GridBasedGoalContainer(object):
    '''Supports testing whether a state is a goal state with `in`.

    Does not perform bounds checking.'''
    def __init__(self, goal_grid):
        self.goal_grid = goal_grid
    def __contains__(self, state):
        x, y, vx, vy = state
        return self.goal_grid[x][y]

def forward_step(state, acceleration):
    x, y, vx, vy = state
    dvx, dvy = acceleration

    new_vx, new_vy = vx+dvx, vy+dvy
    new_x, new_y = x+new_vx, y+new_vy

    return (new_x, new_y, new_vx, new_vy)

def backward_step(state, acceleration):
    x, y, vx, vy = state
    dvx, dvy = acceleration

    old_x, old_y = x-vx, y-vy
    old_vx, old_vy = vx-dvx, vy-dvy

    return (old_x, old_y, old_vx, old_vy)

def bfs(start, walls, goals):
    x, y = start
    initial_state = (x, y, 0, 0)
    initial_frontier = {initial_state}
    visited = {initial_state: None}

    goal_state, frontier, visited = general_bfs(
        frontier=initial_frontier,
        visited=visited,
        walls=walls,
        goalcontainer=GridBasedGoalContainer(goals),
        stop_threshold=float('inf'),
        step_function=forward_step
    )

    return construct_path_from_bfs(goal_state, visited)

def general_bfs(
        frontier,
        visited,
        walls,
        goalcontainer,
        stop_threshold,
        step_function):

    while len(frontier) <= stop_threshold:
        if not frontier:
            raise ImpossibleRaceError

        new_frontier = set()
        for state in frontier:
            for accel in acceleration_options:
                new_state = new_x, new_y, new_vx, new_vy = \
                        step_function(state, accel)

                if not (0 <= new_x < len(walls) and 0 <= new_y < len(walls[0])):
                    continue
                if walls[new_x][new_y]:
                    continue
                if new_state in visited:
                    continue

                new_frontier.add(new_state)
                visited[new_state] = accel

                if new_state in goalcontainer:
                    return new_state, frontier, visited
        frontier = new_frontier
    return None, frontier, visited

def max_velocity_component(n):
    # It takes a distance of at least 0.5*v*(v+1) to achieve a velocity of
    # v in the x or y direction. That means the map has to be at least
    # 1 + 0.5*v*(v+1) rows or columns long to accomodate such a velocity.
    # Solving for v, we get a velocity cap as follows.
    return int((2*n-1.75)**0.5 - 0.5)

def solver(
        start,
        walls,
        goals,
        mode='bidi'):

    x, y = start
    initial_state = (x, y, 0, 0)
    initial_frontier = {initial_state}
    visited = {initial_state: None}
    if mode == 'bidi':
        stop_threshold = bfs_to_bidi_threshold(walls, goals)
    elif mode == 'bfs':
        stop_threshold = float('inf')
    else:
        raise ValueError('Unsupported search mode: {}'.format(mode))

    goal_state, frontier, visited = general_bfs(
        frontier=initial_frontier,
        visited=visited,
        walls=walls,
        goalcontainer=GridBasedGoalContainer(goals),
        stop_threshold=stop_threshold,
        step_function=forward_step
    )

    if goal_state is not None:
        return construct_path_from_bfs(goal_state, visited)

    # Switching to bidirectional search.

    not_walls_or_goals = []
    goal_list = []
    for x in xrange(len(walls)):
        for y in xrange(len(walls[0])):
            if not walls[x][y] and not goals[x][y]:
                not_walls_or_goals.append((x, y))
            if goals[x][y]:
                goal_list.append((x, y))
    max_vx = max_velocity_component(len(walls))
    max_vy = max_velocity_component(len(walls[0]))
    reverse_visited = {(goal_x, goal_y, goal_x-prev_x, goal_y-prev_y): None
                        for goal_x, goal_y in goal_list
                        for prev_x, prev_y in not_walls_or_goals
                        if abs(goal_x-prev_x) <= max_vx
                        and abs(goal_y - prev_y) <= max_vy}
    reverse_frontier = set(reverse_visited)
    while goal_state is None:
        goal_state, reverse_frontier, reverse_visited = general_bfs(
            frontier=reverse_frontier,
            visited=reverse_visited,
            walls=walls,
            goalcontainer=frontier,
            stop_threshold=len(frontier),
            step_function=backward_step
        )
        if goal_state is not None:
            break
        goal_state, frontier, visited = general_bfs(
            frontier=frontier,
            visited=visited,
            walls=walls,
            goalcontainer=reverse_frontier,
            stop_threshold=len(reverse_frontier),
            step_function=forward_step
        )
    forward_path = construct_path_from_bfs(goal_state, visited)
    backward_path = construct_path_from_bfs(goal_state,
                                            reverse_visited,
                                            step_function=forward_step)
    return forward_path + backward_path[::-1]

def construct_path_from_bfs(goal_state,
                            best_moves,
                            step_function=backward_step):
    reversed_path = []
    current_state = goal_state
    while best_moves[current_state] is not None:
        move = best_moves[current_state]
        reversed_path.append(move)
        current_state = step_function(current_state, move)
    return reversed_path[::-1]

def main():
    start, walls, goals = read_input()
    t = time.time()
    path = solver(start, walls, goals)
    for dvx, dvy in path:
        # I wrote the whole program with x pointing down and y pointing right.
        # Whoops. Gotta flip things for the output.
        print dvy, dvx

if __name__ == '__main__':
    main()
user2357112 es compatible con Monica
fuente
Esto a veces falla en los casos 12 y 13. No sé por qué ya que los mensajes de error son algo ... hostiles
Ray
@ Ray También recibo mensajes de error, pero siempre obtengo el resultado de todos modos. Creo que podría ser algo en mi controlador, porque parece que el controlador intenta matar el proceso del corredor aunque ya está terminado.
Martin Ender
@ m.buettner Encontré la razón, agregue -s, entonces estará bien.
Ray
@ Ray Oh, sí, estoy haciendo eso. Todavía recibo un error en las pistas 13 y 14 cuando el controlador está tratando de matar el proceso, aunque el resultado ya está allí. Supongo que debería investigar eso, pero no afecta la puntuación, así que no me molesté todavía.
Martin Ender
Desafortunadamente, tuve que agregar otra regla. La memoria parece ser más limitante que el tiempo en este desafío, por lo que tuve que establecer un límite difícil de consumo de memoria. Cualquier ejecución en la que su corredor use más de 1 GB de memoria se anulará con el mismo efecto que exceda el límite de tiempo. Para el conjunto actual de pistas, su puntuación no se ha visto afectada por este cambio. (Creo que alcanzará ese límite en los desempates n = 400). Avíseme si aplica alguna optimización, para que pueda volver a ejecutar las pruebas.
Martin Ender
3

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.

from collections import namedtuple, deque
import itertools

Field = namedtuple('Map', 'n m grids')

class Grid:
    WALL = '#'
    EMPTY = '.'
    START = 'S'
    END = '*'

def read_nums():
    return list(map(int, input().split()))

def read_field():
    m, n = read_nums()
    return Field(n, m, [input() for i in range(n)])

def find_start_pos(field):
    return next((i, j)
        for i in range(field.n) for j in range(field.m)
        if field.grids[i][j] == Grid.START)

def can_go(field, i, j):
    return 0 <= i < field.n and 0 <= j < field.m and field.grids[i][j] != Grid.WALL

def trace_path(start, end, prev):
    if end == start:
        return
    end, step = prev[end]
    yield from trace_path(start, end, prev)
    yield step

def solve(max_turns, field, time):
    i0, j0 = find_start_pos(field)
    p0 = i0, j0, 0, 0
    prev = {}
    que = deque([p0])
    directions = list(itertools.product((-1, 0, 1), (-1, 0, 1)))

    while que:
        p = i, j, vi, vj = que.popleft()
        for dvi, dvj in directions:
            vi1, vj1 = vi + dvi, vj + dvj
            i1, j1 = i + vi1, j + vj1
            if not can_go(field, i1, j1):
                continue
            p1 = i1, j1, vi1, vj1
            if p1 in prev:
                continue
            que.append(p1)
            prev[p1] = p, (dvi, dvj)
            if field.grids[i1][j1] == Grid.END:
                return trace_path(p0, p1, prev)
    return []

def main():
    for dvy, dvx in solve(int(input()), read_field(), float(input())):
        print(dvx, dvy)

main()

# Resultados

± % time ruby controller.rb benchmark.txt python ../mybfs.py                                                                                                                                                                             !9349
["benchmark.txt", "python", "../mybfs.py"]

Running 'python ../mybfs.py' against benchmark.txt

 No.       Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1       37 x 1        36   0.22222   Racer reached goal at ( 36, 0) in 8 turns.
  2       38 x 1        37   0.24324   Racer reached goal at ( 37, 0) in 9 turns.
  3       33 x 1        32   0.25000   Racer reached goal at ( 32, 0) in 8 turns.
  4       10 x 10       10   0.40000   Racer reached goal at ( 7, 7) in 4 turns.
  5        9 x 6         8   0.37500   Racer reached goal at ( 6, 0) in 3 turns.
  6       15 x 7        16   0.37500   Racer reached goal at ( 12, 4) in 6 turns.
  7       17 x 8        16   0.31250   Racer reached goal at ( 14, 0) in 5 turns.
  8       19 x 13       18   0.27778   Racer reached goal at ( 0, 11) in 5 turns.
  9       60 x 10      107   0.14953   Racer reached goal at ( 0, 6) in 16 turns.
 10       31 x 31      106   0.23585   Racer reached goal at ( 27, 0) in 25 turns.
 11       31 x 31      106   0.24528   Racer reached goal at ( 15, 15) in 26 turns.
 12       50 x 20       50   0.24000   Racer reached goal at ( 49, 10) in 12 turns.
 13      100 x 100    2600   0.01385   Racer reached goal at ( 50, 0) in 36 turns.
 14       79 x 63      242   0.24380   Racer reached goal at ( 3, 42) in 59 turns.
 15       26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16       17 x 1        19   0.52632   Racer reached goal at ( 16, 0) in 10 turns.
 17       50 x 1        55   0.34545   Racer reached goal at ( 23, 0) in 19 turns.
 18       10 x 7        23   0.34783   Racer reached goal at ( 1, 3) in 8 turns.
 19       55 x 55       45   0.17778   Racer reached goal at ( 50, 26) in 8 turns.
 20      101 x 100     100   0.14000   Racer reached goal at ( 99, 99) in 14 turns.
 21   100000 x 1         1   1.00000   Racer reached goal at ( 0, 0) in 1 turns.
 22       50 x 50      200   0.05500   Racer reached goal at ( 47, 46) in 11 turns.
-------------------------------------------------------------------------------------
TOTAL SCORE:                 6.49643

ruby controller.rb benchmark.txt python ../mybfs.py  3.06s user 0.06s system 99% cpu 3.146 total
Rayo
fuente
Sí, según el comentario del usuario2357112, hay un error en la prevención del ciclo de nneonneo. Hasta donde sé, la velocidad está limitada por O(√n)lo que haría su implementación O(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.
Martin Ender
Por cierto, ¿estás planeando agregar otro caso de prueba?
Martin Ender
@ m.buettner No, no tengo una comprensión lo suficientemente buena para este juego. Entonces mi caso de prueba no será interesante.
Ray
Desafortunadamente, tuve que agregar otra regla. La memoria parece ser más limitante que el tiempo en este desafío, por lo que tuve que establecer un límite difícil de consumo de memoria. Cualquier ejecución en la que su corredor use más de 1 GB de memoria se anulará con el mismo efecto que exceda el límite de tiempo. Con esta regla, su envío es el primero en superar ese límite en un desempate de tamaño 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.
Martin Ender
Avíseme si aplica alguna optimización, para que pueda volver a ejecutar las pruebas.
Martin Ender
1

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:

# Parse initial input
target = gets.to_i
size = gets.split.map(&:to_i)
track = []
size[1].times do
    track.push gets
end
time_budget = gets.to_f

# Find start position
start_y = track.find_index { |row| row['S'] }
start_x = track[start_y].index 'S'

position = [start_x, start_y]
velocity = [0, 0]

while true
    x = rand(3) - 1
    y = rand(3) - 1
    puts [x,y].join ' '
    $stdout.flush

    first_line = gets
    break if !first_line || first_line.chomp.empty?

    position = first_line.split.map(&:to_i)
    velocity = gets.split.map(&:to_i)
    time_budget = gets.to_f
end

Ejecútalo con

ruby controller.rb benchmark.txt ruby randomracer.rb
Martin Ender
fuente
1

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.

import java.util.Scanner;
import java.util.Random;
import java.util.ArrayList;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;

public class VectorRacing   {
    private static Scanner in = new Scanner(System.in);
    private static Random rand = new Random();
    private static Track track;
    private static Racer racer;
    private static int target;
    private static double time;
    public static void main(String[] args)  {
        init();
        main_loop();
    }
    private static void main_loop() {
        Scanner linescan;
        String line;
        int count = 0,
            x, y, u, v;

        while(!racer.lost() && !racer.won() && count < target)  {
            Direction d = racer.think();
            racer.move(d);
            count++;
            System.out.println(d);

            line = in.nextLine();
            if(line.equals("")) {
                break;
            }
            linescan = new Scanner(line);
            x = linescan.nextInt();
            y = linescan.nextInt();
            linescan = new Scanner(in.nextLine());
            u = linescan.nextInt();
            v = linescan.nextInt();
            time = Double.parseDouble(in.nextLine());

            assert x == racer.location.x;
            assert y == racer.location.y;
            assert u == racer.direction.x;
            assert v == racer.direction.y;
        }
    }
    private static void init()  {
        target = Integer.parseInt(in.nextLine());
        int width = in.nextInt();
        int height = Integer.parseInt(in.nextLine().trim());
        String[] ascii = new String[height];
        for(int i = 0; i < height; i++) {
            ascii[i] = in.nextLine();
        }
        time = Double.parseDouble(in.nextLine());
        track = new Track(width, height, ascii);
        for(int y = 0; y < ascii.length; y++)   {
            int x = ascii[y].indexOf("S");
            if( x != -1)    {
                racer = new RandomRacer(track, new Location(x, y));
                break;
            }
        }
    }

    public static class RandomRacer extends Racer   {
        public RandomRacer(Track t, Location l) {
            super(t, l);
        }
        public Direction think()    {
            ArrayList<Pair<Location, Direction> > possible = this.getLocationsCanMoveTo();
            if(possible.size() == 0)    {
                return Direction.NONE;
            }
            Pair<Location, Direction> ret = null;
            do  {
                ret = possible.get(rand.nextInt(possible.size()));
            }   while(possible.size() != 1 && ret.a.equals(this.location));
            return ret.b;
        }
    }

    // Base things
    public enum Direction   {
        NORTH("0 -1"), SOUTH("0 1"), EAST("1 0"), WEST("-1 0"), NONE("0 0"),
        NORTH_EAST("1 -1"), NORTH_WEST("-1 -1"), SOUTH_EAST("1 1"), SOUTH_WEST("-1 1");

        private final String d;
        private Direction(String d) {this.d = d;}
        public String toString()    {return d;}
    }
    public enum Cell    {
        WALL('#'), GOAL('*'), ROAD('.'), OUT_OF_BOUNDS('?');

        private final char c;
        private Cell(char c)    {this.c = c;}
        public String toString()    {return "" + c;}
    }

    public static class Track   {
        private Cell[][] track;
        private int target;
        private double time;
        public Track(int width, int height, String[] ascii) {
            this.track = new Cell[width][height];
            for(int y = 0; y < height; y++) {
                for(int x = 0; x < width; x++)  {
                    switch(ascii[y].charAt(x))  {
                        case '#':   this.track[x][y] = Cell.WALL; break;
                        case '*':   this.track[x][y] = Cell.GOAL; break;
                        case '.':
                        case 'S':   this.track[x][y] = Cell.ROAD; break;
                        default:    System.exit(-1);
                    }
                }
            }
        }
        public Cell atLocation(Location loc)    {
            if(loc.x < 0 || loc.x >= track.length || loc.y < 0 || loc.y >= track[0].length) return Cell.OUT_OF_BOUNDS;
            return track[loc.x][loc.y];
        }

        public String toString()    {
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            PrintStream ps = new PrintStream(bos);
            for(int y = 0; y < track[0].length; y++)    {
                for(int x = 0; x < track.length; x++)   {
                    ps.append(track[x][y].toString());
                }
                ps.append('\n');
            }
            String ret = bos.toString();
            ps.close();
            return ret;
        }
    }

    public static abstract class Racer  {
        protected Velocity tdir;
        protected Location tloc;
        protected Track track;
        public Velocity direction;
        public Location location;

        public Racer(Track track, Location start)   {
            this.track = track;
            direction = new Velocity(0, 0);
            location = start;
        }
        public boolean canMove() throws GoHereDammitException {return canMove(Direction.NONE);}
        public boolean canMove(Direction d) throws GoHereDammitException    {
            tdir = new Velocity(direction);
            tloc = new Location(location);
            tdir.add(d);
            tloc.move(tdir);
            Cell at = track.atLocation(tloc);
            if(at == Cell.GOAL) {
                throw new GoHereDammitException();
            }
            return at == Cell.ROAD;
        }
        public ArrayList<Pair<Location, Direction> > getLocationsCanMoveTo()    {
            ArrayList<Pair<Location, Direction> > ret = new ArrayList<Pair<Location, Direction> >(9);
            for(Direction d: Direction.values())    {
                try {
                    if(this.canMove(d)) {
                        ret.add(new Pair<Location, Direction>(tloc, d));
                    }
                }   catch(GoHereDammitException e)  {
                    ret.clear();
                    ret.add(new Pair<Location, Direction>(tloc, d));
                    return ret;
                }
            }
            return ret;
        }
        public void move()  {move(Direction.NONE);}
        public void move(Direction d)   {
            direction.add(d);
            location.move(direction);
        }
        public boolean won()    {
            return track.atLocation(location) == Cell.GOAL;
        }
        public boolean lost()   {
            return track.atLocation(location) == Cell.WALL || track.atLocation(location) == Cell.OUT_OF_BOUNDS;
        }
        public String toString()    {
            return location + ", " + direction;
        }
        public abstract Direction think();

        public class GoHereDammitException extends Exception    {
            public GoHereDammitException()  {}
        }
    }

    public static class Location extends Point  {
        public Location(int x, int y)   {
            super(x, y);
        }
        public Location(Location l) {
            super(l);
        }
        public void move(Velocity d)    {
            this.x += d.x;
            this.y += d.y;
        }
    }

    public static class Velocity extends Point  {
        public Velocity(int x, int y)   {
            super(x, y);
        }
        public Velocity(Velocity v) {
            super(v);
        }
        public void add(Direction d)    {
            if(d == Direction.NONE) return;
            if(d == Direction.NORTH || d == Direction.NORTH_EAST || d == Direction.NORTH_WEST)  this.y--;
            if(d == Direction.SOUTH || d == Direction.SOUTH_EAST || d == Direction.SOUTH_WEST)  this.y++;
            if(d == Direction.EAST || d == Direction.NORTH_EAST || d == Direction.SOUTH_EAST)   this.x++;
            if(d == Direction.WEST || d == Direction.NORTH_WEST || d == Direction.SOUTH_WEST)   this.x--;
        }
    }

    public static class Point   {
        protected int x, y;
        protected Point(int x, int y)   {
            this.x = x;
            this.y = y;
        }
        protected Point(Point c)    {
            this.x = c.x;
            this.y = c.y;
        }
        public int getX()   {return x;}
        public int getY()   {return y;}
        public String toString()    {return "(" + x + ", " + y + ")";}
        public boolean equals(Point p)  {
            return this.x == p.x && this.y == p.y;
        }
    }

    public static class Pair<T, U>  {
        public T a;
        public U b;
        public Pair(T t, U u)   {
            a=t;b=u;
        }
    }
}

Los resultados (el mejor caso que he visto)

Running 'java VectorRacing' against ruby-runner/benchmark.txt

 No.    Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1    37 x 1        36   0.38889   Racer reached goal at ( 36, 0) in 14 turns.
  2    38 x 1        37   0.54054   Racer reached goal at ( 37, 0) in 20 turns.
  3    33 x 1        32   0.62500   Racer reached goal at ( 32, 0) in 20 turns.
  4    10 x 10       10   0.40000   Racer reached goal at ( 9, 8) in 4 turns.
  5     9 x 6         8   0.75000   Racer reached goal at ( 6, 2) in 6 turns.
  6    15 x 7        16   2.00000   Racer did not reach the goal within 16 turns.
  7    17 x 8        16   2.00000   Racer hit a wall at position ( 8, 2).
  8    19 x 13       18   0.44444   Racer reached goal at ( 16, 2) in 8 turns.
  9    60 x 10      107   0.65421   Racer reached goal at ( 0, 6) in 70 turns.
 10    31 x 31      106   2.00000   Racer hit a wall at position ( 25, 9).
 11    31 x 31      106   2.00000   Racer hit a wall at position ( 8, 1).
 12    50 x 20       50   2.00000   Racer hit a wall at position ( 27, 14).
 13   100 x 100    2600   2.00000   Racer went out of bounds at position ( 105, 99).
 14    79 x 63      242   2.00000   Racer went out of bounds at position (-2, 26).
 15    26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16    17 x 1        19   2.00000   Racer went out of bounds at position (-2, 0).
 17    50 x 1        55   2.00000   Racer went out of bounds at position ( 53, 0).
 18    10 x 7        23   2.00000   Racer went out of bounds at position ( 10, 2).
 19    55 x 55       45   0.33333   Racer reached goal at ( 4, 49) in 15 turns.
 20    50 x 50      200   2.00000   Racer hit a wall at position ( 14, 7).
-------------------------------------------------------------------------------------
TOTAL SCORE:             26.45641
seudónimo117
fuente
Sí, lo ejecuté, aunque tuve que ejecutarlo desde el directorio donde está el .classarchivo 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.
Martin Ender
Ah, también tengo que ejecutarlo desde el otro directorio. Para aquellos que no están familiarizados con Java en la línea de comando:java -cp path/to/class/file VectorRacing
Martin Ender
Ah, sí, hice un montón de clases (13, para ser exactos). Siempre estaba ejecutando su script desde mi directorio de clases, por lo que en realidad no lo probé. Puedo hacer un caso de prueba, pero creo que primero intentaré hacer un piloto que no sea aleatorio.
seudónimo117
Seguro. Si lo hace, agréguelo como una respuesta separada. (Y siéntase libre de agregar un caso de prueba con cada uno de ellos.)
Martin Ender
Desafortunadamente, tuve que agregar otra regla. La memoria parece ser más limitante que el tiempo en este desafío, por lo que tuve que establecer un límite difícil de consumo de memoria. Cualquier ejecución en la que su corredor use más de 1 GB de memoria se anulará con el mismo efecto que exceda el límite de tiempo. Para el conjunto actual de pistas, su puntuación no se ha visto afectada por este cambio (y probablemente nunca lo será).
Martin Ender