Introdução

A sequência de Gijswijt ( A090822 ) é famosa, MUITO REALMENTE lenta. Ilustrar:

• Os três primeiros aparecem no nono termo (certo).
• Os quatro primeiros aparecem no 220º termo (muito longe, mas viável).
• Os 5 primeiros aparecem (aproximadamente) no 10º (10 ^ 23) termo (apenas não).
• Ninguém sabe mesmo onde estão os 6 primeiros ... suspeita-se que esteja no ...

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

Você pode assumir que não precisará lidar com um número de dois dígitos.

A sequência é gerada da seguinte maneira:

1. O primeiro termo é 1.
2. Cada termo depois disso é a quantidade de "blocos" repetidos anteriores a ele (se houver vários "blocos" repetidos, a maior quantidade de blocos repetidos será usada).

Para esclarecer, aqui estão os primeiros termos.

1 -> 1, 1(um bloco de repetição ( 1), portanto, o dígito gravado é 1)

1, 1 -> 1, 1, 2(dois blocos repetidos ( 1), então o dígito registrado é 2)

1, 1, 2 -> 1, 1, 2, 1(um bloco de repetição ( 2ou 1, 1, 2), portanto, o dígito gravado é 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (Você entendeu a ideia)

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

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2(dois blocos repetidos ( 1, 1, 2), então o dígito registrado é 2)

Tarefa

Sua tarefa é, como indicado na pergunta, gerar n dígitos da sequência Gijswijt.

Instruções

• A entrada será um número inteiro n.
• Seu código pode gerar os dígitos de qualquer forma (uma lista, várias saídas etc.).

Este é o código golf, pelo que o código mais curto em bytes vence.

Pitão, 25 22 21 bytes

t_u+eSmtfxG*Td1._GGQN

O OP confirmou que precisamos apenas lidar com números de um dígito. Isso permitiu armazenar a lista como uma sequência de dígitos. -> 3 bytes salvos

Experimente online: Demonstração

Explicação:

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

E aqui está como eu gero o próximo número:

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 com listas

_u+eSmhhrcGd8SlGGtQ]1

Experimente online: Demonstração

Usa as mesmas idéias de Martin e Peter. A cada passo, divido a corda em pedaços de comprimento 1, pedaços de comprimento 2, ... Então eu os codifico no comprimento-intervalo e uso a primeira execução máxima como número seguinte.

20 bytes com strings

t_u+eSmhhrcGd8SlGGQN

Experimente online: Demonstração

Combina as idéias dos dois códigos acima.

CJam, 33 31 30 27 bytes

Agradecemos a Peter Taylor por economizar 1 byte.

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

Teste aqui.

Explicação

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>+}/

Demonstração online

Este é um esforço conjunto com Martin.

• O uso inteligente da codificação de comprimento de execução ( e`) para identificar repetições é o
• Assim é o uso de W$para simplificar o gerenciamento de pilha
• Eliminei algumas operações de incremento / decremento usando $W>+revestimento especial, conforme explicado na dissecção abaixo

Minha primeira abordagem de 30 bytes:

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

Demonstração online

Dissecação

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

A terceira linha define uma função anônima que pega um número inteiro e retorna uma lista de números inteiros. Veja em ação.

Explicação

A função auxiliar fconstrói a sequência ao contrário, verificando recursivamente se a sequência anterior começa com um bloco repetido. ké o número de repetições e po comprimento do bloco.

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.

Pitão, 41 38 bytes

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

Experimente online!

Retina , 66 60 bytes

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

A entrada é um número inteiro unário usando !como dígito (embora isso possa ser alterado para qualquer outro caractere não numérico). A saída é simplesmente uma sequência de dígitos.

Experimente online! (Como alternativa, por conveniência, aqui está uma versão que aceita entrada decimal. )

Para fins de teste, esta pode ser acelerado um lote com uma pequena modificação, o que permite testar de entrada 220 em menos de um minuto:

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

Experimente online! ( Versão decimal. )

Se você quiser testar números ainda maiores, é melhor fornecer uma entrada massiva e colocar um :após a inicial +. Isso fará com que o Retina imprima a sequência atual sempre que terminar de calcular um novo dígito (com todos os dígitos desativados um por um).

Explicação

A solução consiste em uma única substituição de regex, que é aplicada à entrada repetidamente até que o resultado pare de mudar, o que nesse caso acontece porque o regex não corresponde mais. O +no início apresenta esse loop. O 1é um limite que diz Retina só para substituir o primeiro jogo (isto só é relevante para a primeira iteração). Em cada iteração, o estágio substitui um !(da esquerda) pelo próximo dígito da sequência.

Como de costume, se você precisar de uma cartilha sobre grupos de balanceamento, remeto para a minha resposta SO .

Aqui está uma versão anotada do regex. Observe que o objetivo é capturar o número máximo de blocos repetidos no grupo 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.

Finalmente, depois que tudo estiver pronto, escrevemos de volta $1(excluindo a !) e também o número de capturas no grupo com o $#1qual corresponde ao número máximo de repetições.

Ruby, 84 bytes

A resposta Retina me inspirou a fazer uma solução baseada em regex para encontrar a melhor sequência, em vez de contar de alguma maneira as seqüências em uma matriz, mas com menos genialidade (olhares negativos com quantificadores não parecem permitidos no Ruby, por isso duvido Eu poderia portar diretamente a resposta da Retina de qualquer maneira)

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

Dada uma sequência já gerada s, ele mapeia tudo ide 1até s.length( nfoi usado neste caso para salvar bytes desde então n>=s.length) e, em seguida, usa esse regex para ajudar a calcular o número de repetições de uma subsequência com comprimento 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

Se for encontrada uma correspondência dessa duração, ele calculará o número de repetições dividindo a duração da correspondência fornecida $&por i, a duração da subsequência; se nenhuma correspondência foi encontrada, ela será tratada como 1. A função encontra o número máximo de repetições desse mapeamento e adiciona esse número ao final da sequência.