L'utilisateur CarpetPython a publié une nouvelle approche de ce problème qui met beaucoup plus l'accent sur les solutions heuristiques, en raison d'un espace de recherche accru. Personnellement, je pense que ce défi est beaucoup plus gentil que le mien, alors pensez à l'essayer!

Vector racing est un jeu addictif qui peut être joué avec un stylo et une feuille de papier à la règle. Vous tracez un circuit arbitraire sur le papier, définissez un début et une fin, puis vous dirigez votre voiture de la taille d'un point par tour. Arrivez à la fin le plus vite possible, mais faites attention de ne pas vous retrouver dans un mur!

La piste

• La carte est une grille à deux dimensions, où chaque cellule a des coordonnées entières.
• Vous vous déplacez sur les cellules de la grille.
• Chaque cellule de la grille fait partie de la piste ou constitue un mur.
• Exactement une cellule de piste est la coordonnée de départ.
• Au moins une cellule de piste est désignée comme objectif. Atterrir sur l'un de ceux-ci complète la course. Les cellules à objectifs multiples ne sont pas nécessairement connectées.

Diriger la voiture

Votre voiture démarre à une coordonnée donnée et avec un vecteur vitesse (0, 0). À chaque tour, vous pouvez ajuster chaque composante de la vitesse ±1ou la laisser telle quelle. Ensuite, le vecteur de vitesse résultant est ajouté à la position de votre voiture.

Une image peut aider! Le cercle rouge était votre position le dernier tour. Le cercle bleu est votre position actuelle. Votre vitesse est le vecteur du cercle rouge au cercle bleu. À ce tour, en fonction de la manière dont vous ajustez votre vélocité, vous pouvez passer à n’importe quel cercle vert.

Si vous atterrissez dans un mur, vous perdez immédiatement.

Ta tâche

Vous l'avez deviné: écrivez un programme qui, avec une piste de course en entrée, dirige la voiture vers l'une des cellules de but en aussi peu de virages que possible. Votre solution doit pouvoir traiter raisonnablement bien des pistes arbitraires et ne pas être spécifiquement optimisée par rapport aux scénarios de test fournis.

Contribution

Lorsque votre programme est appelé, lisez stdin :

target
n m
[ASCII representation of an n x m racetrack]
time

targetest le nombre maximum de tours que vous pouvez effectuer pour terminer la piste, et timevotre budget temps total pour la piste, en secondes (pas nécessairement un nombre entier). Voir ci-dessous pour plus de détails sur le timing.

Pour la piste délimitée par une nouvelle ligne, les caractères suivants sont utilisés:

• # - mur
• S- le départ
• *- un but
• . - toutes les autres cellules de voie (c.-à-d. Route)

Toutes les cellules en dehors de la n x mgrille fournie sont supposées être des murs.

L'origine des coordonnées est dans le coin supérieur gauche.

Voici un exemple simple:

8
4.0
9 6
###...***
###...***
###...***
......###
S.....###
......###

En utilisant l'indexation basée sur 0, la coordonnée de départ serait (0,4).

Après chaque déménagement, vous recevrez d'autres informations:

x y
u v
time

Où x, y, u, vsont tous les entiers à base 0. (x,y)est votre position actuelle et (u,v)votre vitesse actuelle. Notez que x+uet / ou y+vpourrait être hors limites.

timeest ce qui reste de votre budget temps, en secondes. N'hésitez pas à l'ignorer. Ceci ne concerne que les participants qui souhaitent réellement mener à bien leur mise en œuvre.

Lorsque le jeu est terminé (parce que vous avez atterri dans un mur, que vous êtes sorti des limites, que vous avez dépassé les targettours, que vous n’avez plus atteint le but ou que vous avez atteint le but), vous recevez une ligne vide.

Sortie

Pour chaque tour, écrivez sur stdout :

Δu Δv

où Δuet Δvsont chacun l' un des -1, 0, 1. Ceci sera ajouté (u,v)pour déterminer votre nouvelle position. Juste pour clarifier, les instructions sont les suivantes

(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 0, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)

Une solution optimale pour l'exemple ci-dessus serait

1 0
1 -1
1 0

Notez que le contrôleur ne se lie pas à stderr , vous êtes donc libre de l’utiliser pour tout type de sortie de débogage dont vous pourriez avoir besoin lors du développement de votre bot. Veuillez supprimer / commenter tout résultat de ce type dans votre code soumis, cependant.

Votre bot peut prendre une demi-seconde pour répondre à chaque tour. Pour les tours qui prennent plus de temps, vous aurez un budget de temps (par piste) de target/2secondes. Chaque fois qu'un tour prend plus d'une demi-seconde, le temps supplémentaire sera déduit de votre budget-temps. Lorsque votre budget temps est à zéro, la course en cours sera annulée.

Nouveau: pour des raisons pratiques, je dois définir une limite de mémoire (car la mémoire semble être plus contraignante que le temps pour des tailles de piste raisonnables). Par conséquent, je devrai abandonner tout test où le coureur utilise plus de 1 Go de mémoire, mesurée par Process Explorer en octets privés .

Notation

Il y a un repère de 20 pistes. Pour chaque piste:

• Si vous terminez la piste, votre score est le nombre de coups nécessaires pour atteindre une cellule de but divisée partarget .
• Si vous manquez de temps / mémoire ou si vous n'atteignez pas l'objectif avant la fin des targettours ou si vous atterrissez dans un mur / hors des limites à tout moment, votre score est 2.
• Si votre programme n’est pas déterministe, votre score correspond à la moyenne de 10 passages sur cette piste (veuillez l'indiquer dans votre réponse).

Votre score global est la somme des scores de chaque piste. Le score le plus bas gagne!

En outre, chaque participant peut (et est fortement encouragé à) fournir une piste de référence supplémentaire , qui sera ajoutée à la liste officielle. Les réponses précédentes seront réévaluées, y compris cette nouvelle piste. Cela permet de s’assurer qu’aucune solution n’est trop adaptée aux cas de test existants et de prendre en compte les cas intéressants que j’aurais peut-être manqués (mais que vous pourriez remarquer).

Rupture de cravate

Maintenant qu'il existe déjà une solution optimale, ce sera probablement le facteur principal pour les scores des participants.

S'il y a une égalité (en raison de plusieurs réponses résolvant toutes les pistes de manière optimale ou autre), j'ajouterai des cas de test supplémentaires (plus grands) pour rompre l'égalité. Pour éviter tout préjugé humain lors de la création de ces liens, ceux-ci seront générés de manière fixe:

• Je vais augmenter la longueur des côtés npar 10rapport à la dernière piste générée de cette façon. (Je peux sauter des tailles si elles ne brisent pas la cravate.)
• La base est ce vectoriel
• Celui-ci sera pixellisé à la résolution souhaitée à l'aide de cet extrait de Mathematica .
• Le début est dans le coin en haut à gauche. En particulier, ce sera la cellule la plus à gauche de la rangée la plus haute de cette extrémité de la piste.
• Le but est dans le coin en bas à droite. En particulier, ce sera la cellule la plus à droite de la rangée la plus basse de cette extrémité de la piste.
• La targetvolonté 4*n.

La piste finale du benchmark initial était déjà générée comme ceci, avec n = 50.

Le controlle

Le programme qui teste les soumissions est écrit en Ruby et se trouve sur GitHub avec le fichier de référence que je vais utiliser. Il y a aussi un exemple de bot appelé randomracer.rbici, qui choisit simplement des mouvements aléatoires. Vous pouvez utiliser sa structure de base comme point de départ pour que votre bot voie comment fonctionne la communication.

Vous pouvez exécuter votre propre bot contre un fichier de piste de votre choix, comme suit:

ruby controller.rb track_file_name command to run your racer

par exemple

ruby controller.rb benchmark.txt ruby randomracer.rb

Le référentiel contient également deux classes Point2Det Track. Si votre soumission est rédigée en Ruby, n'hésitez pas à les réutiliser pour votre commodité.

Commutateurs de ligne de commande

Vous pouvez ajouter des commutateurs de ligne de commande -v, -s, -tavant le nom du fichier de l'indice de référence. Si vous souhaitez utiliser plusieurs commutateurs, vous pouvez également utiliser, par exemple -vs. Voilà ce qu'ils font:

-v (verbose): utilisez-le pour produire un peu plus de résultats de débogage à partir du contrôleur.

-s (silencieux): Si vous préférez garder vous-même votre position et votre vélocité sans vous soucier du budget temps, vous pouvez désactiver ces trois lignes de sortie à chaque tour (envoyé à votre soumission) avec ce drapeau.

-t(pistes): vous permet de sélectionner des pistes individuelles à tester. Par exemple -t "1,2,5..8,15", les pistes 1, 2, 5, 6, 7, 8 et 15 ne seraient testées que. Merci beaucoup à Ventero pour cette fonctionnalité et l’analyseur d’options.

Votre soumission

En résumé, veuillez inclure les éléments suivants dans votre réponse:

• Ton score.
• Si vous utilisez un caractère aléatoire, indiquez-le afin que je puisse moyenner votre score sur plusieurs analyses.
• Le code pour votre soumission.
• Emplacement d'un compilateur ou interprète gratuit correspondant à la langue de votre choix et s'exécutant sur un ordinateur Windows 8.
• Instructions de compilation si nécessaire.
• Une chaîne de ligne de commande Windows pour exécuter votre soumission.
• Que votre soumission nécessite le -sdrapeau ou non.
• (facultatif) Une nouvelle piste résoluble qui sera ajoutée à l’indice de référence. Je vais déterminer un raisonnable targetpour votre piste manuellement. Lorsque la piste est ajoutée au point de référence, je la modifie dans votre réponse. Je me réserve le droit de vous demander une autre piste (juste au cas où vous ajouteriez une piste disproportionnée, incluez des œuvres ASCII obscènes dans la piste, etc.). Lorsque j'ajoute le scénario de test à l'ensemble de références, je remplace la piste de votre réponse par un lien vers la piste dans le fichier de références afin de réduire l'encombrement de ce message.

Comme vous pouvez le constater, je testerai toutes les soumissions sur un ordinateur Windows 8. S'il n'y a absolument aucun moyen de faire fonctionner votre soumission sous Windows, je peux également essayer sur une machine virtuelle Ubuntu. Cela sera toutefois beaucoup plus lent. Par conséquent, si vous souhaitez respecter le délai imparti, assurez-vous que votre programme fonctionne sous Windows.

Que le meilleur pilote émerge vectoriel!

Mais je veux jouer!

Si vous voulez essayer le jeu vous-même pour en avoir une meilleure idée, il existe cette implémentation . Les règles utilisées ici sont légèrement plus sophistiquées, mais elles sont assez similaires pour être utiles, je pense.

Classement

Dernière mise à jour: 01/09/2014, 21:29 UTC Nombre de
pistes dans le repère: 25
Taille des égalités: 290, 440

1. 6.86688 - Kuroi Neko
2. 8.73108 - user2357112 - 2e soumission
3. 9.86627 - nneonneo
4. 10.66109 - user2357112 - 1ère soumission
5. 12.49643 - Ray
6. 40.0759 - pseudonyme117 (probabiliste)

Résultats détaillés du test . (Les scores pour les soumissions probabilistes ont été déterminés séparément.)

C ++ 11 - 6.66109

Encore une autre implémentation de recherche étendue et optimisée.

Il doit être exécuté avec l' option -s .
Son entrée n'est pas du tout assainie, de sorte que de mauvaises pistes peuvent le transformer en citrouille.

Je l'ai testé avec Microsoft Visual C ++ 2013, version compilée avec l'indicateur par défaut / O2 (optimiser pour la vitesse).
Construit bien avec g ++ et Microsoft IDE.
Mon allocateur de mémoire barebone est un morceau de merde, alors ne vous attendez pas à ce qu'il fonctionne avec d'autres implémentations 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;
}

Résultats

 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

Les performances

Ce langage C ++ merdique a le chic pour vous faire sauter à travers des cerceaux juste pour déplacer une allumette. Cependant, vous pouvez le forcer à produire un code relativement rapide et économe en mémoire.

Hachage

Ici, la clé est de fournir une bonne table de hachage pour les nœuds. C'est de loin le facteur dominant pour la vitesse d'exécution.
Deux implémentations de unordered_set(GNU et Microsoft) ont abouti à une différence de vitesse d'exécution de 30% (en faveur de GNU, yay!).

La différence n’est pas vraiment surprenante avec les camions chargés de code cachés derrière unordered_set.

Par curiosité, j’ai fait quelques statistiques sur l’état final de la table de hachage.
Les deux algorithmes se retrouvent presque avec le même rapport
compartiment / éléments, mais la répartition varie: pour le départage 290x290, GNU obtient une moyenne de 1,5 élément par compartiment non vide, alors que Microsoft se situe à 5,8 (!).

On dirait que ma fonction de hachage n’est pas très bien randomisée par Microsoft ... Je me demande si les gars de Redmond ont vraiment comparé leur STL, ou si mon cas d’utilisation privilégie simplement l’implémentation de GNU ...

Bien sûr, ma fonction de hachage est loin d'être optimale. J'aurais pu utiliser le mélange d'entiers habituel basé sur plusieurs décalages / impulsions, mais une fonction efficace en termes de hachage prend du temps à calculer.

Il semble que le nombre de requêtes de table de hachage soit très élevé par rapport au nombre d'insertions. Par exemple, dans le cas de départage 290 x 290, vous disposez d'environ 3,6 millions d'insertions pour 22,7 millions de requêtes.
Dans ce contexte, un hachage non optimal mais rapide donne de meilleures performances.

Allocation de mémoire

Fournir un allocateur de mémoire efficace vient en second lieu. Cela a amélioré les performances d'environ 30%. La question de savoir si cela vaut la peine d'ajouter du code merdique est discutable :).

La version actuelle utilise entre 40 et 55 octets par nœud.
Les données fonctionnelles nécessitent 24 octets pour un nœud (4 coordonnées et 2 pointeurs).
En raison du cas de test insensé de 100 000 lignes, les coordonnées doivent être stockées dans des mots de 4 octets. Sinon, vous pourriez obtenir 8 octets en utilisant des courts-circuits (avec une valeur de coordonnées maximale de 32767). Les octets restants sont principalement utilisés par la table de hachage de l'ensemble non ordonné. Cela signifie que le traitement des données consomme en réalité un peu plus que la charge utile "utile".

Et le gagnant est...

Sur mon PC sous Win7, le départage (cas 23, 290x290) est résolu par la pire version (c'est-à-dire compilée par Microsoft) en 2,2 secondes environ, avec une consommation de mémoire d'environ 185 Mo.
À titre de comparaison, le leader actuel (code python de l'utilisateur2357112) prend un peu plus de 30 secondes et consomme environ 780 Mo.

Problèmes de contrôleur

Je ne suis pas sûr de pouvoir coder en Ruby pour me sauver la vie.
Cependant, j'ai repéré et piraté deux problèmes hors du code du contrôleur:

1) lecture de carte en track.rb

Avec Ruby 1.9.3 installé, le lecteur de piste craquerait de shift.to_ine pas être disponible string.lines.
Après avoir longuement parcouru la documentation en ligne de Ruby, j'ai abandonné les chaînes et utilisé un tableau intermédiaire à la place, comme ceci (tout au début du fichier):

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

2) tuer des fantômes dans controller.rb

Comme d'autres affiches l'ont déjà noté, le contrôleur tente parfois de supprimer les processus déjà terminés. Pour éviter ces sorties d'erreur honteuses, j'ai simplement traité l'exception, comme suit (autour de la ligne 134):

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

Cas de test

Pour vaincre l'approche par la force brute des solveurs BFS, la pire des pistes est l'inverse de la carte des 100 000 cellules: une zone totalement libre avec l'objectif le plus éloigné possible du début.

Dans cet exemple, une carte 100x400 avec l'objectif en haut à gauche et le début en bas à droite.

Cette carte a une solution en 28 tours, mais un résolveur BFS explorera des millions d’États pour la trouver (la mienne a compté 10,022,658 États visités, a pris environ 12 secondes et a culminé à 600 Mo!).

Avec moins de la moitié de la surface du départage 290 x 290, il nécessite environ 3 fois plus de visites de nœuds. D'autre part, un résolveur heuristique / A * devrait le vaincre facilement.

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

Bonus: une version PHP équivalente (mais un peu moins efficace)

C'est ce que j'ai commencé avec, avant que la lenteur inhérente au langage ne me convaince d'utiliser le C ++.
Les tables de hachage internes à PHP ne semblent pas aussi efficaces que celles de Python, du moins dans ce cas particulier :).

<?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";
?>

C ++, 5.4 (déterministe, optimal)

Solution de programmation dynamique. Probablement optimal. Très rapide: résout les 20 tests en 0.2s. Devrait être particulièrement rapide sur les machines 64 bits. Suppose que le tableau compte moins de 32 000 places dans chaque direction (ce qui devrait être vrai, espérons-le).

Ce coureur est un peu inhabituel. Il calcule le chemin optimal sur la ligne de départ, puis exécute instantanément le chemin calculé. Il ignore le contrôle du temps et suppose qu'il peut terminer l'étape d'optimisation à temps (ce qui devrait être vrai pour tout matériel raisonnablement moderne). Sur des cartes excessivement grandes, le coureur a une faible chance de se gommer. Si vous pouvez le convaincre de commettre une erreur de segmentation, vous obtenez un point brownie et je le résoudrai pour utiliser une boucle explicite.

Compiler avec g++ -O3 . Peut nécessiter C ++ 11 (pour <unordered_map>). Pour exécuter, exécutez simplement l'exécutable compilé (aucun indicateur ni aucune option n'est pris en charge; toutes les entrées sont prises sur 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;
}

Résultats

 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

Nouveau Testcase

Python 2 , déterministe, optimal

Voici mon coureur. Je ne l'ai pas testé sur le benchmark (je ne savais toujours pas quelle version et quel installateur Ruby installer), mais cela devrait tout résoudre de manière optimale et dans les délais. La commande pour l'exécuter est python whateveryoucallthefile.py. Nécessite le -sdrapeau du contrôleur.

# 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()

Après avoir inspecté le pilote de nneonneo (sans le tester, car je n’ai pas non plus de compilateur C ++), j’ai constaté qu’il semblait effectuer une recherche presque exhaustive de l’espace-état, quel que soit le but ou la brièveté. un chemin a déjà été trouvé. J'ai également constaté que les règles de temps impliquent que la création d'une carte avec une solution longue et complexe nécessite une longue limite de temps. Ainsi, ma soumission de carte est assez simple:

Nouveau Testcase

(GitHub ne peut pas afficher la longue ligne. La piste est *S.......[and so on].....)

Envoi supplémentaire: Python 2, recherche bidirectionnelle

C'est une approche que j'ai écrite il y a environ deux mois, lorsque j'essayais d'optimiser mon premier envoi en largeur. Pour les cas de test qui existaient à l'époque, cela n'apportait pas d'amélioration, donc je ne l'ai pas soumise, mais pour la nouvelle carte de kuroi, elle semble à peine se faufiler sous la limite de mémoire. Je m'attends toujours à ce que le résolveur de kuroi réussisse, mais je m'intéresse à la façon dont il résiste.

# 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()

Python 3: 6.49643 (Optimal, BFS)

Pour l'ancien fichier de référence de 20 cas, il a obtenu un score de 5,35643. La solution de @nneonneo n’est pas optimale car elle a obtenu 5.4. Quelques bugs peut-être.

Cette solution utilise BFS pour rechercher dans le graphique, chaque état de recherche se présente sous la forme (x, y, dx, dy). Ensuite, j'utilise une carte pour cartographier des états à des distances. Dans le pire des cas, sa complexité dans le temps et dans l’espace est O (n ^ 2 m ^ 2). Cela se produira rarement car la vitesse ne sera pas trop élevée ou le coureur se plantera. En fait, il a fallu 3 secondes sur ma machine pour compléter les 22 tests.

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()

# Résultats

± % 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

RandomRacer, ~ 40.0 (moyenne sur 10 analyses)

Ce n'est pas que ce bot n'a jamais termine une piste, mais certainement beaucoup moins souvent qu'une fois en 10 tentatives. (Je reçois un score non-pire des cas toutes les 20 à 30 simulations ou à peu près.)

Cela consiste principalement à agir comme un cas de base et à démontrer une implémentation possible (Ruby) pour un coureur:

# 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

Le courir avec

ruby controller.rb benchmark.txt ruby randomracer.rb

Random Racer 2.0, ~ 31

Eh bien, cela ne va pas battre le solveur optimal affiché, mais c’est une légère amélioration par rapport à un coureur aléatoire. La principale différence est que ce coureur envisagera uniquement d'aller au hasard là où il n'y a pas de mur, à moins qu'il ne manque d'endroits valides pour se déplacer, et s'il peut se déplacer vers un but qui tourne, ce sera le cas. Il ne bougera pas non plus pour rester au même endroit, à moins qu'il n'y ait pas d'autre mouvement disponible (improbable, mais possible).

Implémenté en Java, compilé avec java8, mais Java 6 devrait convenir. Aucun paramètre de ligne de commande. Il y a un assez bon groupe de hiérarchie, alors je pense que je fais 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;
        }
    }
}

Les résultats (meilleur cas que j'ai vu)

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