Einführung

Gijswijts Sequenz ( A090822 ) ist wirklich berühmt, WIRKLICH langsam. Um zu veranschaulichen:

• Die ersten 3 erscheinen im 9. Semester (in Ordnung).
• Die ersten 4 erscheinen im 220. Semester (weit weg, aber machbar).
• Die ersten 5 erscheinen (ungefähr) am 10 ^ (10 ^ 23) -ten Term (nur nein).
• Niemand weiß wirklich, wo die ersten 6 sind ... es wird vermutet, dass es an der ...

  2 ^ (2 ^ (3 ^ (4 ^ 5))).

Sie können davon ausgehen, dass Sie sich nicht mit einer zweistelligen Zahl auseinandersetzen müssen.

Die Sequenz wird wie folgt generiert:

1. Der erste Term ist 1.
2. Jeder Ausdruck danach gibt die Anzahl der "Blöcke" an, die zuvor wiederholt wurden (wenn mehrere "Blöcke" wiederholt wurden, wird die größte Anzahl der wiederholten Blöcke verwendet).

Zur Verdeutlichung hier die ersten Begriffe.

1 -> 1, 1(ein Wiederholungsblock ( 1), also die aufgezeichnete Ziffer ist 1)

1, 1 -> 1, 1, 2(zwei Wiederholungsblöcke ( 1), also die aufgezeichnete Ziffer ist 2)

1, 1, 2 -> 1, 1, 2, 1(ein Wiederholungsblock ( 2oder 1, 1, 2), also die aufgezeichnete Ziffer ist 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (Du hast die Idee)

1, 1, 2, 1, 1 -> 1, 1, 2, 1, 1, 2

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2(zwei Wiederholungsblöcke ( 1, 1, 2), also die aufgezeichnete Ziffer ist 2)

Aufgabe

Ihre Aufgabe ist es, wie in der Frage angegeben, n Ziffern der Gijswijt-Sequenz zu generieren.

Anleitung

• Die Eingabe ist eine Ganzzahl n.
• Ihr Code kann die Ziffern in beliebiger Form ausgeben (eine Liste, mehrere Ausgaben usw.).

Dies ist Code Golf, also gewinnt der kürzeste Code in Bytes.

Pyth, 25 22 21 Bytes

t_u+eSmtfxG*Td1._GGQN

OP hat bestätigt, dass wir nur einstellige Zahlen verarbeiten müssen. Dadurch konnte die Liste als Ziffernfolge gespeichert werden. -> 3 Bytes gespeichert

Probieren Sie es online aus: Demonstration

Erläuterung:

t_u+...GQN      implicit: Q = input number
         N      start with the string G = '"'
  u     Q       do the following Q times:
    ...            generate the next number
   +   G           and prepend it to G
 _              print reversed string at the end
t               remove the first char (the '"')

Und so generiere ich die nächste Nummer:

eSmtfxG*Td1._G
           ._G    generate all prefixes of G
  m               map each prefix d to:
    f     1          find the first number T >= 1, so that:
       *Td              d repeated T times
     xG                 occurs at the beginning of G
 S                  sort all numbers
e                   take the last one (maximum)   

21 Bytes mit Listen

_u+eSmhhrcGd8SlGGtQ]1

Probieren Sie es online aus: Demonstration

Verwendet die gleichen Ideen von Martin und Peter. Bei jedem Schritt teile ich die Zeichenfolge in Stücke der Länge 1, Stücke der Länge 2, ... Dann codiere ich sie in Bereichslängen und verwende den maximalen ersten Lauf als nächste Zahl.

20 Bytes mit Strings

t_u+eSmhhrcGd8SlGGQN

Probieren Sie es online aus: Demonstration

Kombiniert die Ideen der beiden obigen Codes.

CJam, 33 31 30 27 Bytes

Vielen Dank an Peter Taylor für das Speichern von 1 Byte.

1sri({),:)1$W%f/:e`$W=sc+}

Teste es hier.

Erläuterung

1s      e# Initialise the sequence as "1".
ri(     e# Read input N and decrement.
{       e# For each I from 0 to N-1...
  )     e#   Increment to get I from 1 to N.
  ,     e#   Turn into a range [0 1 ... I-1].
  :)    e#   Increment each element to get [1 2 ... I].
  1$    e#   Copy sequence so far.
  W%    e#   Reverse the copy.
  f/    e#   For each element x in [1 2 ... I], split the (reversed) sequence
        e#   into (non-overlapping) chunks of length x. These are the potentially
        e#   repeated blocks we're looking for. We now want to find the splitting
        e#   which starts with the largest number of equal blocks.
  :e`   e#   To do that, we run-length encode each list blocks.
  $     e#   Then we sort the list of run-length encoded splittings, which primarily
        e#   sorts them by the length of the first run.
  W=    e#   We extract the last splitting which starts with the longest run.
  sc    e#   And then we extract the length of the first run by flattening
        e#   the list into a string and retrieving the first character.
  +     e#   This is the new element of the sequence, so we append it.
}/

CJam ( 30 29 27 24 Bytes)

'1ri{{)W$W%/e`sc}%$W>+}/

Online-Demo

Dies ist eine sehr gemeinsame Anstrengung mit Martin.

• Die clevere Verwendung der Lauflängencodierung ( e`) zum Identifizieren von Wiederholungen ist die von Martin
• So wird die Verwendung von W$zur Vereinfachung der Stapelverwaltung
• Ich habe einige Inkrementierungs- / Dekrementierungsoperationen mit einer $W>+speziellen Hülle eliminiert , wie in der folgenden Sektion erläutert

Mein erster 30-Byte-Ansatz:

1ari{,1$f{W%0+_@)</{}#}$W>+}/`

Online-Demo

Präparation

1a        e# Special-case the first term
ri{       e# Read int n and iterate for i=0 to n-1
  ,1$f{   e#   Iterate for j=0 to i-1 a map with extra parameter of the sequence so far
    W%0+  e#     Reverse and append 0 to ensure a non-trivial non-repeating tail
    _@)</ e#     Take the first j+1 elements and split around them
    {}#   e#     Find the index of the first non-empty part from the split
          e#     That's equivalent to the number of times the initial word repeats
  }
  $W>+    e#   Add the maximal value to the sequence
          e#   NB Special case: if i=0 then we're taking the last term of an empty array
          e#   and nothing is appended - hence the 1a at the start of the program
}/
`         e# Format for pretty printing

Haskell, 97 Bytes

f 1=[1]
f n|x<-f$n-1=last[k|k<-[1..n],p<-[1..n],k*p<n,take(k*p)x==([1..k]>>take p x)]:x
reverse.f

Die dritte Zeile definiert eine anonyme Funktion, die eine Ganzzahl annimmt und eine Liste von Ganzzahlen zurückgibt. Sehen Sie es in Aktion.

Erläuterung

Die Hilfsfunktion erstellt fdie Sequenz in umgekehrter Reihenfolge, indem sie rekursiv überprüft, ob die vorherige Sequenz mit einem wiederholten Block beginnt. kist die Anzahl der Wiederholungen und pdie Länge des Blocks.

f 1=[1]                                   -- Base case: return [1]
f n|x<-f$n-1=                             -- Recursive case; bind f(n-1) to x.
  last[k|k<-[1..n],                       -- Find the greatest element k of [1..n] such that
  p<-[1..n],                              -- there exists a block length p such that
  k*p<n,                                  -- k*p is at most the length of x, and
  take(k*p)x                              -- the prefix of x of length p*k
    ==                                    -- is equal to
  ([1..k]>>take p x)                      -- the prefix of length p repeated k times.
  ]:x                                     -- Insert that k to x, and return the result.
reverse.f                                 -- Composition of reverse and f.

Pyth, 41 38 Bytes

J]1VSQ=J+h.MZmh+fn@c+J0dT<JdSNZSNJ;P_J

Probieren Sie es online!

Retina , 66 60 Bytes

+1`((\d+)?(?<1>\2)*(?<!\3(?>(?<-1>\3)*)(?!.*\2)(.+)))!
$1$#1

Die Eingabe ist eine unäre Ganzzahl, die verwendet wird ! als Ziffer verwendet wird (obwohl dies in ein anderes nicht numerisches Zeichen geändert werden kann). Die Ausgabe ist einfach eine Folge von Ziffern.

Probieren Sie es online! (Alternativ dazu finden Sie hier eine Version, die dezimale Eingaben akzeptiert. )

Für Testzwecke kann dies beschleunigt werden , bis eine Menge mit einer geringen Modifikation, die von Eingang Tests ermöglicht 220 in weniger als eine Minute:

+1`((\d+)?(?<1>\2)*(?=!)(?<!\3(?>(?<-1>\3)*)(?!.*\2)(.+)))!
$1$#1

Probieren Sie es online! ( Dezimalversion. )

Wenn Sie noch größere Zahlen testen möchten, geben Sie am besten einfach eine massive Eingabe ein und setzen Sie ein :nach dem Anfangsbuchstaben +. Dies veranlasst Retina, die aktuelle Sequenz jedes Mal zu drucken, wenn die Berechnung einer neuen Ziffer abgeschlossen ist (mit allen Ziffern nacheinander).

Erläuterung

Die Lösung besteht aus einer einzelnen Regex-Ersetzung, die wiederholt auf die Eingabe angewendet wird, bis sich das Ergebnis nicht mehr ändert. In diesem Fall stimmt die Regex nicht mehr überein. Das +am Anfang führt diese Schleife ein. Das 1ist eine Grenze , die sagt Retina nur das erste Spiel ersetzen (das zur ersten Iteration nur relevant ist). In jeder Iteration ersetzt die Stufe eine! (von links) durch die nächste Ziffer der Sequenz.

Wenn Sie eine Grundierung für Bilanzkreise benötigen, verweise ich Sie wie gewohnt auf meine SO-Antwort .

Hier ist eine kommentierte Version des regulären Ausdrucks. Beachten Sie, dass das Ziel darin besteht, die maximale Anzahl wiederholter Blöcke in einer Gruppe zu erfassen 1.

(                 # Group 1, this will contain some repeated block at the end
                  # of the existing sequence. We mainly need this so we can
                  # write it back in the substitution. We're also abusing it
                  # for the actual counting but I'll explain that below.
  (\d+)?          # If possible (that is except on the first iteration) capture
                  # one of more digits into group 2. This is a candidate block
                  # which we're checking for maximum repetitions. Note that this
                  # will match the *first* occurrence of the block.
  (?<1>\2)*       # Now we capture as many copies of that block as possible
                  # into group 1. The reason we use group 1 is that this captures
                  # one repetition less than there is in total (because the first
                  # repetition is group 2 itself). Together with the outer
                  # (unrelated) capture of the actual group one, we fix this
                  # off-by-one error. More importantly, this additional capture
                  # from the outer group isn't added until later, such that the
                  # lookbehind which comes next doesn't see it yet, which is
                  # actually very useful.
                  # Before we go into the lookbehind note that at the end of the
                  # regex there's a '!' to ensure that we can actually reach the
                  # end of the string with this repetition of blocks. While this 
                  # isn't actually checked until later, we can essentially assume
                  # that the lookbehind is only relevant if we've actually counted
                  # repetitions of a block at the end of the current sequence.

  (?<!            # We now use a lookbehind to ensure that this is actually the
                  # largest number of repetitions possible. We do this by ensuring
                  # that there is no shorter block which can be matched more
                  # often from the end than the current one. The first time this
                  # is true (since, due to the regex engine's backtracking rules,
                  # we start from longer blocks and move to shorter blocks later),
                  # we know we've found the maximum number of repetitions.
                  # Remember that lookbehinds are matched right-to-left, so
                  # you should read the explanation of the lookbehind from
                  # bottom to top.
    \3            # Try to match *another* occurrence of block 3. If this works,
                  # then this block can be used more often than the current one
                  # and we haven't found the maximum number of repetitions yet.
    (?>           # An atomic group to ensure that we're actually using up all
                  # repetitions from group 1, and don't backtrack.
      (?<-1>\3)*  # For each repetition in group 1, try to match block 3 again.
    )
    (?!.*\2)      # We ensure that this block isn't longer than the candidate
                  # block, by checking that the candidate block doesn't appear
                  # right of it.
    (.+)          # We capture a block from the end into group 3.
  )               # Lookbehind explanation starts here. Read upwards.
)
!                 # As I said above, this ensures that our block actually reaches
                  # the end of the string.

Nachdem dies alles erledigt ist, schreiben wir zurück $1(und löschen damit die !) sowie die Anzahl der Captures in der Gruppe, mit $#1denen die maximale Anzahl der Wiederholungen übereinstimmt.

Ruby, 84 Bytes

Die Retina-Antwort hat mich dazu inspiriert, eine auf Regex basierende Lösung zu entwickeln, um die beste Sequenz zu finden, anstatt Sequenzen in einem Array zu zählen, aber mit weniger Genialität (negative Lookbehinds mit Quantifizierern scheinen in Ruby nicht erlaubt zu sein, daher bezweifle ich Ich könnte Retinas Antwort sowieso direkt portieren.)

->n{s='';n.times{s+=(1..n).map{|i|s=~/(\d{#{i}})\1+$/?$&.size/i: 1}.max.to_s};s[-1]}

Bei einer bereits generierten Sequenz swerden alle ivon 1bis zugeordnet s.length( nwurde in diesem Fall zum Speichern von Bytes verwendet n>=s.length). Anschließend wird diese Regex verwendet, um die Anzahl der Wiederholungen einer Teilsequenz mit der Länge zu berechnen i:

/(.{#{i}})\1+$/
/(                 # Assign the following to group 1
  .{#{i}}          # Match `i` number of characters
         )         # End group 1
          \1+      # Match 1 or more repetitions of group 1
             $/    # Match the end of string

Wenn eine Übereinstimmung mit dieser Länge gefunden wird, berechnet sie die Anzahl der Wiederholungen, indem die Länge der angegebenen Übereinstimmung $&durch idie Länge der Teilsequenz dividiert wird . Wenn keine Übereinstimmung gefunden wurde, wird es als behandelt 1. Die Funktion ermittelt dann die maximale Anzahl von Wiederholungen aus dieser Zuordnung und fügt diese Anzahl am Ende der Zeichenfolge hinzu.