Fabuła
Indiana Jones eksplorowała jaskinię, w której znajduje się cenny skarb. Nagle nastąpiło trzęsienie ziemi.
Kiedy trzęsienie ziemi się skończyło, zauważył, że niektóre skały, które spadły z sufitu, blokowały mu drogę do skarbu. Zauważył również, że może pchać kamień, ale ponieważ kamienie były bardzo ciężkie, nie mógł popchnąć dwóch kolejnych kamieni .
Twoim celem jest pomóc Indianie Jonesowi zdobyć skarb. Ponieważ bardzo trudno jest popchnąć choćby jeden kamień, liczba pchnięć jest bardzo ważna.
Problem
Znajdź najlepszy sposób (gdzie Indiana Jones pcha kamienie jak najmniej), aby znaleźć skarb.
Mapa (wejście)
Mapa jest m
przez n
(zarówno większy niż 1) matrycy, która może zawierać pięć rodzajów komórek:
0
co oznacza pustą komórkę,1
co oznacza ścianę,2
w którym znajduje się Indiana Jones (istnieje tylko jeden),3
w którym znajduje się skarb (istnieje tylko jeden),- i
4
, co oznacza kamień.
W pierwszym rzędzie mapy określa się wymiar mapy 4 6
, a od drugiego do ostatniego rzędu mapy określa się strukturę jaskini mniej więcej tak.
110131
104040
100101
200000
Dlatego pełna mapa to:
4 6
110131
104040
100101
200000
co znaczy
Mapę podaje stdin, plik (możesz podać nazwę pliku) lub tablica w kodzie, która zawiera tylko powyższe informacje.
Wynik
Minimalna kwota, którą Indiana Jones powinna wcisnąć. Jeśli nie ma takiego sposobu, wyjdź X
.
W powyższym przypadku może popchnąć kamień po lewej stronie w górę, a następnie może popchnąć kamień po prawej stronie w prawo, aby zdobyć skarb. Dlatego w tym przypadku wynikiem jest 2
.
Jednak. w tym przypadku :
4 6
111131
104040
100101
200000
(spójrz poniżej) nie może popchnąć prawego kamienia, ponieważ zniszczy on skarb. Również pchnięcie lewego kamienia w prawo nic nie zmienia. Dlatego dane wyjściowe to X
.
Zasady
- Może poruszać się tylko w czterech kierunkach: w górę, w dół, w lewo i w prawo.
- Nie może pchnąć dwóch kolejnych kamieni .
- Nie może ciągnąć żadnego kamienia i może pchać kamień tylko w jednym kierunku („do przodu”).
- Nie może przejść przez ściany. Jedynymi miejscami, do których może się udać, są puste komórki i komórka skarbów.
- Kamienia nie można umieścić na skarbie. To zniszczy skarb. :(
- Nie może wyjść poza mapę.
Cele
Program, który może obsłużyć większość map (podanych w sekcji „Przykład” + inne) w rozsądnym czasie (w szczególności 10 sekund) i wyświetla właściwą odpowiedź wygrywa.
Tutaj „inni” oznaczają przykładowe dane wejściowe podane w odpowiedziach. Oznacza to, że powinieneś stworzyć inteligentny algorytm, aby inne programy nie mogły rozwiązać map, które Twój program może rozwiązać, a mapy rozwiązane przez inne programy mogą być rozwiązane przez Twój program. Jednak umieszczanie rozwiązań w kodzie nie będzie uważane za prawidłowe.
Uwaga
Pierwotnie był to średniookresowy projekt klasy AI, którego słuchałem, tylko jedna rzecz była inna: mówiono, że były tylko dwie skały.
Mówiono, że problemem jest NP, ale powiedziano również, że dobry algorytm heurystyczny może dość skutecznie rozwiązać problem. Użyłem kilku pomysłów i heurystyki, aby skutecznie rozwiązać problem, a mój kod mógł bardzo szybko znaleźć wszystkie rozwiązania próbek (mniej niż sekundę).
Jednak gdy były więcej niż dwie skały, były przypadki, w których kod nie mógł znaleźć odpowiedzi w rozsądnym czasie. Miałem kilka pomysłów, ale niektóre były „błędne” i nie mogłem wyrazić innych pomysłów w kodzie. Chciałem zobaczyć, jakie inteligentne algorytmy istnieją, aby rozwiązać ten problem, więc napisałem to.
Ponieważ już ukończyłem projekt (tak przy okazji, obrazy nie są moje - przeglądałem je), nie musisz się o to martwić.
Przykłady
Przykłady można zobaczyć tutaj. Możesz także zobaczyć przykłady i przetestować swoje wyniki tutaj (powinno to działać w nowoczesnych przeglądarkach). Możesz uzyskać mapę w formacie opisanym powyżej, pisząc whatisthis()
w konsoli JS.
http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 zawiera przykłady, które pierwotnie były dostarczone przez klasę.
Wynik
Przepraszam za spóźnienie… właściwie całkiem sporo. : P (Byłem zbyt leniwy, by zdobyć punkty. Przepraszam.)
Poniżej znajduje się wynik. (X: źle, O: dobrze,?: Trwa co najmniej 10 sekund, zatrzymany)
Map#: 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
Ruby: X O O ? O O O X ? ? O ? ? ? ? ?
Java: O O X O X X O O ? ? O O O X O O
(Java 19: zajęło 25 sekund, wynik był poprawny.) (Użyłem Ruby 1.9.3 i javac 1.7.0_13)
Wygląda na to, że algorytm Java był rzeczywiście lepszy. (Nawiasem mówiąc, myślałem o podobnej metodzie, ale zdałem sobie sprawę, że istnieją mapy takie jak mapa testowa 5).
źródło
Odpowiedzi:
Java - nieco mądrzejszy / szybszy
Całkiem trochę kodu. Staram się być szybszy, oceniając pchnięcia w kolejności „jak prawdopodobne jest uwolnienie drogi do skarbu”, która sama w sobie opiera się na dwóch wędrówkach Dijkstry (jeden zatrzymuje się, gdy napotyka skały, drugi ignoruje skały). Działa całkiem nieźle, a ten przykład z pastebinu, który wydaje się być kłopotliwy dla autora, został rozwiązany w około 2 sekund przez tę implementację. Niektóre inne przykłady trwają do 30-40 sekund, co wciąż uważam za zbyt długie, ale nie mogłem znaleźć sposobu, aby to poprawić bez zepsucia rzeczy :)
Podzieliłem swoje rzeczy na kilka plików, aby uzyskać lepszą strukturę (także dlaczego przestawiłem się na Javę z Ruby):
Punkt wejścia:
Wyliczanie pomocnika kierunku:
Klasa abstrakcyjna reprezentująca zlokalizowaną część „labiryntu”:
I wreszcie sam labirynt:
źródło
Rubinowy - Ogromny i zniszczony
Nieco naiwna implementacja, która brutalnie wymusza przejście przez labirynt. To nie jest super szybkie w niektórych (nie tak) dziwnych przypadkach. Można to poprawić, znajdując lepszą heurystykę niż tylko „jeśli jest bliżej skarbu, będziemy chcieli najpierw zbadać”, ale ogólne pomysły już istnieją.
Pokaże także, jak Indiana dostał skarb w razie potrzeby, to bonus.
Edycja: Zastanawiałem się nad sposobami, aby znacznie poprawić wydajność tego w nieoczywistych sytuacjach (gdzie obecnie ssie zielone jaja), rezygnując z prostej oceny ruchu (np. Dbam tylko o to, kiedy indy pcha skały i / lub dociera do skarbu). Prawdopodobnie zaktualizuję kod później, gdy będę miał czas na wdrożenie.
źródło
C ++ 14 z 16
Algorytm jest nieefektywny i wymaga pamięci. Dodatkowo nie mogłem sobie pozwolić na czas, aby to uporządkować, ale zrobię to, gdy będę miał więcej czasu;) Ciekawe jest to, że mój algorytm zawodzi na tych samych mapach testowych co pytający. Na moim starożytnym notatniku proces zaczyna się zamieniać na mapy T4 i T6. Mapa 3 trwa dość długo, ale jest rozwiązana w czasie. Wszystkie pozostałe są rozwiązywane niemal natychmiast. Więc muszę wymyślić, jak rozwiązać T4 i T6 i wypróbować algorytm na maszynie z większą pamięcią. W końcu mogę rozwiązać T4 i T6. Będę aktualizować wpis ...
Poniżej znajduje się wynik. (X: źle, O: dobrze,?: Trwa co najmniej 10 sekund, zatrzymany)
Ponieważ kod źródłowy jest dość długi i niezbyt przyjemny do odczytania ... Zasadniczo szuka on wszystkich kamieni, do których może dotrzeć Indiana Jones. W przypadku skał, do których można dotrzeć, przechowuje informacje, w które strony można je przenieść. Tak więc tworzona jest lista możliwych ruchów dla bieżącej mapy. Dla każdego z tych możliwych ruchów tworzona jest kopia mapy i ruch jest stosowany. W przypadku nowo utworzonych map algorytm ponownie sprawdzi, które ruchy można zastosować ... Robi się to do momentu, gdy nie będą możliwe dalsze ruchy lub nie dojdzie do drogi do skrzyni skarbów. Gdy algorytm najpierw próbuje wszystkich ruchów, które wymagałyby tylko jednego ruchu, aby dotrzeć do skrzyni, następnie wszystko, co zajęłoby dwa, i tak dalej ... pierwszy znaleziony sposób jest również automatycznie najkrótszy. Aby zapobiec pętlom, algorytm zapamiętuje dla każdej mapy, jakie ruchy można zastosować. Jeśli tworzona jest inna mapa, w wyniku której znajduje się lista ruchów, które zostały już wcześniej znalezione, są one po cichu usuwane, ponieważ są już przetwarzane. Niestety nie jest możliwe wykonanie każdego ruchu tylko raz, ponieważ mogą istnieć mapy, które wymagają kilkukrotnego przesunięcia skały nad tym samym polem. W przeciwnym razie mógłbym zaoszczędzić dużo pamięci. Dodatkowo, aby rozwiązać mapy takie jak mapa 3 w czasie, algorytm ignoruje wszystkie skały, po których można chodzić ... Więc na mapie 3 skała w środku nigdzie nie będzie się przemieszczać, ale tylko do momentu, gdy nie będzie wokół niej żadnych ścian. Kod można skompilować z g ++ --std = c ++ 0x z g ++ w wersji 4.4.3 lub nowszej. nie można wykonać każdego ruchu tylko raz, ponieważ mogą istnieć mapy, które wymagają kilkukrotnego przesunięcia skały nad tym samym polem. W przeciwnym razie mógłbym zaoszczędzić dużo pamięci. Dodatkowo, aby rozwiązać mapy takie jak mapa 3 w czasie, algorytm ignoruje wszystkie skały, po których można chodzić ... Więc na mapie 3 skała w środku nigdzie nie będzie się przemieszczać, ale tylko do momentu, gdy nie będzie wokół niej żadnych ścian. Kod można skompilować z g ++ --std = c ++ 0x z g ++ w wersji 4.4.3 lub nowszej. nie można wykonać każdego ruchu tylko raz, ponieważ mogą istnieć mapy, które wymagają kilkukrotnego przesunięcia skały nad tym samym polem. W przeciwnym razie mógłbym zaoszczędzić dużo pamięci. Dodatkowo, aby rozwiązać mapy takie jak mapa 3 w czasie, algorytm ignoruje wszystkie skały, po których można chodzić ... Więc na mapie 3 skała w środku nigdzie nie będzie się przemieszczać, ale tylko do momentu, gdy nie będzie wokół niej żadnych ścian. Kod można skompilować z g ++ --std = c ++ 0x z g ++ w wersji 4.4.3 lub nowszej. ale tylko dopóki nie będzie już wokół niego ścian. Kod można skompilować z g ++ --std = c ++ 0x z g ++ w wersji 4.4.3 lub nowszej. ale tylko dopóki nie będzie już wokół niego ścian. Kod można skompilować z g ++ --std = c ++ 0x z g ++ w wersji 4.4.3 lub nowszej.
Edycja: program pobiera dane ze standardowego wejścia i ignoruje pierwszy wiersz zawierający rozmiar mapy. Sprawdza, czy używane są tylko dozwolone postacie na mapie, ale nie sprawdza, czy jest tylko jedna Indiana Jones i jedna skrzynia skarbów. Możliwe jest więc umieszczenie więcej niż jednego, a najmniejsze ruchy wymagane do osiągnięcia jednej ze skrzyń są drukowane na standardowym ekranie. Wszelkie nieprawidłowe znaki na mapie są pomijane, a program spróbuje obliczyć najmniejszą liczbę ruchów dla wynikowej mapy. Obliczenia rozpoczną się po zamknięciu standardowego wejścia (w moim systemie ctrl + d).
źródło