Mrówka chodzi wzdłuż krawędzi (nie ścian) sześcianu szkieletowego. Każdy napotkany wierzchołek przedstawia widelec, z którego rozgałęziają się dwie nowe krawędzie. Mrówka wybiera, w którą stronę skręcić - left
lub right
. Kierunki te odnoszą się do mrówki, która jest zwrócona do wierzchołka i znajduje się poza sześcianem. Twoim celem jest ustalenie, na podstawie sekwencji left
/ right
wyborów, które wybrał mrówka, czy kończy się w tej samej pozycji, w której się zaczął.
Na przykład, jeśli mrówka skręci w lewo cztery razy ( left left left left
), przejdzie kwadrat o kierunku przeciwnym do ruchu wskazówek zegara i skończy w tym samym miejscu, w którym zaczął. Ale jeśli przejdzie left left left left right
, skończy się w innym miejscu na kostce. Ponadto, jeśli przejdzie left right right right left
, kończy się na krawędzi początkowej, ale jest skierowany w stronę przeciwnego wierzchołka, co nie jest liczone jako ta sama pozycja.
Ścieżka mrówki może powtarzać krawędzie, w tym krawędź, od której zaczyna, ale ważne jest, gdzie kończy się po całej sekwencji.
Napisz nazwaną funkcję, która pobiera sekwencję zwojów mrówki i podaje, czy mrówka powraca do pozycji początkowej po sekwencji. Przypisanie funkcji bez nazwy do zmiennej wystarczy, aby uczynić ją funkcją o nazwie.
(Edycja: jeśli Twój język nie może utworzyć nazwanej funkcji, może zamiast tego zaimplementować funkcję z wejściami i wyjściami poprzez STDIN / drukowanie lub stos. Jeśli nie jest to możliwe, uczyń z niego fragment kodu, w którym dane wejściowe i wyjściowe są zapisywane w zmienne).
Wkład
Sekwencja left
/ right
decyzji długości 0
do 31
włączenia, reprezentowana w wybranym formacie. Może to być ciąg liter R
/ L
, lista cyfr 1
/ -1
lub tablica boolean. Nic tak tandetnego jak to, że są to nazwy metod lub ciągi znaków przydatne w kodzie.
Prześlij przypadki testowe w swoim formacie, jeśli różnią się one od poniższych przypadków testowych.
Wydajność
True
/ False
, 0
/ 1
lub analogi w twoim języku.
Kryteria wygranej
Wygrywa najmniej bajtów. Pamiętaj, że musisz podać nazwaną funkcję. Możesz mieć kod poza funkcją, ale te bajty też się liczą. Twoja funkcja powinna działać poprawnie, jeśli zostanie wywołana wiele razy.
Przypadki testowe
True
przypadki (jedna na linię, druga to pusta lista):
1 1 1 1
-1 -1 -1 -1
1 -1 1 -1 1 -1
1 1 -1 -1 1 1 -1 -1
-1 1 1 -1 -1 1 1 -1
1 1 1 -1 -1 -1 -1 1
1 -1 -1 1 -1 -1
1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1
-1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
False
etui (jeden na linię):
1
1 1
1 1 1
-1 1
1 -1 -1 -1 1
1 -1 -1 1 1
-1 1 -1 1
1 1 1 1 -1
-1 -1 1 -1 1 -1 -1 1
1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 -1
Oto te same przypadki testowe z L
's R
' i 's.
True
przypadki:
RRRR
LLLL
RLRLRL
RRLLRRLL
LRRLLRRL
RRRLLLLR
RLLRLL
RRRRLLLLRLLRLL
LLLRLLRRLRLRRRRRRRRRRRRRRRRR
False
przypadki:
R
RR
RRR
LR
RLLLR
RLLRR
LRLR
RRRRL
LLRLRLLR
RLRRRRLLLRRLLL
Dodatkowe wyzwanie kredytowe
To samo, ale z dwunastościanem zamiast sześcianu. Zobacz pomysły Hunt the Wumpus .
Odpowiedzi:
GolfScript, 24 znaki (19 tylko dla treści funkcji)
Matematyka FTW!
Przetestuj to rozwiązanie online.
Ta funkcja przyjmuje jako dane wejściowe tablicę binarną (0 dla lewej, 1 dla prawej) i zwraca 1 dla wartości true i 0 dla wartości false.
Koncepcyjnie działa on poprzez obracanie sześcianu, tak aby mrówka zawsze zachowywała tę samą pozycję i orientację oraz sprawdzanie, czy kostka ostatecznie kończy się w tej samej orientacji, w jakiej się rozpoczęła.
W szczególności możemy przedstawić skręt w lewo i w prawo jako dwie mapy liniowe w trzech wymiarach, przy czym skręt w lewo odpowiada obrotowi o 90 ° wokół osi x , tj. Mapie ( x , y , z ) → ( x , z , - y ), a zwrot w prawo odpowiada obrotowi o 90 ° wokół osi y , tj. Mapa ( x , y , z ) → ( z , y , - x ).
Na początku funkcji po prostu ustawiamy trzyelementowy wektor zawierający wyraźne wartości dodatnie (1, 2, 3), stosujemy do niego sekwencję map obrotu i sprawdzamy, czy wektor wynikowy jest równy wektorowi początkowemu.
(W rzeczywistości, aby zapisać kilka znaków, faktycznie transformuję współrzędne, aby wektor początkowy to (0, 1, 2), a mapy to ( x , y , z ) → ( x , z , −1− y ) i ( x , y , z ) → ( z , y , −1− x ), ale wynik końcowy jest taki sam.)
Ps. Dzięki dumnemu haskellerowi za wykrycie błędu w oryginalnej wersji tego rozwiązania.
Perl, 58 znaków
Zgodnie z żądaniem w komentarzach, oto to samo rozwiązanie przeniesione do Perla. (Ta wersja faktycznie używa nietransformowanych współrzędnych, ponieważ transformacja nie zapisuje znaków w Perlu).
Przetestuj to rozwiązanie online.
Bonus: Mrówka na dwunastościanie (GolfScript, 26 znaków)
Przetestuj to rozwiązanie online.
Podobnie jak powyższa funkcja ant-on-a-cube, ta funkcja przyjmuje jako dane wejściowe tablicę binarną (0 dla lewej, 1 dla prawej) i zwraca 1, jeśli mrówka znajdzie się w tej samej pozycji i orientacji, w jakiej się rozpoczęła, lub 0 Inaczej.
To rozwiązanie wykorzystuje nieco bardziej abstrakcyjną reprezentację niż rozwiązanie kostki powyżej. W szczególności, wykorzystuje się fakt, że obrotowa grupa symetrii dwunastościanu jest izomorficzny z grupy zmiennego A 5 , czyli grupa nawet permutacji pięciu elementów. Zatem każdy możliwy obrót dwunastościanu (który odwzorowuje krawędzie na krawędzie, a wierzchołki na wierzchołki) można jednoznacznie przedstawić jako permutację tablicy pięcioelementowej, z kolejnymi obrotami odpowiadającymi stosowaniu odpowiednich permutacji w sekwencji.
Zatem wszystko, co musimy zrobić, to znaleźć dwie kombinacje L i R, które mogą reprezentować lewy i prawy obrót. W szczególności permutacje te muszą mieć 5 cykli (tak, aby ich zastosowanie pięć razy powróciło do stanu pierwotnego), nie mogą być wzajemnymi potęgami (tj. R ≠ L n dla dowolnego n ) i muszą spełniać relację ( LR ) 5 = (1), gdzie (1) oznacza permutację tożsamości. (W efekcie to kryterium stwierdza, że ścieżka
LRLRLRLRLR
musi wrócić do pierwotnej pozycji).Ustalenie, że permutacja L jest prostym przesunięciem lufy w lewo, tj. Mapowaniem ( a , b , c , d , e ) → ( b , c , d , e , a ), ponieważ można ją zaimplementować w GolfScript w zaledwie dwóch chars (
(+
), okazuje się, że istnieje pięć możliwych wyborów dla permutacji R. Spośród nich wybrałem mapowanie ( a , b , c , d , e ) → ( c , e , d ,b , a ), ponieważ ma również stosunkowo kompaktową implementację GolfScript. (W rzeczywistości implementuję go, najpierw przeplatając elementy w2*2%
celu uzyskania ( a , c , e , b , d ), a następnie zamieniając ostatnie dwa elementy za pomocą[~\]
, a na koniec bezwarunkowo stosując permutację L, aby przesunąć a na koniec.)Powyższy link demonstracyjny online zawiera niektóre przypadki testowe prawidłowych ścieżek na dwunastościanie, które powracają do źródła, takie jak:
źródło
{[~@]-1%}*[~@]
lub){[~@]-1%}*-1%
zastąpienie twojego{2*2%[~\]}*(+
Python, 68
Pobiera listę 1 i -1. Na podstawie obrotów 3D: sprawdza, czy punkt (3,2,1) kończy się w tej samej pozycji po zastosowaniu serii obrotów. Możliwe są dwa obroty, odpowiadające 1 i -1. Każda z nich odbywa się poprzez permutację dwóch współrzędnych i zmianę znaku jednej z nich. Dokładne współrzędne, które należy zmienić, i który znak do permutacji nie jest ważny.
EDYCJA: w rzeczywistości jest to w większości to samo rozwiązanie, co „Perl, 58”.
źródło
p
na osobną zmienną.Matematyka
Zainspirowany rozwiązaniem Ilmari Karonen. Grupa symetrii rotacyjnej sześcianu jest izomorficzna do S 4 .
Kostka, 51 bajtów
Pobiera listę
1
s i-1
s jako dane wejściowe.Wypróbuj online!
Dwunastościan, 55 bajtów
Pobiera listę
1
s i-1
s jako dane wejściowe.Wypróbuj online!
źródło
C (gcc) ,
118116107105 bajtów-2 bajty dzięki pułapkowi cat
Wypróbuj online!
Załóżmy, że podaliśmy sześcianowi następujące współrzędne:
Jeśli zaczniemy od rogu D, wówczas przejście do C lub H można uznać za obracanie wokół nas sześcianu. Przesunięcie w prawo oznaczałoby obrót w lewo wokół osi Z, a przesunięcie w lewo oznaczałoby obrót w kierunku wokół osi X. To jedyne dwie rotacje, o które musimy dbać. Ponieważ każdy obrót wynosi dokładnie 90 stopni, możemy sobie wyobrazić, że rogi „ślizgają się” wzdłuż krawędzi. Przesunięcie w prawo oznacza A -> B, B -> C, C -> D, D -> A z drugą stroną wykonującą E -> F itp. Za przesunięcie w lewo otrzymujemy A -> E, E - > H itp.
Ponieważ każdy narożnik przesuwa się tylko wzdłuż krawędzi, oznacza to, że tylko jeden z wymiarów każdego punktu zmienia się dla każdego obrotu. Kiedy B przesuwa się do C, zmienia się tylko jego składnik y, a gdy H przechodzi do D, zmienia się tylko jego składnik z i tak dalej. Ponadto, ponieważ współrzędne są ograniczone do 0 i 1, możemy myśleć o każdym punkcie jako liczbie binarnej, z odpowiednim bitem odwracanym podczas ruchu.
Widzimy, że dla ruchu w prawo A i C odwracają swoje x, podczas gdy D i B odwracają swoje y. Jeśli zmienimy perspektywę, aby spojrzeć na tę stronę głowicy sześcianu i zignorujemy komponent Z (który i tak nie zmienia się dla tego obrotu), otrzymujemy:
Pojawia się wzorzec: dla punktów, które odwracają swoje x, x == y, podczas gdy odwrotnie jest w przypadku punktów odwracających ich y. Dotyczy to innego rodzaju obrotu, ale z z zamiast x.
Innymi słowy:
Teraz możemy łatwo przejść przez wszystkie obroty, a na końcu sprawdzić, czy końcowe D pasuje do naszego początkowego D.
Przechowywanie każdego punktu jako pojedynczej liczby jest dane, ale w C przypisywanie tablicy znaków jest o wiele bardziej zwarte niż tablicy int. Staramy się wybierać znaki, których trzy niższe bity pasują do 000..111, dzięki czemu można po prostu zignorować resztę bitów. Odwracanie współrzędnych jest po prostu kwestią XOR'ingu z odpowiednią maską bitową.
źródło
Python - 110, 150
Pobiera listę liczb całkowitych z
-1
dla skrętu w lewo,1
dla skrętu w prawo.Kostka, 110:
Test:
Dwunastościan, 150:
źródło
Cudowny 188
Bezwstydna kradzież algorytmu Ilmari Karonen w celu pokazania nowego języka.
Ten skrypt oczekuje ciągu 0x00 dla lewego i 0x01 dla prawego na standardowym wejściu, a po nim 0x0A (nowa linia). Zwraca „0” w przypadku niepowodzenia i „1” w przypadku powodzenia.
przykładowy bieg:
źródło
Python 2 , 57 bajtów
Wypróbuj online!
Używa reprezentacji permutacji
gdzie lewa i prawa (0 i 1) odpowiadają długości 4 cykli na 4 elementach. Iterujemy nad wejściem stosując wskazaną permutację i sprawdzamy, czy wynik jest równy wartości początkowej.
Zaczynamy
a,b,c,d
jako lista czterech elementów0,1,2,3
. Kompresujemy je do pojedynczej liczby base-4n=abcd
, z wartością początkowąn=27
odpowiadającą0123
podstawie base 4. Instytujemy każdą kombinację na arytmetycznien
.Ponieważ oba wyniki zaczynają się od
d
, możemy zrobić,n%4
aby wyodrębnićd
, a następnien%4*64
przenieść go do właściwej pozycjid___
. Pozostałe cyfry sąabc
wyodrębniane jakon/4
. Musimy wstawić je do trzech niższych wartości miejsca.Dla kierunku
x=0
wstawiamyabc
jak jest, a dlax=1
obracamy je jakcab
. Ruch obrotowy może zostać osiągnięta*16%63
, co odbywaabc
sięabc00
nacab
. (Mogłoby%63
to pójść nie taka==b==c==3
, ale te wartości nie są możliwe.) Ponieważ samo działanie%63
jest zabronione, wyrażenie zależne od kierunku*16**x%63
dajeabc
lubcab
jest wymagane.Python 2 , 55 bajtów
Wypróbuj online!
źródło
Haskell,
104103999796/6764 znakówWydaje mi się, że odpowiednikiem prawej / lewej strony byłby typ danych Kierunek taki:więc w mojej odpowiedzi założyłem, że były one dostępne.edycja: faktycznie zdałem sobie sprawę, że booleany doprowadziłyby do skrócenia kodu. Prawda reprezentuje zwrot w lewo, a False reprezentuje zwrot w prawo (chociaż technicznie kod działałby tak samo, gdyby został odwrócony; jest symetryczny)
96 znaków:
g to funkcja, która po podaniu listy Kierunków zwraca pogodę, w której mrówka nie wróciła na swoje miejsce.
wyjaśnienie reprezentacji pozycji: pozycja mrówki jest kodowana jako trzy krotki liczb całkowitych. pierwsza liczba całkowita reprezentuje wierzchołek, do którego zmierza mrówka. pierwszy bit oznacza, czy wierzchołek znajduje się w połowie góra / dół, drugi - lewa / prawa połowa, a trzeci - tylna / przednia połowa. Odbywa się to tak, że przejście od wierzchołka do sąsiedniego wierzchołka można wykonać, odwracając jeden bit.
druga liczba całkowita to kwota, którą zmieniłby wierzchołek mrówki, gdyby poszedł w lewo. na przykład, jeśli mrówka znajdowała się na wierzchołku 3, a druga liczba całkowita wynosiła 4, to po skręceniu w lewo wierzchołek wynosiłby 7. zauważ, że zawsze będzie to potęga 2, ponieważ dokładnie jeden bit jest odwracany przez przesunięcie jednego wierzchołka.
trzecia liczba całkowita jest taka sama, ale dla poprawności; wiem, że można to obliczyć na podstawie pierwszych dwóch, ale nie wiem, jak to zrobić. jeśli masz pomysł, proszę powiedz mi.
należy zauważyć, że przy skręcie w lewo trzecia liczba całkowita pozostanie taka sama, a druga stanie się liczbą między 1 2 a 4, która nie będzie ani drugą liczbą całkowitą, ani trzecią, co może być takie samo jak 7 - druga liczba całkowita - trzecia liczba całkowita.
Wybrałem ten sposób reprezentowania pozycji, ponieważ (jak właśnie stwierdzono w poprzednim akapicie) obliczenie następnej pozycji było banalne.
objaśnienie funkcji:
funkcja (%) to funkcja, która pobiera bieżący wierzchołek i kwotę, aby go zmienić, i zmienia go. dochodzi do bitu, który ma się zmienić i odwraca go (w sposób bardzo liczbowy).
funkcja m jest funkcją, która przyjmuje pozycję mrówki i kierunek oraz zwraca nową pozycję za pomocą nuty, którą zanotowaliśmy wcześniej.
następnie funkcja m jest łączona za pomocą foldl (co jest trochę jak
reduce
w javascript, ale nieco bardziej wyraziste), aby utworzyć funkcję g, odpowiedź na to pytanie.Haskell, 64 znaków
zainspirowany odpowiedzią @ alphaalpha, oto jej wersja przeniesiona do haskell:
edytuj:
Czuję się teraz niesamowicie głupio z powodu odpowiedzi Lari Karonena. może prześlę jego odpowiedź do haskell.kolejna edycja: nie czuć się tak głupio, jak jego odpowiedźjestbłędnaedycja: zmieniłem się z używania krotek na używanie list jako ich
Ord
instancji, a[ ... ]
cukier składniowy skraca toźródło
[0,1,2,3]
do zmiennej i użyć jej zarówno jako danych wejściowych do wyrażenia, jak i do sprawdzania wyniku?[0..3]
... Nie wiem, dlaczego wcześniej tego nie zauważyłem. dzięki. ale teraz twoja sztuczka nie działa. No cóż.Haskell , 53 bajty
Wypróbuj online!
Ta sama logika, co moja odpowiedź w Pythonie , nawet myślała
mod
idiv
jest już dłużej pisać.Haskell , 58 bajtów
Wypróbuj online!
źródło
APL (Dyalog Unicode) , 22 bajty ( Adám's SBCS )
Wypróbuj online!
H.PWiz zasugerował, że odwrócenie kroków nie robi różnicy, a to spowodowało -2 bajty.
Cóż, jest to zawstydzające, ponieważ miało być znacznie krótsze niż GolfScript. Przynajmniej próbowałem.
Funkcja ma nazwę
f
, aw przypadkach testowych1
reprezentuje zwrot w lewo (boolean true) i0
reprezentuje zwrot w prawo (boolean false).⍬
reprezentuje pustą listę.źródło
APL (Dyalog) , 21 bajtów
Wypróbuj online! (Przy użyciu środowisku testowym z Eryk Outgolfer za odpowiedzi )
Biorę lewo i prawo jak
1
i2
. Wykorzystuje to następujące permutacjeabcd
:I stosuje się permutacje odpowiadające
1
i2
do⍳4 : 1 2 3 4
, i sprawdzić, czy jest niezmienionaźródło
Bash ,
7165 bajtówWypróbuj online!
Podobnie jak wiele poprzednich odpowiedzi, wykorzystuje reprezentację grupy obrotów sześcianu wygenerowanych przez 1234-> 4123 i 1234-> 4312. Używa liczb zamiast liter, dzięki czemu mogę użyć operatora trójskładnikowego z rozszerzeniem arytmetycznym. Oczekuje, że dane wejściowe będą składać się z zer i jedynek oddzielonych spacjami, a dane wyjściowe za pomocą kodu wyjścia.
6 bajtów zapisanych dzięki komentarzowi @ manatwork!
źródło
pieprzenie mózgu , 119 bajtów, 137 bajtów
Kostka, 119 bajtów
Wypróbuj online!
Dwunastościan, 137 bajtów
Wypróbuj online!
Jedyne różnice między tymi dwoma programami to konfiguracja i permutacje. Zastosowano tutaj lewą permutację
DCAEB
, która wydawała się być najbardziej dostępnym sprzężeniem golfowym.źródło
Galaretka , 14 bajtów
Wypróbuj online!
1
= skręt w lewo,0
= skręt w prawo. Na podstawie mojego rozwiązania Dyalog.Niestety, Jelly nie ma nazwanych funkcji. Jeśli nie mogę użyć niejawnego wejścia i muszę założyć, że jest to zmienna, ta wersja tej samej długości wykona:
Zakłada, że wejście znajduje się w rejestrze (© / ®).
źródło
Perl - 120, 214
Pobiera tablicę (listę) wartości logicznych.
Kostka (120):
Dwunastościan (214):
źródło