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 >i 0pod <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.

Galaretka , 10 bajtów

ð+\ḤiḤoµL‘

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

ð+\ḤiḤoµL‘  Main link. Argument: x (list of binary digits of N)

       µ    Monadic chain. Argument: x
        L   Compute L, the length of x.
         ‘  Increment to yield L + 1.

ð           Dyadic chain. Left argument: x. Right argument: L + 1
 +\         Compute the cumulative sum of x.
            This replaces the k-th one (and all zeroes to its right) with k.
   Ḥ        Unhalve; multiply all partial sums by 2.
    i       Find the first index of L + 1.
            This either gives I + 1, the 1-based index of the ((L + 1) / 2)-th one
            or 0 if the list doesn't contain L + 1.
            The result will be 0 if x contains less than (L + 1) / 2 ones
            or if L + 1 is an odd integer.
     Ḥ      Unhalve; yield either 2(I + 1) or 0.
      o     Logical OR with L + 1; if the previous operation returned a falsy
            value (i.e., if it yielded 0), replace that value with L + 1.

Matlab (wynik = 230, n = inf)

function w(s,f),b=[];e=0;for i=s:f,a=dec2bin(i);c=find(a=='1');g=numel(a)+1;if numel(c)>=g/2;if mod(g,2)==1,fprintf('%d ',g);else,d=c(g/2);fprintf('%d ',2*d);end,else,fprintf('%d ',g);end,e=e+1;if(e==100),e=0;fprintf('\n');end;end

• Funkcja przyjmuje s jako indeks początkowy if jako koniec (wpisz, 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:

  stored=[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, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 14, 8, 8, 8, 14, 8, 14, 12, 12, 8, 8, 8, 14, 8, 14, 12, 12, 8, 14, 12, 12, 10, 10, 10, 10, 8, 8, 8, 14, 8, 14, 12, 12, 8, 14, 12, 12, 10, 10, 10, 10, 8, 14, 12, 12, 10, 10, 10, 10, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 18, 10, 10, 10, 10, 10, 10, 10, 18, 10, 10, 10, 18, 10, 18, 16, 16, 10, 10, 10, 10, 10, 10, 10, 18, 10, 10, 10, 18, 10, 18, 16, 16, 10, 10, 10, 18, 10, 18, 16, 16, 10, 18, 16, 16, 14, 14, 14, 14, 10, 10, 10, 10, 10, 10, 10, 18, 10, 10, 10, 18, 10, 18, 16, 16, 10, 10, 10, 18, 10, 18, 16, 16, 10, 18, 16, 16, 14, 14, 14, 14, 10, 10, 10, 18, 10, 18, 16, 16, 10, 18, 16, 16, 14, 14, 14, 14, 10, 18, 16, 16, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 12, 10, 10, 10, 10, 10, 10, 10, 18, 10, 10, 10, 18, 10, 18, 16, 16, 10, 10, 10, 18, 10, 18, 16, 16, 10, 18, 16, 16, 14, 14, 14, 14, 10, 10, 10, 18, 10, 18, 16, 16, 10, 18, 16, 16, 14, 14, 14, 14, 10, 18, 16, 16, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 12, 10, 10, 10, 18, 10, 18, 16, 16, 10, 18, 16, 16, 14, 14, 14, 14, 10, 18, 16, 16, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 12, 10, 18, 16, 16, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 22, 12, 12, 12, 22, 12, 22, 20, 20, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12, 12, 12, 22, 12, 22, 20, 20, 12, 22, 20, 20, 18, 18, 18, 18, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12, 22, 20, 20, 18, 18, 18, 18, 16, 16, 16, 16, 16, 16, 16, 16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13];
  b=[];for i=1:numel(stored)
  a=dec2bin(i);
  c=find(a=='1');
  if numel(c)>=(numel(a)+1)/2
  if mod(numel(a)+1,2)==1
  b=[b numel(a)+1];
  else
  d=c((numel(a)+1)/2);
  b=[b 2*d];
  end
  else
  b=[b numel(a)+1];
  end
  end
  for i=1:numel(stored)
  if (b(i))
  if b(i)~=stored(i)
  'error',
  end
  end
  end
  

• 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+1

  2 - jeśli długość sekwencji jest równa, a poprzedni warunek nie jest ustawiony, więc wynik jest taki sam L+1

  3 - w przeciwnym razie wynik jest dwukrotnością L/2indeksu th 1.

Python, 122 119 113 110 108 107 103 bajtów

def l(b):
 p=e=w=len(b);d=i=1
 while e:p+=1-2*b[w-e];d*=2*(1!=d-p>~w)-1;p-=d;e=(e-d)%-~w;i+=1
 return i

Pobiera dane wejściowe jako listę cyfr binarnych. Funkcja pomocnicza do testowania:

b = lambda n: [int(d) for d in bin(n)[2:]]

_{Podziękowania dla Lynn za oszczędność 7 bajtów.}

Python 2, 99 bajtów

def l(b):l=len(b);return(l>=sum(b)*2or l%2<1)and-~l or[i+1for i,c in enumerate(b)if b[i]][l/2]*2

Port Pythona genialnej odpowiedzi Agawa001.

Wersja do odczytu:

def l(b):
    if len(b) >= 2*sum(b) or len(b)%2 == 0:
        return len(b) + 1

    return 2*[i+1 for i, c in enumerate(b) if b[i]][len(b)//2]

MATL, 31 , 25 bajtów

BXHnQtHsy2/<w2\+~?2/Hfw)E

Jest 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!

Julia 0,4, 4̷4̷ 42 bajty

x->(k=endof(x)+1;try k=2find(x)[k/2]end;k)

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ść.

JavaScript (ES6), 65 bajtów

s=>(l=s.length+1)%2|!(m=s.match(`(0*1){$l/2}}`))?l:m[0].length*2

Akceptuje ciąg binarny. Używa testu odrzuceń z różnych innych odpowiedzi.

Python 2, 74 bajty

def f(x):k=len(x)+1;print next((i*2for i in range(k)if k==2*sum(x[:i])),k)

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órej k==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 .

> <> , 63 bajty

2r11&>}:?v{1->:l2-%?vr{{$>1+$}$:2=$@&101.
 +&?!^&n;>{1+^ .0+bf<

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!