Uwaga: Historia opowiedziana w tym pytaniu jest całkowicie fikcyjna i wymyślona wyłącznie w celu wprowadzenia wstępu.
Mój szef ma nowego robota-zabawkę i chce, żebym pomógł go zaprogramować. Chce mieć możliwość wprowadzania prostych instrukcji strzałek, aby mógł się poruszać. Te instrukcje to: ^ (dla ruchu do przodu) <(dla skrętu w lewo) i> (dla skrętu w prawo). Jednak teraz, gdy zaprogramowałem robota, chce on dodatkowej funkcjonalności. Chce, żebym przekształcił dowolną sekwencję wprowadzanych przez siebie strzał, aby zamiast zmuszać robota do podążenia wskazaną ścieżką, przesuwa się on w pożądane miejsce, wskazane przez miejsce, w którym znalazłby się, gdyby wybrał wprowadzoną ścieżkę, równie skutecznie jak możliwy. Apeluję do was, członków PP&CG, o pomoc w tym zadaniu.
Twoje zadanie:
Napisz program lub funkcję, aby przekonwertować ciąg złożony ze strzałek na ciąg, który dotrze do miejsca wskazanego przez dane wejściowe tak szybko, jak to możliwe. Obracanie zajmuje tyle samo czasu, co cofanie lub przewijanie do przodu.
Wkład:
Ciąg strzałek, jak wskazano powyżej. Jeśli chcesz, różne postacie mogą być zastąpione strzałkami, ale pamiętaj, aby uwzględnić to w swojej odpowiedzi. Wszystkie przypadki testowe używają strzałek normalnie.
Wydajność:
Ciąg strzałek (lub ich odpowiedników), które prowadzą robota do wybranego miejsca docelowego tak skutecznie, jak to możliwe.
Przypadki testowe:
Pamiętaj, że oferowane rozwiązania są tylko możliwościami i że inne rozwiązania mogą być ważne.
>^<<^^>^^ -> ^^<^
^^^^>^^^^ -> ^^^^>^^^^
>>>^^^^^^ -> <^^^^^^
>^>^>^>^ -> (empty string)
^<^^<^^<^^^^ -> >^^>^
Punktacja:
Pamięć robota jest ograniczona, więc twój program musi mieć możliwie najmniejszą liczbę bajtów.
źródło
^<^^<^^<^^^^
->>^^>^
?Odpowiedzi:
Retina ,
1037471 bajtówWypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:
Skręć w lewo, w trzykrotne w prawo.
Zmniejsz wszystkie obroty modulo 4.
Anuluj ruchy w przeciwnych kierunkach.
Skręć trzykrotnie w prawo z powrotem w skręt w lewo. Dotyczy to również przypadku,
>>^>^
który musi się stać<^<^
.Usuń niepotrzebne zakręty końcowe.
źródło
Mathematica, 135 bajtów
Pobiera
List
ciągi jako dane wejściowe.Wyjaśnienie
Ustaw
j
na 0 i ustawi
na 1.Dla każdego wprowadzanego znaku ...
Jeśli postać jest
>
, pomnóżi
przez jednostkę urojoną. Jeśli postać jest>
, podzieli
przez jednostkę urojoną. Jeśli postać jest^
, dodaji
doj
.Weź prawdziwe i wymyślone części
j
. Daje to kartezjańską współrzędną robota.Zastosuj następujące do tego wyniku:
Ustaw
a
do funkcji, która generuje ciąg z(input)
lub0
znak^
s, w zależności co jest większe.List
Składający się z ...a
zastosowane do pierwszego wejścia (część rzeczywistaj
)Jeżeli drugie wejście (urojonej
j
) jest większa niż0
,>
. W przeciwnym razie<
. Ustaws
wynikowy znak.a
stosowane do wartości bezwzględnej drugiego wejścia.Jeśli pierwsze wejście jest mniejsze niż 0
s
,. W przeciwnym razie pusty ciąg.Zastosuj
a
do czasów wejściowych ujemnych.Dołącz do strun.
źródło
Mathematica 119 bajtów
Ostateczna pozycja JungHwana do kodu ścieżki była krótsza niż moja, więc używając tego. Myślę, że istnieje prawdopodobnie jeszcze krótszy sposób, aby to zrobić ...
Używam wbudowanej
AnglePath
funkcji do decydowania o ostatecznej pozycji. Definiuję również symbole L, F i R dla „<”, „^” i „>”, aby zapisać kilka znaków cudzysłowu.Stosowanie:
Wydajność:
źródło
Rubinowy , 130 bajtów
Jak to działa
Wypróbuj online!
źródło
J, 90 bajtów
rozwiązanie
wyjaśnienie
fajna sztuczka polega na użyciu liczb zespolonych (pomnożenie przez i to obrót w lewo o 90 stopni, a -i daje prawą).
więc bierzemy nasze dane wejściowe jako liczby zespolone: 1 oznacza „iść naprzód”, a i / -i reprezentuje skręt w lewo i w prawo.
pozycja końcowa jest obliczana bez wysiłku dzięki tej reprezentacji. Zauważ, że jest to pierwsza (skrajnie prawa) część mojego ostatniego wyrażenia powyżej:
Ta krótka linia powyżej rozwiązuje problem. Cała reszta zastanawia się, jak sformatować odpowiedź, i na pewno można by ją znacznie pograć.
Aby zrozumieć powyższą krótką linię, zwróć uwagę, że
*/\
(skan produktów częściowych) daje listę pozycji, na które patrzysz przy każdym indeksie na wejściu: i to północ, 1 i -1 to wschód i zachód, a -i to południe . Ale odkąd zaczynamy patrzeć na północ, musimy pomnożyć je wszystkie i, które w J jest reprezentowane przezj.
(żuć to zdanie przez chwilę).Mamy tylko faktycznie „ruch”, gdy oryginalne wejście jest 1, więc następnie pomnożyć wynik przez elementwise tablicy logicznej, która wynosi 1, gdzie oryginalne wejście jest 1 i 0 w przeciwnym przypadku:
=&1*
. Wynik tego zwielokrotnienia jest tablica „kroków kierunkowych”. Nasza ostateczna pozycja to po prostu suma tych kroków:+/
testowanie
Niestety z jakiegoś powodu nie mogę tego uruchomić w TIO, ale wklejenie następujących poleceń w konsoli J sprawdzi, czy to działa:
źródło
C # (.NET Core) , 349 bajtów
Wypróbuj online!
Pobiera ciąg znaków jako dane wejściowe i wyprowadza najkrótszą ścieżkę, jaką wybrałby sygnał wejściowy.
Niegolfowane i komentowane
źródło
JavaScript (Node.js) , 187 bajtów
Wypróbuj online!
Wersja golfowa z białymi spacjami
-14 bajtów przez @Neil
Nie golfowany:
źródło
t&3
zamiast,t%4
ponieważ działa to z przeczeniem,t
więc możesz usunąć4+
i()
.(x?"":t)+t
można zapisać w(x?t:t+t)
celu zaoszczędzenia 1 bajtu. Kod zmieniający kierunek wygląda o wiele za długo. Myślę też, że powinieneś prawdopodobnie zastąpićindexOf
iMath.abs
porównać.indexOf
przez porównanie?t-=b=c<'>'||-(c<'^')
.Python 2 ,
174169165 bajtówEdytuj bajty 1: -5, pozostawiając kierunek poza zakresem 0-3 i usuwając białe znaki.
Edytuj 2: -4 bajty, zmieniając dane wejściowe na (1, 2, 3) zamiast (<, ^,>), ponieważ PO na to pozwala, a także zmieniając mój układ współrzędnych, aby umożliwić mi zmniejszenie obliczeń odległości.
Wypróbuj online!
Określa końcowe współrzędne na podstawie wykonywanych wartości słownika, a następnie drukuje bezpośrednią ścieżkę do celu końcowego.
źródło
Perl 5 , 185 + 1 (-p) = 186 bajtów
Wypróbuj online!
źródło
JavaScript (rodzaj document.getElementById ()), 343 znaków
rozszerzony:
}
Stosowanie:
alerty:
>^^>^
Przydałby się robot z cofaniem.
źródło