Jest to odpowiedź na stare wyzwanie , mające na celu dostosowanie wymagań We / Wy do naszych najnowszych standardów. Odbywa się to w celu umożliwienia większej liczbie języków wzięcia udziału w wyzwaniu dotyczącym tej popularnej sekwencji. Zobacz ten meta post w celu omówienia repost.

Sekwencja Kolakoski to zabawna sekwencja autoreferencyjna, która ma zaszczyt być sekwencją OEIS A000002 (i jest znacznie łatwiejsza do zrozumienia i implementacji niż A000001). Sekwencja zaczyna się od 1 , składa się tylko z 1 si 2 s, a element sekwencji a (n) opisuje długość n- tego przebiegu 1 s lub 2 s w sekwencji. To jednoznacznie określa kolejność (z wizualizacją przebiegów poniżej):

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,...
= === === = = === = === === = === === = = === = = === === = === =
1, 2,  2, 1,1, 2, 1, 2,  2, 1, 2,  2, 1,1, 2, 1,1, 2,  2, 1, 2, 1,...

Twoim zadaniem jest oczywiście wdrożenie tej sekwencji. Możesz wybrać jeden z trzech formatów:

1. Weź wejście n i wyślij n- ty ciąg sekwencji, gdzie n zaczyna się od 0 lub 1 .
2. Wziąć wejście n oraz wyjście terminy włącznie z n -tego okresu sekwencji, gdzie n rozpoczyna albo z 0 lub 1 (tj albo drukowania pierwszej n i pierwszy n + 1 zasady).
3. Wartości wyjściowe z sekwencji w nieskończoność.

W drugim i trzecim przypadku możesz wybrać dowolny rozsądny, jednoznaczny format listy. W porządku, jeśli nie ma separatora między elementami, ponieważ z definicji są one zawsze pojedynczymi cyframi.

W trzecim przypadku, jeśli przesłanie jest funkcją, możesz również zwrócić nieskończoną listę lub generator w językach, które je obsługują.

Możesz napisać program lub funkcję i użyć dowolnej z naszych standardowych metod otrzymywania danych wejściowych i dostarczania danych wyjściowych. Pamiętaj, że te luki są domyślnie zabronione.

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Galaretka , 7 bajtów

2Rṁxṁµ¡

Jest to pełny program, który drukuje pierwsze n warunków.

Wypróbuj online!

Jak to działa

2Rṁxṁµ¡  Main link. Argument: n (integer)

     µ   Combine the preceding links into a monadic chain.
      ¡  Set t = n.  Call the chain n times, updating t with the return value after
         each call. Yield the last value of t.
2R           Set the return value to 2 and take its range. Yields [1, 2].
  ṁ          Mold; cyclically repeat 1 and 2 to match t's length.
             In the first run, ṁ promotes t = n to [1, ..., n].
   x         Repeat the k-th element of the result t[k] times.
             In the first run, x repeats each element t = n times.
    ṁ        Mold; truncate the result to match the length of t.
             In the first run, ṁ promotes t = n to [1, ..., n].                 

Przykładowy przebieg

Niech n = 5 .

Pierwsze wywołanie łańcucha powtarza cyklicznie 1, 2, aby osiągnąć długość 5 , następnie każdy element 5 razy, a na koniec skraca wynik do długości 5 .

  1         2         1         2         1
x 5         5         5         5         5
---------------------------------------------------
  1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1

  1 1 1 1 1

Daje to listę o długości 5 . Pierwszy element jest pierwszym elementem sekwencji Kolakoski.

Drugie wywołanie łańcucha powtarza cyklicznie 1, 2, aby osiągnąć długość 5 , następnie powtarza k- ^ty element j razy, gdzie j jest k- ^tym elementem z poprzedniej listy, i na koniec skraca wynik do długości 5 .

   1 2 1 2 1
x  1 1 1 1 1
------------
   1 2 1 2 1

   1 2 1 2 1

Daje to kolejną listę o długości 5 . Pierwsze dwa elementy są pierwszymi dwoma elementami sekwencji Kolakoski.

Proces ten trwa trzy kolejne iteracje.

   1 2   1 2   1
x  1 2   1 2   1
----------------
   1 2 2 1 2 2 1

   1 2 2 1 2

   1 2   1   2 1
x  1 2   2   1 2
------------------
   1 2 2 1 1 2 1 1

   1 2 2 1 1

   1 2   1   2 1
x  1 2   2   1 1
----------------
   1 2 2 1 1 2 1

   1 2 2 1 1

To jest pierwsze pięć elementów sekwencji Kolakoskiego.

Python 2 , 51 bajtów

l=[2]
print 1,2,
for x in l:print x,;l+=x*[l[-1]^3]

Drukuje w nieskończoność. Tworzy listę lw trakcie iteracji. Dla każdego wpisu xw l, dodaje xkopii 1lub 2, w zależności od bieżącego naprzeciwko ostatniego elementu.

Główną trudnością jest poradzenie sobie z początkowym fragmentem autoreferencyjnym [1,2,2]. Ten kod po prostu drukuje inicjał 1,2i kontynuuje stamtąd. Dodatkowy druk kosztuje 12 bajtów. Bez tego:

39 bajtów , brakuje dwóch pierwszych wpisów:

l=[2]
for x in l:print x;l+=x*[l[-1]^3]

Innym podejściem jest specjalna inicjalizacja pierwszych dwóch wpisów. My zainicjować ljak [0,0,2]tak, że pierwsze dwie pozycje nie powodują dołączenie, ale print x or nsprawia im być drukowane jako n.

51 bajtów

l=[0,0,2]
n=1
for x in l:print x or n;l+=x*[n];n^=3

Inną poprawką jest inicjalizacja l=[1], ręczne śledzenie zmiany ni poprawienie drukowania:

51 bajtów

n,=l=[1]
for x in l:print(l==[1,1])+x;l+=x*[n];n^=3

Bez tego (l==[1,1])+wszystko działa oprócz wydrukowanych sekwencji 1,1,2zamiast 1,2,2. Musi być lepszy sposób na rozpoznanie, że jesteśmy na tym drugim etapie.

I kolejna dziwna poprawka, a także ta sama liczba bajtów:

51 bajtów

l=[1];q=2
for x in l:print x;l+=x*[l[-1]^3]*q;q=q<2

Wumpus , 13 11 bajtów

=[=)O?=!00.

Wypróbuj online!

Drukuje sekwencję w nieskończoność bez separatorów.

Jestem naprawdę zaskoczony, jak krótki jest to czas.

Wyjaśnienie

Podstawowym pomysłem jest utrzymanie sekwencji na stosie i wielokrotne używanie najniższego elementu w celu wygenerowania kolejnego przebiegu, a następnie wydrukowania go. Skutecznie nadużywamy stosu jako kolejki. Możemy także zaoszczędzić kilka bajtów, pracując 0i 1(zwiększając tylko dane wyjściowe) zamiast 1i 2, ponieważ w ten sposób nie musimy jawnie inicjować stosu za pomocą 1i możemy użyć logicznej negacji do przełączania się między dwiema wartościami.

     The entire program is run in a loop.
     At the beginning of loop iteration i, a(i)-1 will be at the bottom of the
     stack and the first element of the ith run of values will be on top.
     The caveat is that on the first iteration, the stack is empty, but
     popping from an empty stack produces an implicit zero.
=    Duplicate the top of the stack. Since this is defined as "pop x, push
     x, push x" this will result in 2 zeros when the stack is empty.
     After this we've got two copies of the ith run's value on top of the stack.
[    Pull up a(i)-1 from the bottom of the stack.
=)O  Duplicate, increment to a(i) and print it.
?=   If a(i)-1 is 1 (as opposed to 0), make another copy of the top of the
     stack. We've now got a(i)+1 copies, so one more than the run should be 
     long, but that's great because we can use the additional copy to get 
     the start of the next run.
!    Logical negation which swaps 0 and 1.
00.  Jump back to the beginning of the program.

Brachylog , 30 26 25 23 17 16 14 bajtów

~a₀{1|2}ᵐḅlᵐ?l

Zwraca pierwsze n wartości. Wykorzystuje „zmienną wyjściową” .dla danych wejściowych i przekazuje dane do „zmiennej wejściowej” ?. Wypróbuj online!

Wyjaśnienie

Bardzo się cieszę z tego, jak to się deklaruje: program jest w zasadzie opisem wysokiego poziomu listy wyników i jej relacji do danych wejściowych.

~a₀{1|2}ᵐḅlᵐ?l  Input is a number N.
                Output is a term that I'll call T.
~a₀             T is a prefix of a list L.
   {   }ᵐ       Each element of L
    1|2         is either 1 or 2.
         ḅ      If you cut L into blocks of equal elements
          lᵐ    and take the length of each block,
            ?   the result is T.
             l  The length of T is N.

Ponieważ {1|2}ᵐlisty testowane są w kolejności leksykograficznej, dane wyjściowe zaczynają się od 1.

Łuska , 10 bajtów

Ṡωo↑⁰`Ṙ¢ḣ2

Zwraca pierwsze n wartości. Wypróbuj online!

Wyjaśnienie

Ṡωo↑⁰`Ṙ¢ḣ2  Input is an integer N.
        ḣ2  The range [1,2]
       ¢    Cycle: C = [1,2,1,2,1,2...
 ω          Iterate until fixed point is found:
Ṡ    `Ṙ      Replicate the list C element-wise according to the current list,
  o↑⁰        then take first N elements.

W przypadku danych wejściowych 20 proces wygląda następująco:

[1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2...
[1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2]
[1,2,2,1,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,2]
[1,2,2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,1,2]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]

Java 10, 155 108 105 100 97 bajtów

v->{var s="122";for(int i=1;;s+=(1+i%2)*(s.charAt(i)>49?11:1))System.out.print(s.charAt(++i-2));}

Drukuje w nieskończoność bez ogranicznika.

-3 bajty po pośredniej wskazówce od @Neil .
-5 bajtów dzięki @MartinEnder .
-3 bajty konwertują Java 8 na Java 10.

Wyjaśnienie:

Wypróbuj online (limit czasu po 60 sekundach w TIO).

v->{              // Method with empty unused parameter and no return-type
  var s="122";    //  String, starting at "122"
  for(int i=1;;   //  Loop `i` from 1 upwards indefinitely
      s+=         //    After every iteration: Append the String with:
         (1+i%2)  //     1+`i`modulo-2
         *(s.charAt(i)>49?11:1))
                  //     either once or twice depending on the digit at index `i`
    System.out.print(s.charAt(++i-2));}
                  //   Print the character at index `i-2` of the String
                  //   After we've first increased `i` by 1 with `++i`

Galaretka , 10 bajtów

’߀+\<¹SḂ‘

Zwraca n- ^ty termin.

Wypróbuj online!

Jak to działa

’߀+\<¹SḂ‘  Main link. Argument: n (positive integer)

’           Decrement; yield n-1.
 ߀         Recursively map the main link over [1, ..., n-1].
   +\       Take the cumulative sum.
            The k-th sum is the combined length of the first k runs.
     <¹     Compare each sum with n.
       S    Sum the Booleans.
            This counts the number of runs that occur before the n-th term.
            If there's an even number (including 0) of runs, the n-th term is 1.
            If there's an odd number of runs, the n-th term is 2.
        Ḃ   Extract the least significant bit of the count.
         ‘  Increment.

Haskell , 33 bajty

r=r%1
~(x:t)%n=n:[n|x>1]++t%(3-n)

Wypróbuj online!

Ørjan Johansen zapisał 7 bajtów przy użyciu niepodważalnego wzorca, aby wymusić prefiks.

Gol> <> , 8 7 bajtów

:{:PnKz

Wypróbuj online!

Wyjaśnienie

To jest port mojej odpowiedzi Wumpusa . Gol> <> jest w zasadzie język, który posiada wszystkie niezbędne funkcje do portu odpowiedź wumpusa (konkretnie ukryte zer na dnie stosu, „duplikat” wdrożone „pop, Push, Push” i komendy obrotu stosu), ale :

• Ma toroidalną siatkę, co oznacza, że ​​nie potrzebujemy wyraźnego 00.skoku, aby wrócić do początku.
• Ma K„pop N, a następnie duplikuje następny element N razy”, który można zastąpić ?=, oszczędzając kolejny bajt.

Mapowanie z Wumpus na Gol> <> staje się:

Wumpus   Gol><>
=        :
[        {
=        :
)        P
O        n
?=       K
!        z
00.

Język programowania Szekspira , 594 583 572 bajtów

Dzięki Ed Wynn za -10 bajtów!

,.Ford,.Puck,.Act I:.Scene I:.[Enter Ford and Puck]Ford:You cat!Open heart!You big cat!Open heart!Puck:Remember you!Remember me!Scene V:.Ford:You is the sum ofI a cat!Puck:Recall!Open heart!Ford:Remember a pig!Is I nicer a cat?If notyou be the sum ofyou a big pig!Scene X:.Puck:Recall!Ford:Is I nicer zero?If soremember I!If solet usScene X!Puck:Is I nicer zero?You is the sum ofI a big cat!If soyou is I!Remember zero!Remember I!Remember you!You be the difference betweena big cat you!Scene L:.Ford:Recall!Is you worse I?If so,let usScene V!Puck:Remember I!Let usScene L!

Wypróbuj online!

To jest golfowa wersja nie golfowego rozwiązania Eda Wynna , zaczynając od 828 bajtowego rozwiązania, które umieścił w komentarzach, i stamtąd trochę wariuje .

Wyjaśnienie:

,.Ford,.Puck,.Act I:.Scene I:.[Enter Ford and Puck]    Boilerplate, introducing the characters
Ford:You cat!Open heart!You big cat!Open heart!  Print 1,2 as the first two terms of the sequence

Puck:Remember you!Remember me!  Initialise stack as 0, 2
                                Ford's value is currently 0, representing the value to be pushed to the stack

Scene V:.     Start infinite loop
  Ford:You is the sum ofI a cat!         
  Puck:Recall!Open heart!                 Pop the next value in the stack and print it
  Ford:Remember a pig!                    Push -1 as the end of the stack
  Is I nicer a cat?                       If Ford's value is 2
  If notyou be the sum ofyou a big pig! Subtract 2 from Puck's value to represent making 2 only one copy

        #Reverse the stack until it reaches the terminator value 0 or -1
  Scene X:.Puck:Recall!Ford:Is I nicer zero?If soremember I!If solet usScene X!

  Puck:Is I nicer zero?                          Check if the Puck's value is bigger than 0 (only making one copy)
  You is the sum of Ia big cat!                 Set Ford's value to Puck+2 to counter the change
  If soyou is I!                                But undo it if making one copies
  Remember zero!                                 Push 0 as the stack terminator
  Remember I!                                    Push Ford's value, which is 0 or -1 if this is a single copy, or 1 or 2 for a double copy
  Remember you!                                  Push one copy of Puck's value
  You be the difference betweena big cat you!   Map Ford's value from 1,2 to 1,0

  Scene L:.   #Reverse the stack until it reaches the terminator 0 
     Ford:Recall!Is you worse I?If solet us Scene V!
     Puck:Remember I!Let usScene L!

> <> , 13 12 bajtów

0:{:1+n?:0=!

Wypróbuj online!

Port odpowiedzi Wumpusa Martina Endera . Niestety, ><>nie ma polecenia inkrementacji ani inwertowania, ani nie ma niejawnych zer na dole stosu, więc kończy się to nieco dłużej.

JavaScript, 67 66 60 58 52 51 50 bajtów

To sprawiło, że mój mózg swędził bardziej niż powinien! Powoduje powtórzenie nth, indeksowane 0.

s=`122`
x=1
f=n=>s[n]||f(n,s+=s[++x%2]*(s[x]+0-9))

5 + 1 bajtów zaoszczędzonych dzięki tsh drapiącemu mój swędzący mózg!

Sprawdź to

Poniższy fragment kodu wyświetli pierwsze 50 haseł.

s=`122`
x=1
f=n=>s[n]||f(n,s+=s[++x%2]*(s[x]+0-9))
o.innerText=[...Array(50).keys()].map(f).join`, `

<pre id=o></pre>

Wyjaśnienie

Jest to jedna z tych rzadkich sytuacji, w których możemy zadeklarować niektóre zmienne poza zakresem naszej funkcji, zmodyfikować je w obrębie funkcji i nadal być w stanie wykorzystać je przy kolejnych wywołaniach funkcji.

s=`122`       :Initialise variable s as the string "122"
x=1           :Initialise variable x as integer 1
f=n=>         :Named function f taking input as an argument through parameter n
 s[n]         :If s has a character at index n, return it and exit
 ||           :Or
 f(n          :Call f with n again
  ,s+=        :At the same time, append to s
  s[++x%2]    :  Increment x, modulo by 2 and get the character at that index in s
  *           :  Multiplied by (the above gets cast to an integer)
  (s[x]+0-9)  :  Append a 0 to the xth character of s and subtract 9
 )            :  (The above gives "1"+0-9="10"-9=1 or "2"+0-9="20"-9=11)

Python (2 i 3), 65 60 bajtów

f=lambda n:sum([f(i)*[i%2+1]for i in range(2,n)],[1,2,2])[n]

Zwraca n- ty wpis, indeksowany 0.

Alternatywa (65 bajtów):

f=lambda n:n>1and sum([f(i)*[i%2+1]for i in range(n)],[])[n]or-~n

Haskell , 48 bajtów

-1 bajt dzięki nim. -2 bajty dzięki Lynn.

c=1:2:c
l=1:2:drop 2(id=<<zipWith replicate l c)

Wypróbuj online!

Powtórz każdy element mod pozycji 2 + 1 razy.

pieprzenie mózgu , 61 bajtów

+.+.[.[>]>+++>+++<<<[->+>->-<<<]<[[->+<]<]>>--[[>]<,<[<]>+]>]

Wypróbuj online!

Drukuje liczby jako kody znaków w nieskończoność. Dla jasności, oto wersja, która drukuje w liczbach (z wyjątkiem pierwszych dwóch elementów, które są łatwe do zweryfikowania).

Jak to działa:

+.+. Prints the first two elements. These are the self-referential elements
     This also intitialises the tape with the third element, 2
[ Start infinite loop
   . Print current lowest element
   [>]>+++>+++ Move to end of tape and create two 3s
   <<<[->+>->-<<<] Subtract the last element of the tape from these 3s
   <[[->+<]<]>> Move to the beginning of the tape
   --  Subtract two from the first element
       This leaves 2 as 0 and 1 as -1
   [ If the number was 1
     [>]<,  Delete the excess element from the end of the tape
     <[<]>+ Remove the -1
   ]
   > Move to the next element of the list
]

05AB1E , 12 9 bajtów

Zaoszczędzono 3 bajty dzięki Grimy

Drukuje pierwsze n elementów.

Δ2LÞsÅΓI∍

Wypróbuj online!

Wyjaśnienie

Δ           # repeat until ToS doesn't change
 2LÞ        # push [1,2,1,2 ...]               
    sÅΓ     # run-length encode with previous value (initially input)
       I∍   # extend/shorten to the length specified by input

05AB1E , 15 bajtów

ƵLS[DNÌ©èF®É>¸«

Wypróbuj online! lub z limitem iteracji

Wyjaśnienie

ƵLS               # push our initial list [1,2,2]
   [              # for every N in [0 ...
    D             # duplicate current list of numbers
     NÌ©è         # get the N+2'th element from the list
         F        # that many times do
          ®É>     # push ((N+2)%2==1)+1
             ¸«   # append to current list

Python 3 , 55 54 bajtów

n=h=1;l=[]
while n:print(h);n^=3;h,*l=l+[n]*(l+[2])[0]

Wypróbuj online!

J , 12 bajtów

Funkcja pojedynczego argumentu przyjmuje n i tworzy pierwsze n wyrażeń. Wypróbuj online!

$(1+2|I.)^:]

Po prostu wyciągam moją starą odpowiedź na stare pytanie.

I.jest czasownikiem, który pobiera tablicę liczb i wyrzuca listę indeksów, więc jeśli k -ty element w tablicy to n , to indeks k pojawia się n razy. Użyjemy go do uruchomienia sekwencji Kołakowskiego od początkowego ziarna. Każdy krok będzie przebiegał w następujący sposób:

1 2   2   1 1 2   1 2   2   1   (some prefix)
0 1 1 2 2 3 4 5 5 6 7 7 8 8 9   (use I.)
0 1 1 0 0 1 0 1 1 0 1 1 0 0 1   (mod 2)
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2   (add 1) 

Jeśli wykonujemy tę operację 1+2|I.w kółko, zaczynając od 10, wygląda to tak:

10
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
1 2 2 1 1 2 1 1 2 2 1 2 2 1 1 ...
1 2 2 1 1 2 1 2 2 1 2 1 1 2 2 ...
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 ...

Zauważ, że za każdym razem otrzymujemy coraz więcej poprawnych warunków, a po pewnym czasie pierwsze n warunków zostaje naprawionych. Ilość iteracji potrzebnych do ustalenia jest trudna do dokładnego opisania, ale wygląda na z grubsza logarytmiczną w n , więc jeśli uruchomimy ją n razy ( ^:]), powinno być dobrze. (Sprawdź te inne sekwencje OEIS, aby uzyskać więcej informacji: długości generacji , sumy częściowe ).

Kiedy to skończymy, wystarczy, że użyjemy pierwszych n terminów $. Konstrukcja $vdowolnego czasownika vjest przykładem haka i podanie go njako argumentu zostanie wykonane n $ (v n).

Oto stara wersja 13-bajtowy, który jest znacznie mniej marnotrawstwem czasu i przestrzeni: ($1+2|I.)^:_~. Obcina dane wejściowe na każdym kroku, dzięki czemu możemy uruchomić dokładnie tyle razy, ile potrzeba, aby ustawić, zamiast liniowo wiele razy.

Fueue , 30 bajtów

Fueue to esolang oparty na kolejce, w którym uruchomiony program i jego dane znajdują się w tej samej kolejce, wykonywanie odbywa się cyklicznie w kolejce, a programowanie wymaga dużej synchronizacji, aby zapobiec wykonywaniu czegokolwiek w niewłaściwym czasie.

1)2:[[2:])~)~:~[[1]:~))~:~~]~]

Wypróbuj online!

Powyżej drukuje niekończącą się listę cyfr jako kodów kontrolnych. Dla 34 bajtów może drukować rzeczywiste cyfry:

49)50:[[50:])~)~:~[[49]:~))~:~~]~]

Wypróbuj online!

W pozostałej części objaśnienia wykorzystano tę ostatnią wersję.

Podsumowanie elementów Fueue

Kolejka Fueue może zawierać następujące elementy:

• Liczby całkowite, które po uruchomieniu drukują swój kod Unicode,
• Bloki podprogramów rozdzielone nawiasami kwadratowymi , które są na szczęście nieaktywne (tylko przechodzą na koniec kolejki), chyba że )funkcja je odblokuje , i
• Funkcje jednoznakowe, które są uruchamiane, jeśli następuje po nich odpowiedni typ argumentów i pozostają nieaktywne w przeciwnym razie.
  • Jedynymi funkcjami używanymi w tym programie są ~(zamiana dwóch następujących elementów), :(duplikowanie następnego elementu) i )(odblokowanie następnego bloku).

Omówienie wysokiego poziomu

Podczas głównej pętli programu kolejka składa się z:

• łańcuch bloków reprezentujących cyfry, które mają być iterowane;
  • Cyfra 1 lub 2 jest reprezentowana odpowiednio przez bloki [49]i [50:].
• samoreplikująca się sekcja głównej pętli, która przecina bloki cyfr i umieszcza na przemian 1 i 2 po nich, a następnie odblokowuje je.
  • Odblokowany blok cyfr drukuje własną cyfrę d , a następnie tworzy d kopie następnego bloku, tworząc w ten sposób cyfry opisywanego przebiegu.

Niski poziom śledzenia pierwszych 10 poleceń

Cmds   Explanation              Queue
49     Print '1'.               )50:[[50:])~)~:~[[49]:~))~:~~]~]
)      Inactive, move to end.   50:[[50:])~)~:~[[49]:~))~:~~]~])
50     Print '2'.               :[[50:])~)~:~[[49]:~))~:~~]~])
:[...] Duplicate block.         )[[50:])~)~:~[[49]:~))~:~~]~][[50:])~)~:~[[49]:~))~:~~]~]
)[...] Deblock (rmv. brackets). [[50:])~)~:~[[49]:~))~:~~]~][50:])~)~:~[[49]:~))~:~~]~
[...]  Inactive.                [50:])~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~]
[50:]  Inactive.                )~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:]
)      Inactive.                ~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])
~)~    Swap ) and ~.            :~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])~)
:~     Duplicate ~.             [[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])~)~~

Omówienie pełnej iteracji głównej pętli

Opcjonalne białe znaki zostały wstawione do oddzielnych poleceń.

49 ) 50 :[[50:])~)~:~[[49]:~))~:~~]~]

Cykl 1: 49drukuje 1. )jest nieaktywny i czeka na połączenie z blokiem głównej pętli. 50odbitki 2. :duplikuje blok głównej pętli (który potrzebuje kopii do samodzielnej replikacji).

) [[50:])~)~:~[[49]:~))~:~~]~] [[50:])~)~:~[[49]:~))~:~~]~]

Cykl 2: )odblokowuje pierwszy blok głównej pętli, dzięki czemu zaczyna wykonywać następny cykl.

[50:] ) ~)~ :~ [[49]:~))~:~~] ~[[50:])~)~:~[[49]:~))~:~~]~]

Cykl 3: [50:]reprezentuje pierwszą cyfrę wyprodukowaną w łańcuchu, 2jeszcze nie odblokowaną. Następujące czynności )ostatecznie to zrobią po przejściu przez resztę głównej pętli. ~)~:~to gra w golfa (za pomocą zamiany i kopii) opóźnienie o jeden cykl wynoszące ~)~~. [[49]:~))~:~~]jest nieaktywny. ~zamienia następujący blok głównej pętli obok [50:]bloku cyfr.

) ~)~ ~[[49]:~))~:~~][50:] [[50:])~)~:~[[49]:~))~:~~]~]

Cykl 4: )nadal czeka, ~)~produkuje ~), ~zamienia [[49]:~))~:~~]obok [50:]bloku cyfr.

) ~)[50:] [[49]:~))~:~~] [[50:])~)~:~[[49]:~))~:~~]~]

Cykl 5: ~zamienia )obok [50:]bloku cyfr.

)[50:] )[[49]:~))~:~~] [[50:])~)~:~[[49]:~))~:~~]~]

Cykl 6: Pierwszy )blokuje teraz [50:]blok cyfrowy, następny )blokuje podprogram [[49]:~))~:~~].

50 :[49] :~ ) ) ~:~ ~[[50:])~)~:~[[49]:~))~:~~]~]

Cykl 7: 50drukuje 2, :duplikuje właśnie wytworzony [49]blok cyfrowy, tworząc ciąg dwóch 1sekund. :~))~:~jest opóźnieniem o jeden cykl wynoszącym ~~))~:. ~zamienia pozostały blok głównej pętli za pierwszym [49].

[49] ~~) ) ~:[49] [[50:])~)~:~[[49]:~))~:~~]~]

Cykl 8: ~~))jest opóźnieniem o jeden cykl wynoszącym )~). ~zamienia się :obok aktualnie trawersowanego [49].

[49] ) ~)[49] :[[50:])~)~:~[[49]:~))~:~~]~]

Cykl 9: ~zamienia się w )przeszłości [49]. :powiela blok głównej pętli.

[49] )[49] )[[50:])~)~:~[[49]:~))~:~~]~] [[50:])~)~:~[[49]:~))~:~~]~]

Cykl 10: Pierwsze )odblokowuje [49]blok cyfrowy, który właśnie przeszedł, drugi )ponownie uruchamia główną pętlę, aby przejść do następnej (powyżej pokazano na początku kolejki).

x 86, 41 37 35 33 28 bajtów

Miałem dużo zabawy z różnymi instrukcjami x86, ponieważ jest to moja pierwsza „nietrywialna” odpowiedź x86. Właściwie nauczyłem się najpierw x86-64 i zaoszczędziłem wiele bajtów, konwertując mój program do wersji 32-bitowej.

Okazuje się, że algorytm, którego użyłem z OEIS, wypycha wartości do tablicy, co czyni go podatnym na x86 i przechowuje wartości na stosie (uwaga, że ​​MIPS nie ma instrukcji stosu).

Obecnie program pobiera Nwartości jako dane wejściowe ecxi zwraca adres ebptablicy z n-tym elementem reprezentującym n-tą wartość w sekwencji. Zakładam, że zwracanie na stosie i obliczanie dodatkowych wartości jest prawidłowe (i tak uważamy to, co poza tablicą, za śmieci).

Dziennik zmian

• -4 bajty, obliczając x = 2 - n%2przy xorkażdej iteracji

• -2 bajty przy użyciu pętli do-while zamiast while.

• -2 bajty, przesuwając wartości początkowe 1, 2, 2 za pomocą eax

• -5 bajtów, nie przechowując njawnie i zamiast tego uruchamiając Nczasy pętli

.section .text
.globl main
main:
        mov     $10, %ecx           # N = 10 

start:
        mov     %esp, %ebp          # Save sp
        push    $1
        push    $2                  # x = 2
        pop     %eax       
        push    %eax                # push 2
        push    %eax                # push 2
        mov     %esp, %esi          # sn = stack+3 addr

loop:                               
        xor     $3, %al             # flip x between 1 <-> 2 
        push    %eax                # push x      
                                    # maybe use jump by parity?
        cmp     $2, (%esi)          # if *sn == 2 
        jne     loop1
        push    %eax                # push x

loop1: 
        sub     $4, %esi            # sn += 1
        loop    loop                # --N, do while (N)
end:
        mov     %ebp, %esp          # Restore sp
        ret

Objdump:

00000005 <start>:
   5:   89 e5                   mov    %esp,%ebp
   7:   6a 01                   push   $0x1
   9:   6a 02                   push   $0x2
   b:   58                      pop    %eax
   c:   50                      push   %eax
   d:   50                      push   %eax
   e:   89 e6                   mov    %esp,%esi

00000010 <loop>:
  10:   34 03                   xor    $0x3,%al
  12:   50                      push   %eax
  13:   83 3e 02                cmpl   $0x2,(%esi)
  16:   75 01                   jne    19 <loop1>
  18:   50                      push   %eax

00000019 <loop1>:
  19:   83 ee 04                sub    $0x4,%esi
  1c:   e2 f2                   loop   10 <loop>

0000001e <end>:
  1e:   89 ec                   mov    %ebp,%esp
  20:   c3                      ret 

C (gcc) , 72 71 65 64 62 bajty

-9 bajtów dzięki @ceilingcat

x,y;f(z){for(x=y=-1;putchar(49-~x%2);y=-~y|z&x/2)x^=z=y&~-~y;}

Wypróbuj online!

Generuje wartości sekwencji w nieskończoność (opcja 3 z wyzwania)

Perl 5 , 36 bajtów

Wciąż trywialna modyfikacja klasycznego rozwiązania TPR (0,3):

Wysyła serię od 0don

#!/usr/bin/perl
use 5.10.0;
say$_=($n+=!--$_[$n])%2+1for@_=0..<>

Wypróbuj online!

JavaScript ES6 - 71 70 68 bajtów

(_="122")=>{for(x=1;;_+=(1+x%2)*(_[x]>1?11:1))console.log(_[++x-2])}

1 bit zapisany dzięki Neilowi

Dziękujemy Shaggy'owi za naprawienie mojego błędu, a także za zapisanie 1-bitowego.

f = (_="122") => {
  for(x=1;x<20;_+=(1+x%2)*(_[x]>1?11:1))
    document.getElementById('content').innerHTML += '   ' + _[++x-2]
}
f()

<div id="content"></div>

Nasiona jabłek , 89 bajtów

(def K(lambda()(concat(q(1 2))(drop 2(flatten(zip-with repeat-val(cycle(q(1 2)))(K)))))))

Definiuje funkcję, Kktóra nie przyjmuje argumentów i zwraca sekwencję Kolakoski jako nieskończoną listę. Wypróbuj online!

To podejście zostało zainspirowane odpowiedzią Haskell całkowicie ludzką . Moje oryginalne podejście było dłuższe i prawdopodobnie było O (2 ^ n). : ^ P

Nie golfił

(def kolakoski
 (lambda ()
  (concat (list 1 2)
   (drop 2
    (flatten
     (zip-with repeat-val
      (cycle (list 1 2))
      (kolakoski)))))))

Lista zwrotów zaczyna się od (1 2). Następnie, aby wygenerować resztę (odczyt od wewnątrz):

• Wywołanie rekurencyjne, (kolakoski)aby uzyskać listę sekwencji Kolakoski (z powodu leniwej oceny nie ma znaczenia, że ​​lista nie została jeszcze w pełni wygenerowana)
• (cycle (list 1 2)) tworzy nieskończoną listę (1 2 1 2 1 2 ...)
• Za pomocą funkcji spakuj dwie nieskończone listy repeat-val. Powtórzy to 1lub 2z cyclelisty jeden lub dwa razy, w zależności od powiązanej wartości z listy Kolakoski. Wynik:((1) (2 2) (1 1) ...)
• flatten ta lista do (1 2 2 1 1 ...)
• Mamy już dwa pierwsze warunki (concat (list 1 2), więc droppierwsze dwa z wygenerowanej listy, aby uniknąć powielania.

Stax , 12 bajtów

╦╥2Bïß▄n»-[╒

Uruchom i debuguj

Jest to reprezentacja ascii tego samego programu.

G@}2R;D{|;^]*m$

Rozszerza sekwencję x razy, gdzie x jest wejściem. Następnie wyprowadza go do X ^th elementu 0 indeksowane.

G }             G jumps to trailing } and returns when done
 @              get xth element in array
   2R           [1, 2]
     ;D         repeat the rest x times
       {     m  map array using block
        |;^]    produces [1] and [2] alternately
            *   repeat array specified number of times
              $ flatten array

Oto dodatkowe 12-bajtowe rozwiązanie, które generuje dane wyjściowe w postaci nieskończonego strumienia. Naciśnij Uruchom, aby rozpocząć.

R, 63 bajty lub 61 bajtów

Implementacja 1: wypisuje n- ^ty termin sekwencji.

x=scan()
a=c(1,2,2)
for(n in 3:x)a=c(a,rep(2-n%%2,a[n]))
a[x]

Implementacja 2: wypisuje pierwsze n warunków sekwencji.

x=scan()
a=c(1,2,2)
for(n in 3:x)a=c(a,rep(2-n%%2,a[n]))
a[1:x]

(Różnica dotyczy tylko ostatniego wiersza).

Tak, tak, możesz narzekać, że moje rozwiązanie jest nieefektywne, że oblicza naprawdę więcej terminów niż jest to potrzebne, ale nadal ...

Aktualizacja: Podziękowania dla @Giuseppe za stratę 9 bajtów.

Język programowania Szekspira, 575 bajtów (ale uszkodzony) lub 653 lub 623 bajtów

,.Puck,.Ford,.Act I:.Scene X:.[Enter Puck and Ford]Ford:You big cat!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you nicer zero?If not,let us Scene X.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

W mocno kwestionowanej kategorii SPL pobiłoby to obecny wpis Jo Kinga (583 bajty), z tym wyjątkiem, że jest wadliwy: po pierwsze, nie działa w wersji TIO (implementacja strony internetowej SPL) - ale działa w Perlu wersja , więc może nie jest to poważna wada. Po drugie, nie wypisuje pierwszych dwóch cyfr. Gdybyśmy dopuścili tę wadę w rozwiązaniu Jo Kinga, wówczas to wadliwe rozwiązanie miałoby 553 bajty, pokonując moje wadliwe rozwiązanie.

Moje rozwiązanie zawodzi w przypadku TIO z dwóch powodów: staramy się polegać na pustym stosie zwracającym zero po wyskakowaniu; i mamy pierwszą scenę z „[Enter Ford and Puck]”, mimo że nikt nie opuścił sceny. Są to tylko ostrzeżenia w wersji Perl. Jeśli naprawię te błędy i wstawię pierwsze dwie cyfry, osiągnę 653 bajty:

 ,.Puck,.Ford,.Act I:.Scene I:.[Enter Puck and Ford]Ford:You cat!Open heart!You big cat!Open heart!You zero!Scene X:.Ford:Remember you!You big cat!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you nicer zero?If not,let us Scene X.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

Wypróbuj online!

Mogę wygenerować pełną sekwencję w implementacji Perla przy użyciu 623 bajtów:

,.Puck,.Ford,.Act I:.Scene I:.[Enter Puck and Ford]Ford:You cat!Open heart!You big cat!Open heart!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you worse a cat?If so,you big cat!If so,let us Scene L.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

Chciałbym jednak zauważyć, że to rozwiązanie jest szybkie w porównaniu z wieloma innymi rozwiązaniami i wykorzystuje logarytmiczne ilości pamięci zamiast przechowywania całej listy. (Jest to podobne do rozwiązania C Vazta, z którym jest daleko związane.) Nie ma to znaczenia dla golfa, ale mimo to jestem z niego zadowolony. Możesz wygenerować milion cyfr w około minutę w Perlu (na przykład, jeśli potokujesz do sed i wc, aby uzyskać liczbę cyfr), gdzie inne rozwiązanie może dać ci kilka tysięcy cyfr.

Wyjaśnienie

Przechowujemy sekwencję zmiennych w kolejności: stos Pucka (od dołu do góry), wartość Pucka, wartość Forda, stos Forda (od góry do dołu). Poza zerowymi wartościami na końcach (z zerowym po lewej stronie może wynikającym z wybicia pustego stosu), każda wartość jest cyfrą wygenerowaną w następnym pokoleniu, z 2 dodanymi, jeśli następne pokolenie musi mieć kolejne dziecko z tego rodzica. Kiedy w sekwencji mamy N niezerowych wartości, generujemy wszystkie dzieci aż do N-tej generacji włącznie, w rodzaju przejścia przez drzewo w pierwszej głębokości. Drukujemy wartości tylko z N-tej generacji. Po całkowitym wygenerowaniu N-tej generacji przechowywane wartości są w rzeczywistości wartościami początkowymi dla generacji 2 do (N + 1), więc dodajemy 2 po lewej stronie i rozpoczynamy od nowa, tym razem generując (N + 1 ) -tego pokolenia.

A więc zarys: Scena X: Kiedy tu dotrzemy, zaczyna się nowa podróż. Krążek == 0. Opcjonalnie wypychamy to zero na stos Pucka i ustawiamy Puck = 2. Scena L: Jeśli Ford == 0, osiągnęliśmy generację drukowania. Jeśli nie, goto V. W przypadku drukowania, jeśli wartość w Pucku została dodana 2, usuń 2 i wydrukuj dwa razy; jeśli nie, wydrukuj go raz. Scena M: Jest to pętla, w której wielokrotnie przełączamy wartość Pucka i wracamy do sekwencji. Powtarzamy, dopóki nie dojdziemy do końca (krążek == 0), w którym to przypadku osiągamy X, lub osiągniemy wartość, która potrzebuje innego dziecka (krążek> 2), w którym to przypadku odejmujemy dodatkowe 2 i idziemy do przodu w V. Scena V: Idziemy do przodu. Jeśli Puck ma 2 lub 4 lata, następne pokolenie będzie zawierać dwoje dzieci z obecnego rodzica, więc Ford + = 2. Przejdź do przodu przez sekwencję. Idź do L, aby sprawdzić zakończenie.

axo , 13 bajtów

[:|[1+{#;1;-_

Wypróbuj online!

Wyjaśnienie

Zaczęło się to jako port alternatywnego rozwiązania w mojej odpowiedzi Wumpus :

2%)[=]&=[O00.

Spowodowało to 18 bajtów. Skończyłem grać w golfa aż do 13 bajtów, które widzisz powyżej, aby dostosować go bardziej do sposobu działania axo. Ta 13-bajtowa wersja ostatecznie zainspirowała ulepszenie do 11 bajtów w Wumpus, więc teraz jest faktycznie bliższa tej wersji.

Podobnie jak w Wumpus, w iteracji i , spód stosu zawiera (i) -1, a góra zawiera pierwszy element i- tego przebiegu, ale pracujemy z 0 i 1 przez cały czas, z wyjątkiem drukowania.

[:    Store a copy of the top of the stack in register A.
|     Pull up a(i)-1 from the bottom of the stack.
[1+{  Print a(i).
#;    If a(i)-1 is 1, push the value in register A.
1;-   Push another copy of that value and subtract it from 1 to swap
      0 and 1 for the next run.
_     Jump back to the beginning of the program.

Rubinowy , 45 39 bajtów

a=*i=0;loop{a+=[k=1+i%2]*p(a[i+=1]||k)}

drukuje w nieskończoność

Wypróbuj online!

Wypróbuj to z funkcją przeciążenia drukowania, która pozwala wybrać separator i liczbę wydrukowanych elementów