Użytkownik CarpetPython opublikował nowe podejście do tego problemu, który kładzie większy nacisk na rozwiązania heurystyczne, ze względu na zwiększoną przestrzeń wyszukiwania. Osobiście uważam, że wyzwanie jest o wiele ładniejsze niż moje, więc spróbuj spróbować!

Wyścigi wektorowe to wciągająca gra, w którą można grać długopisem i kartką papieru o kwadratowych liniach. Narysujesz na papierze dowolny tor wyścigowy, określisz początek i koniec, a następnie pokierujesz swoim samochodem punktowym w sposób turowy. Dotrzyj do końca tak szybko, jak to możliwe, ale uważaj, aby nie skończyć w ścianie!

Utwór

• Mapa jest dwuwymiarową siatką, w której każda komórka ma współrzędne całkowite.
• Poruszasz się po komórkach siatki.
• Każda komórka siatki jest albo częścią ścieżki, albo ścianą.
• Dokładnie jedna komórka ścieżki jest współrzędną początkową.
• Co najmniej jedna komórka śledzenia jest wyznaczona jako cel. Lądowanie na którymkolwiek z nich kończy wyścig. Wiele komórek celu niekoniecznie jest połączonych.

Kierowanie samochodem

Twój samochód zaczyna się od określonej współrzędnej i wektora prędkości (0, 0). W każdej turze możesz regulować każdy składnik prędkości ±1lub pozostawić go bez zmian . Następnie powstały wektor prędkości jest dodawany do pozycji samochodu.

Zdjęcie może pomóc! Czerwone kółko było Twoją pozycją w ostatniej turze. Niebieskie kółko to twoja aktualna pozycja. Twoja prędkość to wektor od czerwonego do niebieskiego koła. W tej turze, w zależności od sposobu regulacji prędkości, możesz przejść do dowolnego z zielonych kół.

Jeśli wylądujesz w ścianie, natychmiast przegrywasz.

Twoje zadanie

Zgadłeś: napisz program, który biorąc pod uwagę tor wyścigowy jako dane wejściowe, kieruje samochód do jednej z komórek bramkowych w jak najmniejszej liczbie zakrętów. Twoje rozwiązanie powinno być w stanie dobrze radzić sobie z dowolnymi ścieżkami i nie być specjalnie zoptymalizowane pod kątem dostarczonych przypadków testowych.

Wejście

Kiedy twój program zostanie wywołany, czytaj ze standardowego wejścia :

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

targetto maksymalna liczba zwojów, jaką możesz wykonać, aby ukończyć ścieżkę, i timecałkowity budżet czasu ścieżki, w sekundach (niekoniecznie liczba całkowita). Zobacz poniżej szczegóły dotyczące czasu.

W przypadku ścieżki rozdzielanej znakiem nowej linii używane są następujące znaki:

• # - Ściana
• S- początek
• *- cel
• . - wszystkie pozostałe komórki toru (tj. Droga)

Wszystkie komórki poza udostępnioną n x msiatką mają być ścianami.

Początek współrzędnych znajduje się w lewym górnym rogu.

Oto prosty przykład:

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

Przy indeksowaniu opartym na 0 początkowa współrzędna byłaby (0,4).

Po każdym ruchu otrzymasz dalsze informacje:

x y
u v
time

Gdzie x, y, u, vsą liczbami całkowitymi 0 oparte. (x,y)to twoja aktualna pozycja i (u,v)aktualna prędkość. Zauważ, że x+ui / lub y+vmoże być poza zakresem.

timeto ile pozostało z twojego budżetu czasu, w sekundach. Możesz to zignorować. Jest to tylko dla uczestników, którzy naprawdę chcą, aby ich wdrożenie zostało zrealizowane w wyznaczonym terminie.

Po zakończeniu gry (ponieważ wylądowałeś w ścianie, wyszedłeś poza granice, przekroczyłeś targetobroty, skończył się czas lub osiągnąłeś cel), otrzymasz pustą linię.

Wydajność

Dla każdej tury napisz na stdout :

Δu Δv

gdzie Δui Δvkażdy są jednym -1, 0, 1. Zostanie to dodane w (u,v)celu ustalenia nowej pozycji. Aby wyjaśnić, wskazówki są następujące

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

Optymalnym rozwiązaniem dla powyższego przykładu byłoby

1 0
1 -1
1 0

Zauważ, że kontroler nie podłącza się do stderr , więc możesz go używać do wszelkiego rodzaju wyników debugowania, których możesz potrzebować podczas tworzenia bota. Proszę jednak usunąć / skomentować wszelkie takie dane wyjściowe w przesłanym kodzie.

Twój bot może potrzebować pół sekundy na odpowiedź w każdej turze. W przypadku tur, które trwają dłużej, będziesz mieć budżet czasu (na ścieżkę) w target/2sekundach. Za każdym razem, gdy tura trwa dłużej niż pół sekundy, dodatkowy czas zostanie odjęty od twojego budżetu czasu. Kiedy budżet czasu osiągnie zero, bieżący wyścig zostanie przerwany.

Nowość: Ze względów praktycznych muszę ustawić limit pamięci (ponieważ pamięć wydaje się bardziej ograniczająca niż czas dla rozsądnych rozmiarów ścieżek). Dlatego będę musiał przerwać każdy test, w którym zawodnik zużywa więcej niż 1 GB pamięci, mierzonej przez Process Explorer jako Private Bytes .

Punktacja

Test porównawczy obejmuje 20 utworów. Dla każdej ścieżki:

• Jeśli ukończysz ścieżkę, twój wynik to liczba ruchów, które musisz osiągnąć, aby dotrzeć do komórki bramkowej podzielona przeztarget .
• Jeśli zabraknie Ci czasu / pamięci lub nie osiągniesz bramki przed upływem targettury lub wylądujesz w ścianie / poza boiskiem w dowolnym momencie, Twój wynik to 2.
• Jeśli twój program nie jest deterministyczny, twój wynik to średnia z 10 przebiegów na tym torze (proszę podać to w odpowiedzi).

Twój ogólny wynik to suma wyników poszczególnych utworów. Najniższy wynik wygrywa!

Ponadto każdy uczestnik może (i zdecydowanie zachęca) do zapewnienia dodatkowej ścieżki porównawczej , która zostanie dodana do oficjalnej listy. Poprzednie odpowiedzi zostaną ponownie ocenione, w tym ten nowy utwór. Ma to na celu upewnienie się, że żadne rozwiązanie nie jest zbyt ściśle dopasowane do istniejących przypadków testowych i uwzględnienie interesujących przypadków skrajnych, które mogłem przeoczyć (ale które można zauważyć).

Łamanie krawatów

Teraz, gdy istnieje już optymalne rozwiązanie, będzie to prawdopodobnie główny czynnik dla wyników uczestników.

Jeśli istnieje remis (z powodu kilku odpowiedzi optymalnie rozwiązujących wszystkie ścieżki lub w inny sposób), dodam dodatkowe (większe) przypadki testowe w celu zerwania remisu. Aby uniknąć uprzedzeń u ludzi podczas tworzenia tych przerywników, zostaną one wygenerowane w ustalony sposób:

• Zwiększę długość boku nw 10porównaniu do ostatniej ścieżki wygenerowanej w ten sposób. (Mogę pominąć rozmiary, jeśli nie zerwą remisu).
• Podstawą jest grafika wektorowa
• Zostanie to zrasteryzowane w pożądanej rozdzielczości przy użyciu tego fragmentu kodu Mathematica .
• Początek znajduje się w lewym górnym rogu. W szczególności będzie to komórka znajdująca się najbardziej po lewej stronie najwyższego rzędu tego końca ścieżki.
• Cel znajduje się w prawym dolnym rogu. W szczególności będzie to komórka znajdująca się najbardziej na prawo od najniższego rzędu tego końca ścieżki.
• targetWola 4*n.

Ostateczna ścieżka początkowego testu porównawczego została już wygenerowana w ten sposób, z n = 50.

Kontroler

Program do testowania zgłoszeń jest napisany w Ruby i można go znaleźć na GitHub wraz z plikiem testu, którego będę używać. Jest tam także wywoływany przykładowy bot randomracer.rb, który po prostu wybiera losowe ruchy. Możesz użyć jego podstawowej struktury jako punktu wyjścia dla bota, aby zobaczyć, jak działa komunikacja.

Możesz uruchomić własnego bota na wybranym pliku ścieżki w następujący sposób:

ruby controller.rb track_file_name command to run your racer

na przykład

ruby controller.rb benchmark.txt ruby randomracer.rb

Repozytorium zawiera także dwie klasy Point2Di Track. Jeśli Twoje zgłoszenie zostało napisane w języku Ruby, możesz je ponownie wykorzystać dla Twojej wygody.

Przełączniki wiersza polecenia

Możesz dodać przełączniki wiersza polecenia -v, -s, -tprzed nazwą pliku w benchmarku. Jeśli chcesz użyć wielu przełączników, możesz także zrobić na przykład -vs. Oto co robią:

-v (verbose): Użyj tego, aby uzyskać nieco więcej danych do debugowania ze sterownika.

-s (cicho): Jeśli wolisz samodzielnie śledzić swoją pozycję i prędkość i nie zależy ci na budżecie czasu, możesz wyłączyć te trzy linie wyników za każdym razem (wysyłane do twojego zgłoszenia) za pomocą tej flagi.

-t(ścieżki): Pozwala wybrać pojedyncze ścieżki do przetestowania. Np. Testowałby tylko -t "1,2,5..8,15"ścieżki 1, 2, 5, 6, 7, 8 i 15. Bardzo dziękuję Ventero za tę funkcję i analizator opcji.

Twoje zgłoszenie

Podsumowując, w odpowiedzi należy podać następujące informacje:

• Twój wynik.
• Jeśli używasz losowości, podaj to, abym mógł uśrednić Twój wynik w wielu biegach.
• Kod zgłoszenia.
• Lokalizacja bezpłatnego kompilatora lub tłumacza dla wybranego języka działającego na komputerze z systemem Windows 8.
• Instrukcje kompilacji, jeśli to konieczne.
• Ciąg wiersza polecenia systemu Windows, aby uruchomić przesyłanie.
• Niezależnie od tego, czy przesłanie wymaga podania -sflagi, czy nie.
• (opcjonalnie) Nowa ścieżka do rozwiązania, która zostanie dodana do testu porównawczego. Określę rozsądnie targetdla twojego toru ręcznie. Gdy utwór zostanie dodany do testu porównawczego, wyedytuję go z Twojej odpowiedzi. Zastrzegam sobie prawo do poproszenia Cię o inny utwór (na wypadek, gdybyś dodał nieproporcjonalnie duży utwór, wrzucił nieprzyzwoitą grafikę ASCII itp.). Kiedy dodam przypadek testowy do zestawu testów, zastąpię ścieżkę w twojej odpowiedzi linkiem do ścieżki w pliku testu, aby zmniejszyć bałagan w tym poście.

Jak widać, będę testować wszystkie zgłoszenia na komputerze z systemem Windows 8. Jeśli nie ma absolutnie żadnego sposobu na uruchomienie przesyłania w systemie Windows, mogę również wypróbować maszynę Wirtualną Ubuntu. Będzie to jednak znacznie wolniejsze, więc jeśli chcesz maksymalnie ograniczyć czas, upewnij się, że Twój program działa w systemie Windows.

Oby najlepszy kierowca pojawił się wektorowo!

Ale ja chcę grać!

Jeśli chcesz wypróbować grę, aby lepiej ją poczuć, dostępna jest ta implementacja . Stosowane tam zasady są nieco bardziej wyrafinowane, ale myślę, że są wystarczająco podobne, aby były przydatne.

Tabela liderów

Ostatnia aktualizacja: 01/09/2014, 21:29 UTC
Utwory w teście porównawczym: 25
Rozmiary remisów: 290, 440

1. 6.86688 - Kuroi Neko
2. 8.73108 - user2357112 - 2. przesłanie
3. 9,86627 - nneonneo
4. 10.66109 - user2357112 - Pierwsze przesłanie
5. 12,49643 - Ray
6. 40.0759 - pseudonim 117 (probabilistyczny)

Szczegółowe wyniki testu . (Wyniki dla wniosków probabilistycznych zostały określone osobno.)

C ++ 11 - 6,66109

Kolejna szeroka implementacja pierwszego wyszukiwania, tylko zoptymalizowana.

Musi być uruchomiony z opcją -s .
Jego wkład w ogóle nie jest dezynfekowany, więc złe ścieżki mogą zmienić go w dyni.

Przetestowałem to z Microsoft Visual C ++ 2013, wersja kompilacji z domyślną flagą / O2 (optymalizacja pod kątem szybkości).
CZY buduje OK z g ++ i Microsoft IDE.
Mój boski alokator pamięci to bzdura, więc nie oczekuj, że będzie działał z innymi implementacjami STL 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;
}

Wyniki

 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

Występy

Ten gówniany język C ++ ma talent do skakania przez obręcze tylko po to, by poruszyć zapałkę. Możesz jednak wykorzystać go do tworzenia stosunkowo szybkiego i wydajnego pamięci.

Hashowanie

Tutaj kluczem jest zapewnienie dobrej tabeli skrótów dla węzłów. Jest to zdecydowanie dominujący czynnik szybkości wykonywania.
Dwie implementacje unordered_set(GNU i Microsoft) przyniosły 30% różnicę prędkości wykonania (na korzyść GNU, tak!).

Różnica nie jest tak naprawdę zaskakująca, co z ukrytą za nią ciężarówką kodu unordered_set.

Z ciekawości zrobiłem statystyki dotyczące ostatecznego stanu tabeli skrótów.
Oba algorytmy mają prawie taki sam stosunek segmentu do elementów, ale podział jest różny:
w przypadku przerywacza remisów 290x290 GNU otrzymuje średnio 1,5 elementu na niepuste segmenty, podczas gdy Microsoft ma wartość 5,8 (!).

Wygląda na to, że moja funkcja haszująca nie jest zbyt dobrze losowa przez Microsoft ... Zastanawiam się, czy faceci w Redmond naprawdę porównali swoje STL, a może mój przypadek użycia po prostu sprzyja implementacji GNU ...

Jasne, moja funkcja haszująca nie jest prawie optymalna. Mógłbym użyć zwykłego mieszania liczb całkowitych w oparciu o wielokrotne przesunięcie / impulsy, ale funkcja efektywna w haszowaniu wymaga czasu.

Wygląda na to, że liczba zapytań do tabeli skrótów jest bardzo wysoka w porównaniu z liczbą wstawień. Na przykład w wyłączniku remisu 290x290 masz około 3,6 miliona wstawek dla 22,7 miliona zapytań.
W tym kontekście nieoptymalne, ale szybkie mieszanie daje lepsze wyniki.

Przydział pamięci

Zapewnienie wydajnego alokatora pamięci zajmuje drugie miejsce. Poprawił wydajność o około 30%. To, czy warto, to dodany kod bzdur jest dyskusyjny :).

Obecna wersja wykorzystuje od 40 do 55 bajtów na węzeł.
Dane funkcjonalne wymagają 24 bajtów dla węzła (4 współrzędne i 2 wskaźniki).
Ze względu na szalony przypadek testowy 100 000 linii, współrzędne muszą być przechowywane w 4 bajtowych słowach, w przeciwnym razie można uzyskać 8 bajtów za pomocą skrótów (z maksymalną wartością współrzędnych 32767). Pozostałe bajty są w większości zużywane przez tablicę skrótu nieuporządkowanego zestawu. Oznacza to, że przetwarzanie danych faktycznie zużywa nieco więcej niż „użyteczny” ładunek.

A zwycięzcą jest...

Na moim komputerze z Win7, remis (przypadek 23, 290x290) jest rozwiązany przez najgorszą wersję (tj. Skompilowaną przez Microsoft) w około 2,2 sekundy, przy zużyciu pamięci około 185 Mb.
Dla porównania, obecny lider (kod python autorstwa user2357112) zajmuje nieco ponad 30 sekund i zużywa około 780 Mb.

Problemy z kontrolerem

Nie jestem pewien, czy uda mi się napisać w Ruby kod, aby uratować mi życie.
Jednak zauważyłem i zhackowałem dwa problemy z kodu kontrolera:

1) wczytywanie mapy w track.rb

Po zainstalowaniu Ruby 1.9.3 czytnik śladów wykrzykiwałby, że shift.to_inie jest dostępny string.lines.
Po długim przejściu przez internetową dokumentację Ruby zrezygnowałem z napisów i zamiast tego użyłem tablicy pośredniej, tak jak na początku (na początku pliku):

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

2) zabijanie duchów w controller.rb

Jak zauważyli już inni plakaty, kontroler czasami próbuje zabić procesy, które już się zakończyły. Aby uniknąć tych haniebnych wyników błędów, po prostu usunąłem wyjątek, tak jak poniżej (około linii 134):

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

Przypadek testowy

Aby pokonać podejście brutalnej siły w solverach BFS, najgorszy tor jest przeciwieństwem mapy 100 000 komórek: całkowicie wolny obszar z celem jak najdalej od początku.

W tym przykładzie mapa 100 x 400 z celem w lewym górnym rogu i początkiem w prawym dolnym rogu.

Ta mapa ma rozwiązanie w 28 turach, ale solver BFS zbada miliony stanów, aby ją znaleźć (moja zliczona 10 022 655 odwiedzonych stanów, zajęła około 12 sekund i osiągnęła szczyt przy 600 Mb!).

Z mniej niż połową powierzchni zrywacza 290x290, wymaga około 3 razy więcej wizyt w węźle. Z drugiej strony solver oparty na heurystyce / A * powinien go łatwo pokonać.

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

Bonus: równoważna (ale nieco mniej wydajna) wersja PHP

Z tym zacząłem, zanim wrodzona powolność języka przekonała mnie do używania C ++.
Wewnętrzne tabele skrótów PHP nie wydają się tak wydajne jak tabele Pythona, przynajmniej w tym konkretnym przypadku :).

<?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 (deterministyczny, optymalny)

Dynamiczne rozwiązanie programistyczne. Zapewnione optymalnie. Bardzo szybko: rozwiązuje wszystkie 20 przypadków testowych w 0,2 sekundy. Powinny być szczególnie szybkie na komputerach 64-bitowych. Zakłada się, że plansza ma mniej niż 32 000 miejsc w każdym kierunku (co, mam nadzieję, powinno być prawdą).

Ten zawodnik jest trochę niezwykły. Oblicza optymalną ścieżkę na linii początkowej, a następnie natychmiast wykonuje obliczoną ścieżkę. Ignoruje kontrolę czasu i zakłada, że ​​może ukończyć krok optymalizacji na czas (co powinno być prawdą w przypadku każdego stosunkowo nowoczesnego sprzętu). Na zbyt dużych mapach istnieje niewielka szansa, że ​​zawodnik może się segregować. Jeśli zdołasz przekonać go do segfaulta, otrzymasz punkt brownie, a ja naprawię go, aby używał wyraźnej pętli.

Kompiluj z g++ -O3. Może wymagać C ++ 11 (for <unordered_map>). Aby uruchomić, wystarczy uruchomić skompilowany plik wykonywalny (nie są obsługiwane flagi ani opcje; wszystkie dane wejściowe są pobierane na standardowe wejście).

#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;
}

Wyniki

 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

Nowa walizka testowa

Python 2 , deterministyczny, optymalny

Oto mój zawodnik. Nie testowałem tego na testach porównawczych (wciąż nie wiem, jaką wersję i instalatora Ruby zainstalować), ale powinno to wszystko rozwiązać optymalnie i w terminie. Poleceniem do uruchomienia jest python whateveryoucallthefile.py. Potrzebuje -sflagi kontrolera.

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

Po sprawdzeniu racera nneonneo (ale nie testowaniu go, ponieważ nie mam również kompilatora C ++), stwierdziłem, że wydaje się on przeprowadzać prawie wyczerpujące przeszukiwanie przestrzeni stanów, bez względu na to, jak blisko celu lub jak krótko ścieżka została już znaleziona. Odkryłem również, że reguły czasowe oznaczają, że zbudowanie mapy z długim, złożonym rozwiązaniem wymaga długiego, nudnego limitu czasu. Zatem przesłanie mapy jest dość proste:

Nowa walizka testowa

(GitHub nie może wyświetlić długiej linii. Ścieżka jest *S.......[and so on].....)

Dodatkowe przesłanie: Python 2, wyszukiwanie dwukierunkowe

Jest to podejście, które napisałem około dwa miesiące temu, próbując zoptymalizować moje pierwsze zgłoszenie. W przypadku przypadków testowych, które istniały w tym czasie, nie oferowało to ulepszenia, więc go nie przesłałem, ale w przypadku nowej mapy Kuroi wydaje się, że ledwo się przeciska pod pokrywą pamięci. Nadal oczekuję, że solver Kuroi to pokona, ale interesuje mnie, jak to wytrzyma.

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

W przypadku starego pliku z 20 wynikami testu uzyskał on wynik 5,35643. Rozwiązanie @nneonneo nie jest optymalne, ponieważ ma 5,4. Może jakieś błędy.

To rozwiązanie używa BFS do przeszukiwania wykresu, każdy stan wyszukiwania ma postać (x, y, dx, dy). Następnie używam mapy do mapowania stanów i odległości. W najgorszym przypadku złożoność czasu i przestrzeni wynosi O (n ^ 2 m ^ 2). Zdarza się to rzadko, ponieważ prędkość nie będzie zbyt wysoka lub zawodnik się rozbije. Ukończenie wszystkich 22 przypadków testowych na moim komputerze kosztowało 3 sekundy.

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

＃ Wyniki

± % 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 (uśredniony dla 10 przebiegów)

Nie chodzi o to, że ten bot nigdy nie kończy utworu, ale zdecydowanie rzadziej niż raz na 10 prób. (Dostaję najgorszy wynik co 20-30 symulacji.)

Ma to głównie służyć jako przypadek podstawowy i zademonstrować możliwą implementację (Ruby) dla zawodnika:

# 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

Uruchom to z

ruby controller.rb benchmark.txt ruby randomracer.rb

Random Racer 2.0, ~ 31

Cóż, to nie będzie w stanie pokonać opublikowanego optymalnego solwera, ale jest to niewielka poprawa w przypadku losowego kierowcy. Główna różnica polega na tym, że ten kierowca rozważy losowe wybranie się tam, gdzie nie ma muru, chyba że zabraknie ważnych miejsc do poruszania się, a jeśli uda mu się osiągnąć cel, który się zmieni, to zrobi to. Nie porusza się również, aby pozostać w tym samym miejscu, chyba że nie ma innego dostępnego ruchu (mało prawdopodobne, ale możliwe).

Zaimplementowane w Javie, skompilowane z java8, ale Java 6 powinna być w porządku. Brak parametrów wiersza poleceń. Istnieje całkiem niezła hierarchia, więc myślę, że dobrze wykonuję 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;
        }
    }
}

Wyniki (najlepszy przypadek, jaki widziałem)

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