Wyobraźmy sobie ścieżkę złożoną z <i >a kończąc w sposób @, na przykład
><>@
Walker zaczyna się w lewej komórce. Przemierza ścieżkę w następujący sposób:
- Jeśli piechur jest w
@celi, osiągnął cel i jest skończony. - Jeśli chodzik znajduje się w
>komórce, cała ścieżka przesuwa się o jeden krok w prawo, cyklicznie, zabierając go ze sobą . - Jeśli chodzik znajduje się w
<komórce, cała ścieżka przesuwa się o krok w lewo, cyklicznie, zabierając go ze sobą . - Następnie piechur robi jeden krok. Jeśli jest na dowolnym końcu ścieżki, odsuwa się od końca. W przeciwnym razie porusza się w kierunku, w którym poruszał się na ostatnim stopniu (ignorując obrót), początkowo idąc w prawo.
Przeanalizujmy powyższy przykład. Pozycja spacerowicza jest oznaczona ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
Walker odwiedził 6 komórek w tym procesie (w tym komórkę początkową, a także @i zliczając każdą komórkę tak często, jak jest odwiedzana).
Oto mały przykład, w którym chodzik jest transportowany przez krawędzie poprzez obrót:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
Tym razem piechur odwiedził 3 komórki.
Możemy łatwo przekształcić to w ciąg liczb całkowitych:
- Otrzymujesz dodatnią liczbę całkowitą N , np
9. - Obliczasz binarną reprezentację tej liczby całkowitej, np
1001. - Następnie skręcić
1na>i0pod<oraz załączyć@:><<>@. - Kojarzymy z N liczbę komórek odwiedzonych przez piechura w liczbie zbudowanej w ten sposób.
Pierwsze kilka elementów wynikowej sekwencji to:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Może się to wydawać dość arbitralne, ale wynikowa sekwencja okazuje się mieć wiele struktur:
W celach informacyjnych można znaleźć pierwsze 2048 numerów sekwencji w tym pastebinie .
Wyzwanie
Zgadłeś: musisz obliczyć powyższą sekwencję. Możesz to zrobić na jeden z trzech sposobów:
- Możesz stworzyć nieskończoną sekwencję (o ile pozwala na to pamięć), albo przez ciągłe wyprowadzanie (oddzielone znakami nienumerycznymi) wartości, albo przez użycie jakiejś formy nieskończonego generatora w językach, które je obsługują. Jeśli drukujesz nieskończony strumień do STDOUT, nie musisz drukować liczb jeden po drugim, ale upewnij się, że każda liczba zostanie wydrukowana po skończonym czasie (i w kolejności). Jeśli skorzystasz z tej opcji, nie powinieneś przyjmować żadnych danych wejściowych.
- Możesz wziąć liczbę całkowitą N jako dane wejściowe i wygenerować N- ty ciąg sekwencji.
- Można wziąć całkowitą N jako wejście i produkować wszystko do tej N th określenie sekwencji, albo jako listy lub łańcucha za pomocą jednoznacznego separator.
Ponieważ nie chcę karać języków, które nie mogą łatwo przekonwertować między bazami, zamiast liczby całkowitej N możesz zamiast tego wziąć binarną reprezentację N , używając 0s i 1s jak zwykle (jako listy lub łańcucha), z największą liczbą - znaczący bit pierwszy.
Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).
Obowiązują standardowe zasady gry w golfa .
tło
To faktycznie oblicza liczbę „tyknięć”, które prosty interpreter mojego ezoterycznego języka programowania, Labiryntu, musiałby interpretować „ścieżkę” jako kod źródłowy. W takim przypadku „walker” jest po prostu wskaźnikiem instrukcji (który ma pozycję i kierunek), @polecenie kończy program <i >jest poleceniem modyfikacji kodu źródłowego.
Odpowiedzi:
Galaretka , 10 bajtów
Ta funkcja przyjmuje jako liczbę wejściową jedną liczbę całkowitą w postaci listy cyfr binarnych.
Algorytm jest równoważny z algorytmem z odpowiedzi @ Agawa001 .
Wypróbuj online! lub wygeneruj pierwsze 2048 liczb .
tło
Wymień pozycje pod ścieżką od 0 do L , dając w sumie pozycje L + 1 . L pokrywa się z liczbą cyfr binarnych liczby N, która koduje ścieżkę. Przy tym zapisie Walker rozpoczyna się w pozycji 0 , gola w pozycji L .
Z każdym krokiem, który idzie piechur, zbliża się o jeden krok do celu (w kierunku, w którym aktualnie idzie). Ponadto, z każdym krokiem zmiany, w zależności od tego, czy idzie z kierunkiem zmiany kierunku, czy przeciwnie, albo zwiększa lub zmniejsza swoją pozycję o 2 modulo L + 1 , albo pozostaje w aktualnej pozycji.
Aby zmienić kierunek, musi wylądować na pozycji L - 1 (przodem do L ) lub pozycji 1 (przodem do 0 ), a następnie przesunąć się w jego kierunku. Następny krok, który zrobi, przywróci go do poprzedniej pozycji, w przeciwnym kierunku.
Jeśli L jest parzysty, L - 1 jest nieparzysty, więc nie może przejść bezpośrednio z początkowej pozycji do L - 1 bezpośrednio. Jedynym sposobem na dotarcie do niego jest przejście przez L , doprowadzenie do zera i wykonanie następnego kroku, aby wylądować na 1 , a następnie przejść w prawo. Wymaga to przesunięcia pozycji o wartości 2L , co można zrobić w nie mniej niż L. krokach.
Jednak po wykonaniu kroków L bez zmiany kierunku osiągnie cel. Dodając jedną do komórki początkowej, otrzymujemy w tym przypadku łącznie L + 1 odwiedzonych komórek.
Jeśli L jest nieparzysty, L - 1 jest parzysty, więc może osiągnąć tę pozycję, przesuwając się (L - 1) / 2 razy w prawo. Jeśli pozycja L - 1 znajduje się pod 1 w tym czasie, zostanie przesunięty do pozycji L , zawróci i wejdzie na pozycję L - 1 (skierowaną w lewo).
Może się to zdarzyć, zanim osiągnie swój cel, dlatego należy przeanalizować dwa przypadki:
Jeśli wystąpi mniej niż (L + 1) / 2 wystąpień 1 w binarnym rozwinięciu N , wykonanie L kroków nie wystarczy, aby obrócić kierunek. Ponieważ te kroki L doprowadzają piechura do jego celu, dodając jeden do komórki początkowej, w tym przypadku otrzymujemy w sumie L + 1 odwiedzonych komórek.
Jeśli w binarnym rozszerzeniu N występuje co najmniej (L + 1) / 2 wystąpienia 1 , przejście do ((L + 1) / 2) tego wystąpienia będzie wymagało I kroków, gdzie I jest początkową pozycją tego wystąpienia z 1 .
Tak więc, po zrobieniu I kroków, chodzik znajduje się w pozycji L - 1 , twarzą w lewo. Aby ponownie skręcić w kierunki, musiałby iść do przodu w lewo do pozycji 1 . Jednak, podobnie jak w przypadku nawet, ponieważ (L - 1) - 1 jest nieparzysta, to będzie wymagało przeżywa 0 i nie mniej biorąc tha L kroki.
Ponieważ początkowa odległość do bramki w lewym kierunku wynosi 1 , po zrobieniu I kroków piechur po zmianie kierunku znajduje się w odległości I + 1 od bramki. Ponieważ I <L , mamy, że I + 1 ≤ L , więc kolejne kroki I + 1 doprowadzą go do celu.
Daje to łącznie I + I + 1 = 2I + 1 podjętych kroków. Dodając jeden do komórki początkowej, otrzymujemy w sumie 2I + 1 + 1 = 2 (I + 1) odwiedzonych komórek w tym przypadku.
Jak to działa
źródło
Matlab (wynik = 230, n = inf)
infjeśli chcesz być nieskończony).h=1000000000000000000000000000000000000000000000000000;w(h,h+1)Dla pewności funkcja ta może trwać wiecznie bez żadnych znaczących opóźnień czasowych między dowolnymi dwoma typami wyjść .Algorytm jest oparty na matematycznym podejściu, które wyjaśnię później, i potwierdza listę referencyjną Martina, opartą na tym programie:
Ponieważ algorytm weryfikuje pierwsze przypadki testowe 2048, na ślepo założę, że byłoby tak w każdym przypadku testowym, więc mój algorytm działa w odniesieniu do kilku właściwości, które odkryłem w tym procesie, bez bólu przesunięcia i przesunięcia wskaźnika:
1-, jeśli dwukrotność liczby 1 w tłumaczeniu binarnym nie przekracza długości sekwencji,
Lwięc wynik jest następującyL+12 - jeśli długość sekwencji jest równa, a poprzedni warunek nie jest ustawiony, więc wynik jest taki sam
L+13 - w przeciwnym razie wynik jest dwukrotnością
L/2indeksu th 1.źródło
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, co daje tylko jeden element sekwencji.Python,
122119113110108107103 bajtówPobiera dane wejściowe jako listę cyfr binarnych. Funkcja pomocnicza do testowania:
Podziękowania dla Lynn za oszczędność 7 bajtów.
źródło
p-d-1in[-2,w]oszczędza jeden bajt.d*=2*(1!=d-p>~w)-1pozwala zaoszczędzić jeszcze cztery! ° v °Python 2, 99 bajtów
Port Pythona genialnej odpowiedzi Agawa001.
Wersja do odczytu:
źródło
MATL,
31, 25 bajtówJest to tylko wersja MATL algorytmu Agawa001, z tym wyjątkiem, że pobiera liczbę całkowitą N i zwraca N-ty termin w sekwencji. Trudno było nadążyć za wszystkimi elementami na stosie! Musiałem skorzystać ze schowka, żeby nie oszaleć. Możesz wypróbować online!
Można przekształcić w pętlę drukującą pierwsze N warunków, dodając
:"@przed kodem i]Dpo nim.Dzięki Luis Mendo za uratowanie 6 całych bajtów!
źródło
Julia 0,4, 4̷4̷ 42 bajty
Ta funkcja przyjmuje jako liczbę wejściową jedną liczbę całkowitą w postaci listy cyfr binarnych.
Algorytm jest równoważny z tym z odpowiedzi @ Agawa001 i mojej odpowiedzi Jelly .
Wypróbuj online!
Jak to działa
find(x)zwraca indeksy 1 dla wszystkich niezerowych elementów x . Próbujemy uzyskać dostęp do wynikowej tablicy o indeksie k / 2 i, jeśli się powiedzie, zastąpić k dwukrotnością wybranego indeksu.Nie powiedzie się to wtedy i tylko wtedy, gdy spełniony jest jeden z poniższych warunków:
k / 2 jest niecałkowitą liczbą zmiennoprzecinkową, więc podniesiono InexactError .
Tablica indeksów zawiera mniej niż k / 2 elementów, więc zgłaszany jest błąd BoundsError .
W obu przypadkach nadpisanie k zakończy się niepowodzeniem, więc zostanie zwrócona jego pierwotna wartość.
źródło
JavaScript (ES6), 65 bajtów
Akceptuje ciąg binarny. Używa testu odrzuceń z różnych innych odpowiedzi.
źródło
Python 2, 74 bajty
Ta funkcja przyjmuje jako liczbę wejściową jedną liczbę całkowitą w postaci listy cyfr binarnych.
Algorytm jest równoważny z tym z odpowiedzi @ Agawa001 i mojej odpowiedzi Jelly .
Przetestuj na Ideone .
Jak to działa
nextpróbuje znaleźć pierwszą liczbę całkowitą 2i, dla którejk==2*sum(x[:i])zwraca true. Ponieważx[:i]zawiera elementy i , daje to indeks oparty na 1 (k / 2) th 1 .nextzawiedzie, jeśli k / 2 nie jest całką lub jeśli x zawiera mniej niż k / 2 . W takim przypadku zwracana jest wartość domyślna k .źródło
> <> , 63 bajty
Od momentu, gdy zobaczyłem przykładowy wzór w tym wyzwaniu, wiedziałem, którego języka użyć :)
Użycie N, aby uzyskać N- ty termin.
Dane wejściowe przyjmowane są w postaci binarnej na stosie. Zamiast przesuwać walker, to rozwiązanie polega głównie na przesuwaniu taśmy pod walkerem.
Wypróbuj online!
źródło