Berechnen Sie die Kolakoski-Sequenz

54

Dies ist eine Neuauflage einer alten Herausforderung , um die E / A-Anforderungen an unsere aktuellen Standards anzupassen. Dies geschieht, um mehr Sprachen die Teilnahme an einer Herausforderung zu dieser beliebten Sequenz zu ermöglichen. In diesem Meta-Post finden Sie eine Diskussion zum Repost.

Die Kolakoski-Sequenz ist eine unterhaltsame selbstreferenzielle Sequenz, die die Ehre hat, die OEIS-Sequenz A000002 zu sein (und die viel einfacher zu verstehen und zu implementieren ist als A000001). Die Sequenz beginnt mit 1 , besteht nur aus 1 s und 2 s und das Sequenzelement a (n) beschreibt die Länge des n- ten Laufs von 1 s oder 2 s in der Sequenz. Dies definiert eindeutig die Reihenfolge (mit einer Visualisierung der Läufe darunter):

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,...

Ihre Aufgabe ist es natürlich, diesen Ablauf umzusetzen. Sie können dazu eines von drei Formaten auswählen:

  1. Nehmen Sie eine Eingabe n und geben Sie den n- ten Term der Sequenz aus, wobei n entweder bei 0 oder 1 beginnt .
  2. Nehmen Sie eine Eingabe n und geben Sie die Terme bis einschließlich des n- ten Terms der Sequenz aus, wobei n entweder mit 0 oder 1 beginnt (dh entweder die ersten n oder die ersten n + 1 Terme ausgeben ).
  3. Ausgabewerte aus der Sequenz auf unbestimmte Zeit.

Im zweiten und dritten Fall können Sie jedes vernünftige, eindeutige Listenformat auswählen. Es ist in Ordnung, wenn es kein Trennzeichen zwischen den Elementen gibt, da sie per Definition immer eine einzelne Ziffer sind.

Im dritten Fall können Sie, wenn es sich bei Ihrer Einreichung um eine Funktion handelt, auch eine unendliche Liste oder einen Generator in Sprachen zurückgeben, die diese unterstützen.

Sie können ein Programm oder eine Funktion schreiben und eine unserer Standardmethoden zum Empfangen und Bereitstellen von Eingaben verwenden. Beachten Sie, dass diese Lücken standardmäßig verboten sind.

Das ist , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .

Martin Ender
quelle
Verwandt , aber kein Betrüger.
Magic Octopus Urn
Verallgemeinerung des Problems , aber Optimierungen sind wahrscheinlich möglich, da der anfängliche Teil der Sequenz festgelegt ist.
Giuseppe
Während wir gerade dabei sind, habe ich auch eine andere Verallgemeinerung .
Martin Ender

Antworten:

17

Gelee , 7 Bytes

2Rṁxṁµ¡

Dies ist ein vollständiges Programm, das die ersten n Terme ausgibt.

Probieren Sie es online!

Wie es funktioniert

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].                 

Beispiellauf

Sei n = 5 .

Der erste Aufruf der Ketten Wiederholungen 1, 2 zyklisch Länge zu erreichen , 5 , dann jedes Element 5 mal, und kürzt schließlich das Ergebnis zu Länge 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

Dies ergibt eine Liste der Länge 5 . Das erste Element ist das erste Element der Kolakoski-Sequenz.

Der zweite Aufruf der Kette wiederholt 1, 2 zyklisch, um die Länge 5 zu erreichen , und wiederholt dann das k- te Element j- mal, wobei j das k- te Element der vorherigen Liste ist, und schneidet schließlich das Ergebnis auf die Länge 5 ab .

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

   1 2 1 2 1

Dies ergibt eine weitere Liste der Länge 5 . Die ersten beiden Elemente sind die ersten beiden Elemente der Kolakoski-Sequenz.

Der Prozess wird für drei weitere Iterationen fortgesetzt.

   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

Dies sind die ersten fünf Elemente der Kolakoski-Sequenz.

Dennis
quelle
12

Python 2 , 51 Bytes

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

Druckt auf unbestimmte Zeit. Erstellt die Liste, lwährend sie durchlaufen wird. Hängt für jeden Eintrag xvon Kopien von oder an , je nachdem, was sich gegenüber dem aktuell letzten Element befindet.lx12

Die Hauptschwierigkeit liegt im Umgang mit dem anfänglichen selbstreferenziellen Fragment [1,2,2]. Dieser Code druckt nur die Initiale 1,2und fährt von dort fort. Der zusätzliche Druck kostet 12 Bytes. Ohne das:

39 Bytes , die ersten beiden Einträge fehlen:

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

Ein weiterer Ansatz besteht darin, die ersten beiden Einträge speziell zu initialisieren. Wir initialisieren lals, [0,0,2]damit die ersten beiden Einträge nicht zum Anhängen führen, sondern print x or nals gedruckt werden n.

51 Bytes

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

Eine weitere Korrektur besteht darin l=[1], den Wechsel manuell zu initialisieren , zu verfolgen nund den Druckvorgang zu korrigieren:

51 Bytes

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

Ohne das (l==[1,1])+funktioniert alles, außer die gedruckten Sequenzen starten 1,1,2statt 1,2,2. Es muss einen besseren Weg geben, um zu erkennen, dass wir uns in diesem zweiten Schritt befinden.

Und noch ein seltsamer Fix, auch irgendwie die selbe Byteanzahl:

51 Bytes

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

Wumpus , 13 11 Bytes

=[=)O?=!00.

Probieren Sie es online!

Druckt die Sequenz unbegrenzt ohne Trennzeichen.

Ich bin wirklich überrascht, wie kurz das ist.

Erläuterung

Die Grundidee ist, die Sequenz auf dem Stapel zu belassen und das unterste Element wiederholt zu verwenden, um einen weiteren Lauf zu generieren und ihn dann zu drucken. Wir missbrauchen den Stack hier effektiv als Warteschlange. Wir können auch ein paar Bytes sparen, indem wir arbeiten 0und 1(nur für die Ausgabe inkrementieren) anstelle von 1und 2, da wir auf diese Weise den Stapel nicht explizit mit einem initialisieren müssen 1und die logische Negation verwenden können, um zwischen den beiden Werten umzuschalten.

     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.
Martin Ender
quelle
10

Brachylog , 30 26 25 23 17 16 14 Bytes

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

Gibt die ersten n Werte aus. Verwendet die "Ausgangsvariable" .für die Eingabe und gibt sie an die "Eingangsvariable" aus ?. Probieren Sie es online!

Erläuterung

Ich bin ziemlich zufrieden damit, wie aussagekräftig dies war: Das Programm ist im Grunde eine allgemeine Beschreibung der Ausgabeliste und ihrer Beziehung zur Eingabe.

~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.

Da {1|2}ᵐListen in lexikografischer Reihenfolge ausprobiert werden, beginnt die Ausgabe mit 1.

Zgarb
quelle
9

Schale , 10 Bytes

Ṡωo↑⁰`Ṙ¢ḣ2

Gibt die ersten n Werte zurück. Probieren Sie es online!

Erläuterung

Ṡω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.

Für Eingabe 20 sieht der Vorgang folgendermaßen aus:

[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]
Zgarb
quelle
1
Hier ist eine Variation, die die Sequenz auf unbestimmte Zeit druckt, die gleiche Byteanzahl, aber vielleicht sehen Sie einige Golfmöglichkeiten, die ich nicht online ausprobiert habe!
Leo
9

Java 10, 155 108 105 100 97 Bytes

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));}

Druckt unbegrenzt ohne Begrenzer.

-3 Bytes nach einem indirekten Hinweis von @Neil .
-5 Bytes dank @MartinEnder .
-3 Bytes für die Konvertierung von Java 8 nach Java 10.

Erläuterung:

Probieren Sie es online aus (Timeout nach 60 Sekunden bei 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`
Kevin Cruijssen
quelle
1
Mir gefällt, wie Sie diesen Look so einfach gemacht haben.
Erik der Outgolfer
@EriktheOutgolfer Danke! :) Als ich die Herausforderung las, war ich mir nicht sicher, wie ich überhaupt anfangen sollte, aber dann traf es mich (unter Verwendung einer Liste mit dem Anfangsbuchstaben [1,2,2]und von dort aus) und ich schrieb die 155-Byte-Antwort (die jetzt mit einem String gespielt wird) statt Liste).
Kevin Cruijssen
Warum nicht (3-i)statt verwenden (1+i%2)?
Erik der Outgolfer
1
@EriktheOutgolfer, da inicht 1 oder 2, sondern der String-Index.
Martin Ender
7

Gelee , 10 Bytes

’߀+\<¹SḂ‘

Gibt den n- ten Term zurück.

Probieren Sie es online!

Wie es funktioniert

’߀+\<¹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.
Dennis
quelle
7

Haskell , 33 Bytes

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

Probieren Sie es online!

Ørjan Johansen sparte 7 Bytes mit einem unwiderlegbaren Muster, um das Präfix zu erzwingen.

xnor
quelle
5
Sie können 7 Bytes sparen, indem Sie es fauler machen. Probieren Sie es online!
Ørjan Johansen
@ ØrjanJohansen Das ist unglaublich und das faule Muster ist magisch für mich. Möchtest du deine eigene Antwort posten?
xnor
Nein, du warst den größten Teil des Weges dorthin. Wenn Sie n:am Anfang des Ausdrucks verwenden, müssen Sie nicht wissen x, dass der erste Ausdruck erzeugt werden soll n. Das Muster muss jedoch faul sein, um zu vermeiden, dass die Funktion es überprüft, bevor Sie zum Menü wechseln n:.
Ørjan Johansen
6

Gol> <> , 8 7 Bytes

:{:PnKz

Probieren Sie es online!

Erläuterung

Dies ist ein Port meiner Wumpus-Antwort . Gol> <> ist im Grunde die Sprache, die über alle notwendigen Funktionen verfügt, um die Wumpus-Antwort zu portieren (insbesondere implizite Nullen am Ende des Stapels, "duplizieren" implementiertes "pop, push, push" und einen Stapelrotationsbefehl), aber :

  • Es hat ein toroidales Gitter, was bedeutet, dass wir nicht explizit 00.zum Anfang zurückspringen müssen.
  • Es hat K, das heißt "pop N, dann dupliziere das nächste Element N-mal", das ersetzt werden kann ?=und ein weiteres Byte speichert.

Das Mapping von Wumpus nach Gol> <> lautet also:

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

Shakespeare Programming Language , 594 583 572 Bytes

Vielen Dank an Ed Wynn für -10 Bytes!

,.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!

Probieren Sie es online!

Dies ist eine Golf-Version von Ed Wynns ungolfed Lösung , ausgehend von der 828-Byte-Lösung, die er in den Kommentaren verlinkt hat und die ein wenig verrückt macht.

Erläuterung:

,.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!
Scherzen
quelle
Nett! Sie können 7 Bytes sparen, indem Sie festlegen, dass das einzelne untergeordnete Element (-1 oder 0) anstelle der Zwillinge ist. Dies kostet Sie 1 Byte kurz vor der Szene X (wenn "Wenn ja" zu "Wenn nicht" wird) und ein weiteres Byte kurz nach der Szene X-Schleife (wenn "Bin ich schöner, Sie" zu "Bin ich schöner, Null" wird). Die Ersparnis besteht darin, dass Sie das "Wenn nicht, erinnern Sie sich an Sie!" mit einfach "Remember I!" eine Zeile früher. Wir fügen entweder ein zweites Kind oder einen Ersatzterminator ein. (Aus diesem Grund müssen Sie das fein abgestimmte "Bin ich nett zu Ihnen?" Ändern - Sie können sich nach Szene X nicht mehr auf Ford == 0 verlassen.) Hier ist TIO, 587 Byte: tinyurl.com/yb9zg4gp
Ed Wynn
Sie können das erste "Wenn ja" in Szene L entfernen und den Befehl an den Anfang von Szene V verschieben. Dadurch sparen Sie nur 1 Byte, da Sie einen neuen "Ford:" benötigen. Sie sparen jedoch ein paar Bytes in Szene I, solange Sie sich darauf verlassen können, dass Ford automatisch auf Null gesetzt wird. Sie haben kein Recht, sich darauf zu verlassen, aber es könnte funktionieren: Hier ist TIO, 584 Bytes: tinyurl.com/y9f6vy7u
Ed Wynn
5

> <> , 13 12 Bytes

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

Probieren Sie es online!

Ein Hafen von Martin Enders Wumpus-Antwort . Leider ><>gibt es weder einen Inkrement- oder Invertierungsbefehl noch implizite Nullen am unteren Ende des Stapels, sodass dieser Vorgang etwas länger dauert.

Scherzen
quelle
1
Ja, das war es, was ich hatte, bevor ich mich an Gol> <> erinnerte. :)
Martin Ender
5

JavaScript, 67 66 60 58 52 51 50 Bytes

Nun, das hat mein Gehirn mehr jucken lassen, als es sollte! Führt den dritten nTerm mit dem Index 0 erneut aus.

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

5 + 1 Bytes gespart dank tsh kratzt mein juckendes Gehirn!


Probier es aus

Das folgende Snippet gibt die ersten 50 Terme aus.


Erläuterung

Dies ist eine der seltenen Situationen, in denen wir einige Variablen außerhalb des Funktionsbereichs deklarieren, sie innerhalb der Funktion ändern und sie bei nachfolgenden Aufrufen der Funktion immer noch wiederverwenden können.

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)
Zottelig
quelle
Was ist mitn=>(g=s=>s[n]||g(s+(++x%2+1)*(10*s[x]-9)))('122',x=1)
tsh
Übrigens, gilt das s='122',x=1,g=n=>s[n]||g(n,s+=(++x%2+1)*(10*s[x]-9))als gültige Vorlage?
tsh
Danke, @tsh. s[n]||war ein klarer Fall, den Wald vor lauter Bäumen nicht zu sehen! Ihr zweiter Vorschlag ist jedoch nicht gültig, da die Funktion nur einmal aufgerufen werden kann. s& xmüssen bei jedem Aufruf initialisiert werden.
Shaggy
die zweite wiederverwendbar, solange nicht sein , sund xnicht von anderen Codes zwischen je Invokes (die Standardeinstellung) berührt.
tsh
1
Nett! s[x]+0-9ist ein ziemlich ordentlicher Trick
JollyJoker
4

Python (2 und 3), 65 bis 60 Bytes

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

Gibt den n- ten Eintrag mit dem Index 0 zurück.

Alternative (65 Bytes):

f=lambda n:n>1and sum([f(i)*[i%2+1]for i in range(n)],[])[n]or-~n
ManfP
quelle
3
Willkommen bei PPCG!
Martin Ender
1
Sie können (wahrscheinlich habe ich es aber nicht getestet) 5 Bytes in der alternativen Version speichern, indem Sie [1,2,2]als Startwert densum
Rod
4

Haskell , 48 Bytes

-1 byte dank nimi. -2 Bytes dank Lynn.

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

Probieren Sie es online!

Wiederhole jedes Element seiner Position mod 2 + 1 mal.

total menschlich
quelle
Sie können zwei weitere sparen, indem Siec=1:2:c
Lynn
4

Brainfuck , 61 Bytes

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

Probieren Sie es online!

Druckt Zahlen auf unbestimmte Zeit als Zeichencodes. Aus Gründen der Übersichtlichkeit wird hier eine Version in Zahlen gedruckt (mit Ausnahme der ersten beiden Elemente, die leicht zu überprüfen sind).

Wie es funktioniert:

+.+. 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
]
Scherzen
quelle
4

05AB1E , 12 9 Bytes

3 Bytes dank Grimy gespart

Druckt die ersten n Elemente.

Δ2LÞsÅΓI∍

Probieren Sie es online!

Erläuterung

Δ           # 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
Emigna
quelle
Die Lauflängendekodierung ist jetzt integriert, dies kann also einfach sein 2L[2LÞsÅΓ.
Grimmy
Oder noch besser: ∞[2LÞsÅΓ.
Grimmy
Oder Δ2LÞsÅΓI∍für eine Version, die die ersten n Elemente bei Eingabe von n druckt.
Grimmy
@ Grimy: Danke! Ich mag die erste n-Version seit es tatsächlich endet :)
Emigna
3

05AB1E , 15 Bytes

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

Probieren Sie es online! oder mit einem Iterationslimit

Erläuterung

Ƶ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
Emigna
quelle
Statt ¸«, =würde sie für 2 Bytes gespeichert drucken. ƵLS[NÌ©èF®É>=, keine Notwendigkeit zu täuschen, wenn Sie nicht verbrauchen.
Magic Octopus Urn
@MagicOctopusUrn: Ich produziere jedoch nicht die ersten 3 Artikel, daher funktioniert das Drucken leider nicht
Emigna
3

J , 12 Bytes

Funktion mit einem Argument, die n nimmt und die ersten n Terme erzeugt. Probieren Sie es online!

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

Ich möchte nur meine alte Antwort auf die alte Frage erläutern .

I.ist ein Verb, das ein Array von Zahlen aufnimmt und eine Liste von Indizes ausspuckt. Wenn also das k- te Element im Array n ist , erscheint der Index k n- mal. Wir werden es verwenden, um die Kolakowski-Sequenz von einem Anfangssamen hochzufahren. Jeder Schritt wird wie folgt ausgeführt:

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) 

Wenn wir diese Operation ( 1+2|I.) ab 10 immer wieder ausführen , sieht das ungefähr so ​​aus:

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

Beachten Sie, wie wir jedes Mal mehr und mehr korrekte Ausdrücke erhalten und nach einer Weile die ersten n Ausdrücke festgelegt werden. Die Anzahl der Iterationen, die erforderlich sind, um sich zu beruhigen, ist schwer genau zu beschreiben, aber es scheint in n grob logarithmisch zu sein. Wenn wir es also n- mal ausführen ( ^:]), sollte es in Ordnung sein. (Weitere Informationen finden Sie in diesen anderen OEIS-Sequenzen: Generierungslängen , Teilsummen .)

Sobald wir damit fertig sind, müssen wir nur noch die ersten n Terme verwenden $. Die Konstruktion $vfür jedes Verb vist ein Beispiel für einen Hook, und nwenn Sie es als Argument angeben, wird sie ausgeführt n $ (v n).

Hier ist die alte 13-Bit - Version , die weit weniger Verschwendung von Zeit und Raum ist: ($1+2|I.)^:_~. Die Eingabe wird bei jedem Schritt abgeschnitten, sodass genau so oft ausgeführt werden kann, wie zum Einschwingen erforderlich, und nicht mehr linear.

algorithmshark
quelle
Oh das funktioniert perfekt mit I.. Ich wollte schon immer die Kopierfunktion sehen, die in einigen Golfspielen verwendet wird.
Meilen
3

Fueue , 30 Bytes

Fueue ist ein warteschlangenbasierter Esolang, bei dem sich das laufende Programm und seine Daten in derselben Warteschlange befinden, die Ausführung die Warteschlange zyklisch durchläuft und die Programmierung viel Synchronisation erfordert, um zu verhindern, dass etwas zur falschen Zeit ausgeführt wird.

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

Probieren Sie es online!

Das obige druckt eine endlose Liste von Ziffern als Steuercodes. Für 34 Bytes können tatsächliche Ziffern ausgegeben werden:

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

Probieren Sie es online!

Der Rest der Erklärung verwendet die letztere Version.

Zusammenfassung der Fueue-Elemente

Die Warteschlange Fueue kann die folgenden Elemente enthalten:

  • Ganzzahlen, die bei der Ausführung ihren Unicode-Codepunkt ausgeben,
  • Durch eckige Klammern begrenzte Unterprogrammblöcke, die gnädigerweise inaktiv sind (nur bis zum Ende der Warteschlange), sofern die )Funktion sie nicht entsperrt , und
  • Einzelzeichenfunktionen, die ausgeführt werden, wenn ihnen die richtigen Argumenttypen folgen und ansonsten inaktiv bleiben.
    • Die einzigen Funktionen, die in diesem Programm verwendet werden, sind ~(zwei folgende Elemente tauschen), :(nächstes Element duplizieren) und )(folgenden Block deblockieren).

Übersicht auf hoher Ebene

Während der Hauptschleife des Programms besteht die Warteschlange aus:

  • eine Kette von Blöcken, die Ziffern darstellen, durch die iteriert werden soll;
    • Eine Ziffer 1 oder 2 ist durch die Blöcke dargestellt [49]und [50:]bezeichnet.
  • Ein sich selbst replizierender Hauptschleifenabschnitt, der die Ziffernblöcke durchläuft und abwechselnd 1s und 2s nach ihnen setzt und sie dann entsperrt.
    • Ein entsperrter Ziffernblock druckt seine eigene Ziffer d und erstellt dann d Kopien des folgenden Blocks, wodurch die Ziffern für den beschriebenen Lauf erstellt werden.

Low-Level-Trace der ersten 10 Befehle

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:])~)~~

Exemplarische Vorgehensweise einer vollständigen Iteration der Hauptschleife

Optionales Leerzeichen wurde eingefügt, um Befehle zu trennen.

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

Zyklus 1: 49druckt 1. )ist inaktiv und wartet darauf, mit dem Hauptschleifenblock zusammengeführt zu werden. 50druckt 2. :dupliziert den Hauptschleifenblock (der eine Kopie für die Selbstreplikation benötigt.)

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

Zyklus 2: )Deblockiert den ersten Hauptschleifenblock, sodass er mit der Ausführung des nächsten Zyklus beginnt.

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

Zyklus 3: Stellt [50:]die erste in der Kette erzeugte Ziffer dar, die 2noch nicht entsperrt ist. Das Folgende )wird dies schließlich tun, nachdem der Rest der Hauptschleife ihn durchlaufen hat. ~)~:~ist eine golfene (mit einem Swap und einer Kopie) Verzögerung von einem Zyklus ~)~~. [[49]:~))~:~~]ist inaktiv. ~tauscht den folgenden Hauptschleifenblock hinter den [50:]Ziffernblock.

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

Zyklus 4: )wartet noch, ~)~produziert ~), ~springt [[49]:~))~:~~]über den [50:]Ziffernblock hinaus.

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

Zyklus 5: ~Wechselt )über den [50:]Ziffernblock hinaus.

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

Zyklus 6: Der erste )entsperrt jetzt den Ziffernblock [50:], der nächste )entsperrt das Unterprogramm [[49]:~))~:~~].

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

Zyklus 7: 50druckt 2, :dupliziert den gerade erzeugten [49]Ziffernblock und erzeugt einen Lauf von zwei 1Sekunden. :~))~:~ist eine Verzögerung von einem Zyklus von ~~))~:. ~tauscht den verbleibenden Hauptschleifenblock nach dem ersten aus [49].

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

Zyklus 8: ~~))ist eine Verzögerung von einem Zyklus )~). ~Swaps :vorbei an der aktuell durchquerten [49].

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

Zyklus 9: ~tauscht )vorbei [49]. :dupliziert den Hauptschleifenblock.

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

Zyklus 10: Der erste )löst die [49]Sperrung des gerade durchlaufenen Ziffernblocks , der zweite )startet die Hauptschleife neu, um den nächsten zu durchlaufen (oben am Anfang der Warteschlange gezeigt).

Ørjan Johansen
quelle
Gute Arbeit! Der Grund, warum ich etwas über Fueue gelernt und die HW-Herausforderung beantwortet habe, weil ich mich tatsächlich mit dieser Herausforderung befasst habe, mich aber zu sehr von der Art der Warteschlangen eingeschüchtert fühlte. Das ist eine wirklich gute Punktzahl für Fueue! :)
Martin Ender
3

x86, 41 37 35 33 28 Bytes

Ich hatte viel Spaß beim Herumspielen mit verschiedenen x86-Anweisungen, da dies meine erste "nicht triviale" x86-Antwort ist. Ich habe zuerst x86-64 gelernt und viele Bytes gespart, indem ich mein Programm auf 32-Bit konvertiert habe.

Es stellt sich heraus, dass der von OEIS verwendete Algorithmus Werte in ein Array überträgt, wodurch es für x86 zugänglich ist und Werte auf dem Stapel gespeichert werden können (beachten Sie, dass MIPS keine Stapelanweisungen hat).

Derzeit nimmt das Programm NWerte als Eingabe in ecxund gibt eine Adresse in ebpeinem Array zurück, wobei das n-te Element den n-ten Wert in der Sequenz darstellt. Ich gehe davon aus, dass die Rückgabe auf dem Stack und die Berechnung zusätzlicher Werte gültig ist (wir betrachten das, was sich hinter dem Array befindet, sowieso als Müll).

Änderungsprotokoll

  • -4 Bytes durch Berechnen x = 2 - n%2mit xorjeder Iteration

  • -2 Bytes mit do-while statt while-Schleife.

  • -2 Bytes durch Drücken der Anfangswerte 1, 2, 2 mit eax

  • -5 - Bytes von nicht speichert nexplizit und stattdessen NSchleifenlaufzeiten

.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

Objektspeicherauszug:

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 
qwr
quelle
3

C (gcc) , 72 71 65 64 62 Bytes

-9 Bytes dank @ceilingcat

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

Probieren Sie es online!

Generiert Werte der Sequenz auf unbestimmte Zeit (Option 3 aus der Challenge)

vazt
quelle
Erklärung bitte! Ich habe keine Ahnung, wie das funktioniert. Es gibt kein Array! Und die Zahlen bleiben zu klein, um eins als Bits zu enthalten.
Ørjan Johansen
@ ØrjanJohansen Ich muss zugeben, ich habe auch keine Ahnung, wie das geht! :) Ich habe die Python-Implementierung von OEIS A000002 übernommen , sie nach C portiert und sie golfen :)
Freitag,
Ah, ich dachte, es könnte etwas gewesen sein, aber ich habe auf dieser Seite nicht weit genug geschaut, um den Python zu finden. Es gibt einen Link zu einer Erklärung , die jedoch im Linkbereich etwas vergraben wurde. Diese Methode passt auf jeden Fall auch zu C.
Ørjan Johansen
1) 56 Bytes in PHP: for($x=$y=-1;;$y=$y+1|$f&.5*$x^=$f=$y&-$y-2)echo$x&1?:2;. 2) 50-x%2sollte ein Byte für Sie speichern. 3) Ich habe versucht, es zum Laufen zu bringen x=y=1; konnte aber noch nicht richtig operieren. Können Sie?
Titus
2

Perl 5 , 36 Bytes

Noch eine triviale Modifikation der klassischen TPR (0,3) -Lösung:

Gibt die Serie von 0bis ausn

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

Probieren Sie es online!

Tonne Hospel
quelle
2

Javascript ES6 - 71 70 68 Bytes

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

1 Bit gespart dank Neil

Danke an Shaggy für die Korrektur meines Fehlers, auch für das Speichern von 1 Bit.

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>

Luis Felipe De Jesus Munoz
quelle
Dies sieht aus wie eine Portierung meiner Java 8-Antwort (außer x=0statt x=1), aber @Shaggy ist in der Tat richtig: Dies funktioniert nicht in der aktuellen Form (ich habe das ,i=100;i-->0temporäre hinzugefügt, um nur die ersten 100 Elemente zu sehen, anstatt es zu müssen) Warten Sie 60 Sekunden, bevor Sie eine Ausgabe sehen. Keine Ahnung, warum es nicht funktioniert. JS ist nicht mein Ding.
Kevin Cruijssen
Die Probleme sind: 1.Initiieren xauf 0 anstelle von 1 (wie @KevinCruijssen erwähnt) und 2.Überprüfen, ob das xth Zeichen in der Zeichenfolge, das immer nur 1 oder 2 sein kann, größer als 49 ist.
Shaggy
2
Hier ist eine heruntergespielte (aber nicht vollständig getestete) Version der festen Lösung: tio.run/…
Shaggy
(_[x]*10-9)als(_[x]>1?11:1)
l4m2
2

Appleseed , 89 Bytes

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

Definiert eine Funktion K, die keine Argumente akzeptiert und die Kolakoski-Sequenz als unendliche Liste zurückgibt. Probieren Sie es online!

Dieser Ansatz wurde durch die Haskell-Antwort von Totalhuman inspiriert . Mein ursprünglicher Ansatz war länger und war wahrscheinlich O (2 ^ n). : ^ P

Ungolfed

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

Die Retourenliste beginnt mit (1 2). Danach, um den Rest zu generieren (von innen nach außen lesen):

  • Rufen Sie rekursiv (kolakoski)auf, um die Kolakoski-Sequenzliste abzurufen (aufgrund der verzögerten Auswertung spielt es keine Rolle, dass die Liste noch nicht vollständig generiert wurde).
  • (cycle (list 1 2)) Erstellt eine unendliche Liste (1 2 1 2 1 2 ...)
  • Zip die beiden unendlichen Listen zusammen mit der Funktion repeat-val. Dies wiederholt das 1oder 2aus der cycleListe entweder ein- oder zweimal, abhängig vom zugeordneten Wert in der Kolakoski-Liste. Ergebnis:((1) (2 2) (1 1) ...)
  • flatten diese Liste in (1 2 2 1 1 ...)
  • Wir haben bereits die ersten beiden Begriffe von (concat (list 1 2), also dropdie ersten beiden aus der generierten Liste, um Doppelungen zu vermeiden.
DLosc
quelle
2

Stax , 12 Bytes

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

Führen Sie es aus und debuggen Sie es

Dies ist die ASCII-Darstellung desselben Programms.

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

Die Sequenz wird x-mal erweitert, wobei x die Eingabe ist. Dann gibt es das x- te Element mit dem Index 0 aus.

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

Hier ist eine 12-Byte-Bonuslösung, die die Ausgabe als unendlichen Stream erzeugt. Drücken Sie Run, um zu starten.

rekursiv
quelle
2

R, 63 Bytes oder 61 Bytes

Implementierung 1: druckt den n- ten Term der Sequenz aus.

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

Implementierung 2: druckt die ersten n Terme der Sequenz aus.

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

(Der Unterschied ist nur in der letzten Zeile.)

Ja, ja, Sie können sich beschweren, dass meine Lösung ineffizient ist, wirklich mehr Begriffe berechnet als benötigt, aber dennoch ...

Update: Danke an @Giuseppe für das Abschneiden von 9 Bytes.

Andreï Kostyrka
quelle
1
Verwenden Sie a=c(a,rep(2-n%%2,a[n]))anstelle der zweiten forSchleife, um einige Bytes zu entfernen.
Giuseppe
@ Giuseppe umgesetzt, danke!
Andreï Kostyrka
Wir haben nichts dagegen, dass Golflösungen hier ineffizient sind. Tatsächlich ist die Verwendung eines ineffizienten Algorithmus einer der Tipps im Code-Golf- Tag-Wiki .
Ørjan Johansen
2

Shakespeare Programming Language, 575 Bytes (aber fehlerhaft) oder 653 oder 623 Bytes

,.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.

In der heiß umkämpften SPL-Kategorie würde dies Jo Kings aktuellen Eintrag (583 Byte) übertreffen, mit der Ausnahme, dass er fehlerhaft ist: Erstens läuft er nicht in der TIO-Version (Implementierung der SPL-Website), sondern in Perl Version , also vielleicht ist das kein schwerwiegender Defekt. Zweitens werden die ersten beiden Ziffern nicht gedruckt. Wenn wir diesen Fehler in Jo Kings Lösung zulassen würden, wäre diese fehlerhafte Lösung 553 Byte groß und würde meine fehlerhafte Lösung übertreffen.

Meine Lösung schlägt bei TIO aus zwei Gründen fehl: Wir versuchen, einen leeren Stack zu verwenden, der beim Auftauchen Null zurückgibt. und wir kommen zur ersten Szene mit "[Enter Ford and Puck]", obwohl niemand die Bühne verlassen hat. Dies sind lediglich Warnungen in der Perl-Version. Wenn ich diese Fehler behebe und die ersten beiden Ziffern eingebe, erreiche ich 653 Bytes:

 ,.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.

Probieren Sie es online!

Ich kann die vollständige Sequenz in der Perl-Implementierung mit 623 Bytes generieren:

,.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.

Ich möchte jedoch darauf hinweisen, dass diese Lösung im Vergleich zu vielen anderen Lösungen schnell ist und logarithmische Speichermengen verwendet, anstatt die gesamte Liste zu speichern. (Dies ähnelt der C-Lösung von vazt, mit der es in weiter Ferne verwandt ist.) Dies macht keinen Unterschied für den Golfsport, aber ich bin trotzdem zufrieden damit. In Perl können Sie in etwa einer Minute eine Million Stellen erzeugen (z. B., wenn Sie zu sed und wc wechseln, um eine Stellenzählung zu erhalten), wobei die andere Lösung möglicherweise einige tausend Stellen ergibt.

Erläuterung

Wir speichern eine Folge von Variablen in der Reihenfolge: Pucks Stapel (von unten nach oben), Pucks Wert, Ford Wert, Ford Stapel (von oben nach unten). Abgesehen von den Nullwerten an den Enden (mit der Null links, möglicherweise aus dem Poppen eines leeren Stapels), ist jeder Wert die Ziffer, die bei dieser Generation als nächstes generiert wird, wobei 2 hinzugefügt wird, wenn die nächste Generation ein anderes Kind von diesem Elternteil haben muss. Wenn die Sequenz N Nicht-Null-Werte enthält, werden alle untergeordneten Elemente bis einschließlich der N-ten Generation in einer Art Tiefen-Erst-Baumdurchquerung generiert. Wir drucken nur Werte der N-ten Generation. Wenn die N-te Generation vollständig generiert wurde, sind die gespeicherten Werte tatsächlich die Startwerte für die Generationen 2 bis (N + 1), daher fügen wir links eine 2 hinzu und beginnen erneut, wobei wir diesmal die (N + 1) generieren ) -te Generation.

Also ein Überblick: Szene X: Wenn wir hier ankommen, ist dies der Beginn einer neuen Durchquerung. Puck == 0. Wir legen diese Null optional auf Pucks Stapel und setzen Puck = 2. Szene L: Wenn Ford == 0 ist, haben wir die Druckgeneration erreicht. Wenn nicht, gehe zu V. Zum Drucken, wenn der Wert in Puck 2 addiert hat, entferne die 2 und drucke sie zweimal; Wenn nicht, drucken Sie es einmal aus. Szene M: Dies ist eine Schleife, in der wir den Wert von Puck wiederholt umschalten und durch die Sequenz zurückgehen. Wir wiederholen, bis entweder wir das Ende erreichen (Puck == 0), in diesem Fall gehen wir zu X, oder wir erreichen einen Wert, der ein anderes Kind benötigt (Puck> 2), in diesem Fall subtrahieren wir die zusätzlichen 2 und gehen in V. Szene vorwärts V: Hier gehen wir vorwärts. Wenn Puck 2 oder 4 ist, enthält die nächste Generation zwei Kinder vom aktuellen Elternteil, also Ford + = 2. Schritt vorwärts durch die Sequenz. Gehe zu L, um die Beendigung zu überprüfen.

Ed Wynn
quelle
1

Axo , 13 Bytes

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

Probieren Sie es online!

Erläuterung

Dies begann als Port einer alternativen Lösung in meiner Wumpus-Antwort :

2%)[=]&=[O00.

Dies ergab 18 Bytes. Am Ende habe ich es auf die 13 Bytes herunter gespielt, die Sie oben sehen, um es besser an die Funktionsweise von Axo anzupassen. Diese 13-Byte-Version inspirierte dann die Verbesserung auf 11 Byte in Wumpus. Jetzt ist sie tatsächlich näher an dieser Version.

Wie bei Wumpus enthält auch bei Iteration i der untere Teil des Stapels ein (i) -1 und der obere Teil das erste Element des i- ten Durchlaufs, aber wir arbeiten durchgehend mit 0 und 1 , außer beim Drucken.

[:    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.
Martin Ender
quelle