introduction

La séquence de Gijswijt ( A090822 ) est connue pour être vraiment, VRAIMENT lente. Pour illustrer:

• Les 3 premiers apparaissent dans le 9ème terme (d'accord).
• Les 4 premiers apparaissent au 220ème trimestre (loin, mais faisables).
• Les 5 premiers apparaissent à (approximativement) le 10 ^ (10 ^ 23) ème terme (tout simplement pas).
• Personne ne sait vraiment où sont les 6 premiers ... on soupçonne que c'est au ...

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

Vous pouvez supposer que vous n'aurez pas à traiter avec un nombre à deux chiffres.

La séquence est générée comme suit:

1. Le premier terme est 1.
2. Chaque terme après cela est la quantité de "blocs" de répétition qui le précède (s'il y a plusieurs "blocs" de répétition, la plus grande quantité de blocs de répétition est utilisée).

Pour clarifier, voici les premiers termes.

1 -> 1, 1(un bloc répétitif ( 1), donc le chiffre enregistré est 1)

1, 1 -> 1, 1, 2(deux blocs répétitifs ( 1), donc le chiffre enregistré est 2)

1, 1, 2 -> 1, 1, 2, 1(un bloc répétitif ( 2ou 1, 1, 2), donc le chiffre enregistré est 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (vous avez eu l'idée)

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

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2(deux blocs répétitifs ( 1, 1, 2), donc le chiffre enregistré est 2)

Tâche

Votre tâche consiste, comme indiqué dans la question, à générer n chiffres de la séquence de Gijswijt.

Instructions

• L'entrée sera un entier n.
• Votre code peut sortir les chiffres sous n'importe quelle forme (une liste, plusieurs sorties, etc.).

C'est le code golf, donc le code le plus court en octets l'emporte.

Pyth, 25 22 21 octets

t_u+eSmtfxG*Td1._GGQN

OP a confirmé que nous ne devons gérer que des nombres à un chiffre. Cela a permis de stocker la liste sous forme de chaîne de chiffres. -> enregistré 3 octets

Essayez-le en ligne: Démonstration

Explication:

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 '"')

Et voici comment je génère le numéro suivant:

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 octets avec listes

_u+eSmhhrcGd8SlGGtQ]1

Essayez-le en ligne: Démonstration

Utilise les mêmes idées que Martin et Peter. À chaque étape, je divise la chaîne en morceaux de longueur 1, morceaux de longueur 2, ... Ensuite, je les encode en longueur et j'utilise le premier tirage maximal comme numéro suivant.

20 octets avec des chaînes

t_u+eSmhhrcGd8SlGGQN

Essayez-le en ligne: Démonstration

Combine les idées des deux codes ci-dessus.

CJam, 33 31 30 27 octets

Merci à Peter Taylor d'avoir économisé 1 octet.

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

Testez-le ici.

Explication

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 octets)

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

Démo en ligne

Il s'agit vraiment d'un effort conjoint avec Martin.

• e`Martin utilise intelligemment l'encodage de longueur d'exécution ( ) pour identifier les répétitions.
• Il en va de même W$pour simplifier la gestion de la pile
• J'ai éliminé quelques opérations d'incrémentation / décrémentation en utilisant $W>+un boîtier spécial, comme expliqué dans la dissection ci-dessous

Ma première approche de 30 octets:

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

Démo en ligne

Dissection

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 octets

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

La troisième ligne définit une fonction anonyme qui prend un entier et retourne une liste d'entiers. Voyez-le en action.

Explication

La fonction d'assistance fconstruit la séquence à l'envers, en vérifiant récursivement si la séquence précédente commence par un bloc répété. kest le nombre de répétitions et pla longueur du bloc.

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 octets

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

Essayez-le en ligne!

Rétine , 66 60 octets

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

L'entrée est un entier unaire utilisant !comme chiffre (bien que cela puisse être changé en n'importe quel autre caractère non numérique). La sortie est simplement une chaîne de chiffres.

Essayez-le en ligne! (Alternativement, pour plus de commodité, voici une version qui prend une entrée décimale. )

À des fins de test, cela peut être accéléré beaucoup avec une petite modification, ce qui permet de tester l'entrée 220 en moins d'une minute:

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

Essayez-le en ligne! ( Version décimale. )

Si vous souhaitez tester des nombres encore plus grands, il est préférable de simplement lui fournir une entrée massive et de mettre un :après l'initiale +. Cela fera en sorte que Retina imprime la séquence actuelle à chaque fois qu'elle termine le calcul d'un nouveau chiffre (avec tous les chiffres décalés un par un).

Explication

La solution consiste en une seule substitution d'expression régulière, qui est appliquée à l'entrée de manière répétée jusqu'à ce que le résultat cesse de changer, ce qui se produit dans ce cas parce que l'expression régulière ne correspond plus. Au +début introduit cette boucle. Il 1s'agit d'une limite qui indique à Retina de ne remplacer que la première correspondance (ceci n'est pertinent que pour la toute première itération). À chaque itération, la scène en remplace une !(à partir de la gauche) par le chiffre suivant de la séquence.

Comme d'habitude, si vous avez besoin d'une introduction sur l'équilibrage des groupes, je vous renvoie à ma réponse SO .

Voici une version annotée de l'expression régulière. Notez que l'objectif est de capturer le nombre maximum de blocs répétés en groupe 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.

Enfin, après tout cela, nous réécrivons $1(supprimant ainsi le !) ainsi que le nombre de captures dans le groupe avec $#1lequel correspond au nombre maximum de répétitions.

Rubis, 84 octets

La réponse Retina m'a inspiré à faire une solution basée sur les expressions rationnelles pour trouver la meilleure séquence au lieu de compter les séquences dans un tableau, mais avec moins de génie (les regards négatifs avec des quantificateurs ne semblent pas être autorisés dans Ruby, donc je doute Je pourrais porter la réponse de Retina directement de toute façon)

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

Étant donné une séquence déjà générée s, il mappe tout ide 1à s.length(a nété utilisé dans ce cas pour économiser des octets depuis n>=s.length) et utilise ensuite cette expression régulière pour aider à calculer le nombre de répétitions d'une sous-séquence de longueur 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

Si une correspondance est trouvée de cette longueur, il calcule le nombre de répétitions en divisant la longueur de la correspondance donnée $&par ila longueur de la sous-séquence; si aucune correspondance n'a été trouvée, elle est traitée comme 1. La fonction recherche ensuite le nombre maximal de répétitions de ce mappage et ajoute ce nombre à la fin de la chaîne.