Czas na kolejne wyzwanie labiryntowe, ale nie takie, jakie znasz.
Zasady tego wyzwania są nieco inne niż większość wyzwań w labiryncie. Typy kafelków są zdefiniowane w następujący sposób:
S: Lokalizacja w labiryncie, od której zaczynaszE: Lokalizacja, do której próbujesz się dostać0: Ściana, której nie można przekroczyć+: Podłoga, którą można przejść
Możesz podróżować w jednym z sześciu kierunków: góra-lewo, góra-prawo, lewo, prawo, dół-lewo lub dół-prawo.
\ /
-S-
/ \
Labirynt się nie zawija. Celem jest znalezienie najkrótszego ciągu ścieżki, z którego można przejść Sdo E.
Wkład:
Dane wejściowe to oddzielone spacjami linie, takie jak pokazane labirynty. Żadne końcowe miejsce nie będzie podążać za linią.
Wydajność:
Łańcuch R, Li Fgdzie
Robraca cię w prawo (zgodnie z ruchem wskazówek zegara) o 60 stopniLobraca w lewo (w lewo) o 60 stopniFprzesuwa cię o jedną spację w kierunku, który wskazujesz
Zaczynasz wskazywać left-up
Najkrótsza ścieżka jest liczona na podstawie długości wyprodukowanego ciągu, a nie liczby odwiedzonych pozycji. Twój program musi wydrukować najkrótszą ścieżkę jako rozwiązanie.
Jeśli labirynt jest nierozwiązywalny, powinieneś wyjść Invalid maze!.
( >>>to wynik)
0 0 0 0
0 + 0 + 0
0 0 0 + + 0
0 + 0 + 0 + 0
0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
E 0 + 0 0 + + 0
+ + 0 + 0 + 0
0 0 0 0 0 +
+ 0 + + +
0 S 0 0
>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
+ 0 0 0 0 0 0
0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
0 0 0 0 0 0 0 +
0 + 0 0 + + +
0 0 + + 0 0
S + 0 0 0
>>>Invalid maze!
0 E S
>>>LF
E + 0
0 + + +
0 0 S
+ +
>>>FFLF
E
0 +
0 + +
0 +
S
>>>RFFLFF
0 E + 0 0
0 + 0 0 + +
+ 0 + + + 0
+ 0 + 0 + 0
+ + + 0 S
>>>FFLFLFFRFRFFRFF
E 0 + + 0
0 + 0 + + 0
+ + + 0 + 0
+ 0 0 0 0 0
+ + + + 0
+ 0 S 0
>>>FLFFRFFRFLF
(Pamiętaj, że niektóre labirynty mają inne rozwiązania, które są tej samej długości, ale nie są tutaj wymienione)
źródło
Odpowiedzi:
Python 2, 291 bajtów
Funkcja,
fprzyjmująca labirynt jako listę wierszy i zwracająca rozwiązanie, jeśli takie istnieje.Wyjaśnienie
Wykonuje pierwsze wyszukiwanie na wykresie par pozycji / kierunku w celu znalezienia najkrótszej ścieżki od
SdoE.Interesujące jest znalezienie zwartego sposobu reprezentowania pozycji i kierunków na sześciokątnej siatce, który pozwala na proste „kroczenie” (tj. Poruszanie się w określonym kierunku) i obrót. Kuszące jest tutaj stosowanie liczb zespolonych do reprezentowania współrzędnych na „prawdziwej” siatce heksagonalnej, ale nie jest to bardzo dobry pomysł z wielu powodów, z których najpoważniejszym jest fakt, że musimy podłączyć √3 gdzieś, żeby to zadziałało (sin 60 ° = √3 / 2), co przy użyciu liczb zmiennoprzecinkowych nie jest możliwe, jeśli potrzebujemy absolutnej precyzji (np. do śledzenia stanów, które już odwiedziliśmy;) możesz spróbować uruchomić konsolę JavaScript i pisać
Math.sqrt(3)*Math.sqrt(3) == 3i przekonać się sam.Ale możemy użyć małej sztuczki! Zamiast używać liczb zespolonych, zdefiniujmy liczby heksagonalne w podobnej żyle, jako parę liczb rzeczywistych a + bh , gdzie h odgrywa podobną rolę do urojonej liczby i w przypadku liczb zespolonych. Podobnie jak w przypadku liczb zespolonych, możemy powiązać parę ( a , b ) z punktem na płaszczyźnie, w którym oś rzeczywista jest skierowana w prawo, oś urojona jest skierowana w górę o 60 ° i oba przecinają jednostkowy sześciokąt, gdy rzeczywista i części urojone wynoszą odpowiednio 1. Mapowanie tego układu współrzędnych do komórek labiryntu jest banalne.
W przeciwieństwie do i , stała h jest zdefiniowana przez relację h 2 = h - 1 (rozwiązanie dla h może ujawnić pewne spostrzeżenia.) I to wszystko! Numery sześciokątne mogą być dodawane i mnoży, wykorzystując powyższy związek, tak jak na liczbach zespolonych ( + bh ) + ( C + DH ) = ( + c ) + ( b + d ) H , oraz ( + bh ) · ( c + dh ) = ( ac - bd
) + ( ad + bc + bd ) h . Operacje te mają taką samą interpretację geometryczną jak ich złożone odpowiedniki: dodawanie to dodawanie wektora, a mnożenie to skalowanie i obrót. W szczególności, aby obrócić liczbę heksagonalną o 60 ° w kierunku przeciwnym do ruchu wskazówek zegara, mnożymy ją przez h :
( a + bh ) · h = - b + ( a + b ) h , a aby obrócić tę samą liczbę o 60 ° w prawo, dzielimy do godz . :
( a + bh ) / h = ( a +bh ) · (1 - h ) = (a + b) - ah . Na przykład, możemy wziąć jednostkową liczbę heksagonalną wskazującą w prawo, 1 = (1, 0), pełny okrąg, idąc w lewo, sześciokrotnie mnożąc go przez h :
(1, 0) · h = (0, 1 ); (0, 1) · h = (-1, 1); (-1, 1) · h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).
Program używa w ten sposób liczb heksagonalnych, aby przedstawić bieżącą pozycję w labiryncie i bieżący kierunek, aby przejść w określonym kierunku i obrócić kierunek w lewo i w prawo.
źródło
Sześciokąt , 2437 bajtów
Długo oczekiwany program jest tutaj:
Wypróbuj online!
Wersja „czytelna”:
Testowane na Esoteric IDE: TIO może przekroczyć limit czasu w niektórych większych przypadkach testowych, ale wszystkie zostaną zweryfikowane. Wielkie dzięki Timwi, nie byłoby to możliwe bez IDE.
Jest trochę pustej przestrzeni, więc mogłem zmieścić to na sześciokącie o długości boku 28 (zamiast boku o długości 29), ale będzie to ogromne zadanie, więc prawdopodobnie nie zamierzam tego robić.
Podstawowe objaśnienie
Kliknij obrazy, aby uzyskać większą i bardziej szczegółową wersję.
Funkcje
Uwaga: Podziały są ogólnie poprawne, ale czasami mogą być trudne do odgadnięcia.
Ten kod jest dość „funkcjonalny” - na tyle na ile pozwala na to Hexagony. W tym kodzie jest osiem głównych funkcji oznaczonych na powyższym schemacie, nazwanych liczbami, z którymi są wywoływane (więc ich numery wskaźników instrukcji to ta liczba mod 6). W (przybliżonej) kolejności wywoływania są to (cytowane nazwy to miejsca w pamięci, które zostaną wyjaśnione później):
F,RiLgotowy do głównej obróbki. Wskaźnik instrukcji 0 przesuwa się do funkcji 0, a wykonanie przechodzi do funkcji 1.+w ciągu 2 ruchów od pierwszego osiągnięcia. Powrót do funkcji 1.F. Powrót do funkcji 1.F,RalboLdodane. Powrót do funkcji 1.FFLF), A następnie kończy działanie programu.Invalid maze!i kończy.Pamięć
Uwaga: Jeszcze raz dzięki Esoteric IDE dla diagramu
Pamięć składa się z trzech głównych części:
0lub ważnego miejsca, które było dostępnego więcej ruchów temu niż byłoby wymagane, aby zakończyć się w dowolnym kierunku.+że jeszcze nie został osiągnięty.-1z pojedynczego-2po lewej, pozwala wskaźnikowi pamięci szybko wrócić do obszaru przetwarzania rdzenia.F,R,Ljak1,2,3odpowiednio-1s w prawo, a następnie wartość y w górę (chociaż y = 0 i tak jest przetwarzane jako 1 w celu oddzielenia szyny od danych odniesienia)Inne ważne lokalizacje pamięci:
E.źródło
Python 3, 466 bajtów
Prawdopodobnie skończyłby się mniej, gdybym użył wyszukiwania w głębokości lub czegoś takiego. Ta potworność używa Dijkstry i jest dość szybka, ale bardzo długa.
Kod definiuje funkcję,
Sktóra pobiera ciąg labiryntowy z labiryntu i zwraca wynik.Oto test kodu.
Nie golfił
źródło
L,,R.Groovy, 624 bajtów. Dziobowy!
Czas czas, aby piłka toczyła się z dużą. Pobiera ciąg wieloliniowy jako argument do
QWersja bez golfa:
źródło
C #,
600574 bajtówKompletny program, przyjmuje dane wejściowe z STDIN, dane wyjściowe do STDOUT.
Edycja: wystąpił błąd w obsłudze zawijania (nie zepsuł się w żadnym z podanych przypadków testowych), który dodałby 1 bajt, więc zrobiłem trochę golfa, aby to zrekompensować.
Zaczyna się od czytania na mapie, dołączania
(do każdej linii, aby wiedział, gdzie się kończy, i może wrócić i dodać mnóstwo spacji, aby mapa była prostokątna, oraz z rzędem spacji po prawej stronie (oszczędza to wykonujemy kontrole pakowania, jak wyjaśnimy poniżej). W pewnym momencie oblicza szerokość prostokąta i określa całkowitą długość mapy.Następnie inicjuje wszystko do pierwszego wyszukiwania szerokości. Tworzone są dwie duże tablice, jedna do przechowywania wszystkich stanów, które musimy zbadać w naszym wyszukiwaniu, druga do rejestrowania trasy, którą wybraliśmy się do każdego stanu. Stan początkowy jest dodawany do odpowiedniej tablicy, a wskaźniki głowy i ogona są wstępnie ustawione nieco powyżej. Wszystko ma indeks 1.
Następnie iterujemy, dopóki ogon nie uderzy w głowę, a przynajmniej wydaje się, że uderzył w głowę. Dla każdego stanu, który odwiedziliśmy, próbujemy dodać nowy stan w tym samym miejscu, w którym jesteśmy obracani w lewo lub w prawo, a następnie taki, w którym przesuwaliśmy się do przodu. Kierunki są indeksowane, a początkowy kierunek (domyślnie to
0) odpowiada „w górę w lewo”.Gdy próbujemy stanić w kolejce stan, jest on sprawdzany, ale nie jest sprawdzany zawijaniem, ze względu na kolumny spacji po prawej stronie, które są odbierane przez „czy możemy tu być?” sprawdź (nie możesz przebywać na spacjach). Jeśli stan jest w kolejce, sprawdzamy, czy znajduje się on w
Ekomórce, a jeśli tak, to ustawiamy, że głowa kolejki ma wartość minus sama, co powoduje zamknięcie głównej pętli i informuje ostatni wiersz programu, aby wydrukował poza odpowiednią trasę zamiast komunikatu o błędzie (który pokazuje, czy zabraknie stanów do rozwinięcia (ogon uderza w głowę).Podobnie jak większość moich Wyszukiwań Grafów na tej stronie, dobrze wykorzystuję struktury C #, które domyślnie porównują dosłownie.
źródło
Python 2, 703 bajty
Nie tak dobre jak pozostałe dwie wersje, ale przynajmniej działa haha. Ustaw
Msię w labiryncie.Ponieważ nie mam doświadczenia w rozwiązywaniu labiryntów, stosuje podejście oparte na brutalnej sile, w którym znajdzie wszystkie możliwe rozwiązania, które nie wymagają przekraczania samego siebie. Oblicza zakręty od najkrótszych, a następnie wybiera z nich najkrótszy wynik.
Brudna nie golfowa wersja:
źródło
if heading != required_heading: while heading != required_heading:tylkowhile heading != required_heading: