Gra
Większość z nas wie o Frogger , arkadowej grze z lat 80., w której celem jest bezpieczne przeskoczenie żaby przez ruchliwą autostradę i staw pełen niebezpieczeństw, aby bezpiecznie dotrzeć do domu.
Kilka miesięcy temu wydano wyzwanie opracowania klonu Frogger. Ale po co klonować Frogger, kiedy możesz grać w Frogger? :)
Rozważ następującą uproszczoną siatkę gry:
XXXXXXXXXXXXXXXXXXXXXXX North Safe Zone
-----------------------
| | <<<< Express Lane West (Lane 1)
| | > Gridlock East (Lane 2)
| | << Freeflowing Traffic West (Lane 3)
| | < Gridlock West (Lane 4)
| | >>>> Express Lane East (Lane 5)
-----------------------
XXXXXXXXXXX@XXXXXXXXXXX South Safe Zone
\__________ __________/
'
23 cells horizontally
Mamy pięć pasów ruchu, każdy o szerokości 23 komórek i dwie bezpieczne strefy (w których żaba może bezpiecznie poruszać się w lewo i w prawo), również o szerokości 23 komórek. Możesz zignorować prawą i lewą granicę, ponieważ służą one przejrzystości obrazu.
Nasza żaba zaczyna się w bezpiecznej południowej strefie, w środkowej (12.) komórce, jak @pokazano na powyższym rysunku.
Czas w grze podzielony jest na dyskretne kroki zwane ramkami. Froggy jest szybką żabą i może przeskakiwać jedną komórkę w dowolnym kierunku (w górę, w dół, w prawo, w lewo) na klatkę. Może również zdecydować, że pozostanie nieruchomy dla dowolnej klatki. Ruch na pięciu pasach ruchu odbywa się ze stałymi prędkościami w następujący sposób:
- ruch na linii ekspresowej na zachód (linia 1) przesuwa 2 komórki w lewo w każdej ramce
- ruch na wschodnim pasie siatki (pas 2) przesuwa 1 komórkę w prawo co drugą klatkę
- ruch na zachodnim pasie ruchu o swobodnym przepływie (pas 3) przesuwa 1 komórkę w lewo na każdą ramkę
- ruch na zachodnim pasie siatki (linia 4) przesuwa się o 1 komórkę w lewo co drugą klatkę
- ruch na linii ekspresowej wschód (linia 5) przesuwa 2 komórki w prawo w każdej ramce
Sam ruch jest jednoznacznie zdefiniowany dla ok. 3000 kroków czasowych w tym pliku tekstowym . „Ruch drogowy” obejmuje pojazdy i przestrzenie między pojazdami. Każda postać, która nie jest spacją, jest częścią pojazdu. Plik tekstowy zawiera pięć wierszy odpowiadających pięciu pasom ruchu (w tej samej kolejności).
W przypadku zachodnich pasów na początku ramki 0 (początek gry) uważamy, że pierwszy pojazd na linii znajduje się tuż za prawą krawędzią pola gry.
W przypadku pasów ruchu na wschód ciąg znaków należy uznać za „do tyłu” w tym sensie, że pojazdy pojawiają się na końcu ciągu. Na początku ramki 0 uważamy, że pierwszy pojazd na tych pasach znajduje się tuż za lewą krawędzią pola gry.
Rozważ jako przykład:
Traffic Lane 1: [|==| =
Traffic Lane 2: |) = o
Traffic Lane 3: (|[]-[]:
Traffic Lane 4: <| (oo|
Traffic Lane 5: |==|] :=)
Następnie pojawi się plansza gry:
Start of Frame 0 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 1 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 2 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 3 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Po tym, jak cały ruch na linii zostanie „wyczerpany” (tzn. Łańcuch się skończy), uważamy, że wszystkie znaki w łańcuchu są spacjami.
Nasza żaba jest zgnieciona, jeśli wystąpi którykolwiek z poniższych:
- żaba zajmuje komórkę zajmowaną przez pojazd, na dowolnej ramie
- żaba pozostaje nieruchoma na linii szybkiego ruchu, a pojazd o szerokości 1 komórki przechodzi nad nim w tej ramce
- żaba skacze na wschód „przez” pojazd jadący na zachód lub skacze na zachód przez pojazd jadący na wschód
- żaba wyskakuje poza siatkę 7 (linia) o 23 (komórka) na dowolnej klatce
Pamiętaj, że są to jedyne warunki, w których żaba jest wyciskana. W szczególności dozwolona jest żaba skacząca wraz z „ruchem”, podobnie jak żaba skacząca do lub z komórki na ekspresowym pasie, który jest omijany przez pojazd o szerokości 1 w tej samej ramie.
Cel i punktacja
Celem wyzwania programowania jest poprowadzenie żaby tak często, jak to możliwe, zanim ostatni pojazd opuści pole gry . Oznacza to, że program kończy się natychmiast po zakończeniu ramki X , gdzie rama X jest pierwszą ramką, która przenosi siatkę do stanu, w którym nie ma już więcej pojazdów.
Wyjście Twojego programu powinno być ciągiem (lub plikiem tekstowym) zawierającym sekwencję ruchów żaby przy użyciu następującego kodowania:
< frog moves left
> frog moves right
^ frog moves up
v frog moves down
. frog remains stationary
Na przykład ciąg znaków <<^.^wskazuje, że żaba przesuwa się dwukrotnie w lewo, następnie w górę, następnie zatrzymuje się na jedną klatkę, a następnie przesuwa się ponownie w górę.
Jeden punkt jest przyznawany za każdym razem, gdy żaba przechodzi z bezpiecznej strefy południowej do bezpiecznej strefy północnej, a jeden punkt jest przyznawany za każdym razem, gdy żaba przechodzi z bezpiecznej strefy północnej do bezpiecznej strefy południowej.
Kilka ważnych zasad:
- Żaba nie może być zgnieciona.
- Proszę zamieścić swoje rozwiązanie (sekwencję ruchów) wraz z kodem programu, albo w pliku tekstowym (np. Za pomocą pastebin.com).
- Nasza żaba jest przewidywalna i wstępnie rozpoznawalna, dlatego Twój program może wykorzystywać dowolne dane o ruchu w dowolnej ramce podczas wyszukiwania rozwiązań. Obejmuje to dane dotyczące ruchu, który nie dotarł jeszcze do planszy odtwarzania.
- Siatka się nie zawija. Wyjście z siatki spowoduje zgniecenie żaby i dlatego nie jest dozwolone.
- W żadnym momencie ruch nie „resetuje się”, a żaba nie „teleportuje się”. Symulacja jest ciągła.
- Żaba może powrócić do bezpiecznej strefy południowej po wyjściu z niej, ale nie jest to liczone jako punkt. Podobnie dla północnej strefy bezpieczeństwa.
- Zwycięzcą konkursu jest program, który generuje sekwencję ruchów zapewniającą największą liczbę skrzyżowań.
- W przypadku jakichkolwiek dodatkowych pytań lub wątpliwości prosimy o kontakt w sekcji komentarzy.
Aby uzyskać dodatkową zachętę, dodam nagrodę +100 powtórzeń do zwycięskiego programu, gdy będę mógł to zrobić.
Bonusy
+ 2,5% do wyniku podstawowego * (do + 10%) za każdy róg siatki gry, której dotyka żaba. Cztery rogi siatki są skrajnie lewą i prawą komórką dwóch bezpiecznych stref.
+ 25% do wyniku podstawowego *, jeśli sekwencja ruchów utrzymuje żabę w granicach +/- 4 komórek po lewej lub prawej stronie komórki początkowej dla całej symulacji (może oczywiście swobodnie poruszać się pionowo).
Brak premii za punktację, ale specjalne rekwizyty w PO trafią do każdego, kto opublikuje szybki i brudny walidator rozwiązania, abym nie musiał go programować. ;) Walidator po prostu zaakceptuje sekwencję ruchów, zapewni jej zgodność z prawem (zgodnie z przepisami i plikiem ruchu) i zgłosi swój wynik (tj. Całkowitą liczbę przejazdów).
* Całkowity wynik jest równy wynikowi podstawowemu powiększonemu o bonus, zaokrąglony w dół do najbliższej liczby całkowitej.
Odpowiedzi:
C ++: 176
Wynik:
Istnieje ponad 8 milionów kombinacji
stanówpozycji X czas X zestaw odwiedzonych rogów, więc można je wyczerpująco przeszukać w mniej niż 1 sekundę. Jeśli w kodzie nie ma błędów, jego pokonanie powinno być niemożliwe. Optymalną strategią było użycie całej planszy, ponieważ pozwala żabce przejść 160 razy drogę, w porównaniu do około 120, gdy jest ograniczona do centrum. Odwiedzanie zakrętów nie kosztowało żadnych przejazdów, ponieważ ruch był tak duży.źródło