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 ±1
lub 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
target
to maksymalna liczba zwojów, jaką możesz wykonać, aby ukończyć ścieżkę, i time
cał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:
#
- ŚcianaS
- początek*
- cel.
- wszystkie pozostałe komórki toru (tj. Droga)
Wszystkie komórki poza udostępnioną n x m
siatką 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
, v
są liczbami całkowitymi 0 oparte. (x,y)
to twoja aktualna pozycja i (u,v)
aktualna prędkość. Zauważ, że x+u
i / lub y+v
może być poza zakresem.
time
to 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ś target
obroty, skończył się czas lub osiągnąłeś cel), otrzymasz pustą linię.
Wydajność
Dla każdej tury napisz na stdout :
Δu Δv
gdzie Δu
i Δv
każ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/2
sekundach. 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 przez
target
. - Jeśli zabraknie Ci czasu / pamięci lub nie osiągniesz bramki przed upływem
target
tury lub wylądujesz w ścianie / poza boiskiem w dowolnym momencie, Twój wynik to2
. - 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
n
w10
poró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.
target
Wola4*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 Point2D
i 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
, -t
przed 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
-s
flagi, czy nie. - (opcjonalnie) Nowa ścieżka do rozwiązania, która zostanie dodana do testu porównawczego. Określę rozsądnie
target
dla 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
- 6.86688 - Kuroi Neko
- 8.73108 - user2357112 - 2. przesłanie
- 9,86627 - nneonneo
- 10.66109 - user2357112 - Pierwsze przesłanie
- 12,49643 - Ray
- 40.0759 - pseudonim 117 (probabilistyczny)
Szczegółowe wyniki testu . (Wyniki dla wniosków probabilistycznych zostały określone osobno.)
źródło
400
, ponieważ jest to zgodne z tym, jak ustaliłem wszystkie pozostałe cele (oprócz remisu). Zaktualizuję główny post, gdy zmienię wszystkie pozostałe zgłoszenia.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).Wyniki
Nowa walizka testowa
źródło
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-s
flagi kontrolera.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.
źródło
n = 400
). Daj mi znać, jeśli zastosujesz jakieś optymalizacje, bym mógł ponownie uruchomić testy.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.
# Wyniki
źródło
O(√n)
co twoja implementacjaO(n³)
na kwadratowych siatkach (tak jak inne, jak sądzę). Dodam remis, aby ocenić twoje przesłanie w porównaniu do user2357112 później.n=270
i dlatego jesteś teraz za pozostałymi dwoma „optymalnymi” zgłoszeniami. To powiedziawszy, twoje zgłoszenie jest również najwolniejsze z trzech, więc i tak byłoby trzecie, tylko z większym rozstrzygnięciem.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:
Uruchom to z
źródło
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.
Wyniki (najlepszy przypadek, jaki widziałem)
źródło
.class
z jakiegoś powodu musiałem go uruchomić z katalogu, w którym znajduje się plik (zamiast katalogu, w którym znajduje się kontroler). Wyślij mi ping (z komentarzem), jeśli zdecydujesz się dodać testcase, abym mógł dodać go do testu porównawczego. Twój wynik wyniósł około 33 w ciągu 10 przebiegów (patrz tabela wyników), ale może się to zmienić wraz z każdym nowym torem testowym dodawanym do testu porównawczego.java -cp path/to/class/file VectorRacing