Вступление

Последовательность Gijswijt ( A090822 ) классно действительно, очень медленно. Проиллюстрировать:

• Первые 3 появляются в 9-м семестре (хорошо).
• Первые 4 появляются в 220-м семестре (далеко, но выполнимо).
• Первые 5 появляются в (приблизительно) 10 ^ (10 ^ 23) -ом члене (просто нет).
• Никто на самом деле даже не знает, где первые 6 ... подозревается, что это на ...

  2 ^ (2 ^ (3 ^ (4 ^ 5))) -й срок.

Вы можете предположить, что вам не придется иметь дело с двузначным числом.

Последовательность генерируется так:

1. Первый член - 1.
2. Каждый термин после этого представляет собой количество повторяющихся «блоков», предшествующих ему (если имеется несколько повторяющихся «блоков», используется наибольшее количество повторяющихся блоков).

Чтобы уточнить, вот несколько первых терминов.

1 -> 1, 1(один повторяющийся блок ( 1), поэтому записанная цифра равна 1)

1, 1 -> 1, 1, 2(два повторяющихся блока ( 1), поэтому записанная цифра равна 2)

1, 1, 2 -> 1, 1, 2, 1(один повторяющийся блок ( 2или 1, 1, 2), поэтому записанная цифра 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (вы поняли)

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

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2(два повторяющихся блока ( 1, 1, 2), поэтому записанная цифра равна 2)

задача

Ваша задача, как указано в вопросе, сгенерировать n цифр последовательности Gijswijt.

инструкции

• Ввод будет целым числом n.
• Ваш код может выводить цифры в любой форме (список, несколько выходов и т. Д.).

Это код гольф, поэтому выигрывает самый короткий код в байтах.

Pyth, 25 22 21 байт

t_u+eSmtfxG*Td1._GGQN

ОП подтвердил, что нам нужно обрабатывать только однозначные числа. Это позволило сохранить список в виде строки цифр. -> Сохранено 3 байта

Попробуйте онлайн: демонстрация

Объяснение:

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

И вот как я генерирую следующее число:

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 байт со списками

_u+eSmhhrcGd8SlGGtQ]1

Попробуйте онлайн: демонстрация

Используются те же идеи Мартина и Питера. На каждом шаге я делю строку на куски длиной 1, куски длиной 2, ... Затем я кодирую их по длине диапазона и использую максимальный первый прогон в качестве следующего числа.

20 байтов со строками

t_u+eSmhhrcGd8SlGGQN

Попробуйте онлайн: демонстрация

Объединяет идеи двух кодов выше.

CJam, 33 31 30 27 байтов

Спасибо Питеру Тейлору за сохранение 1 байта.

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

Проверьте это здесь.

объяснение

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 байта)

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

Онлайн демо

Это очень совместные усилия с Мартином.

• Умное использование кодировки длин серий ( e`) для определения повторений принадлежит Мартину
• Так что использование W$для упрощения управления стека
• Я исключил пару операций увеличения / уменьшения, используя $W>+специальный регистр, как объяснено в рассечении ниже

Мой первый 30-байтовый подход:

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

Онлайн демо

рассечение

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 байт

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

Третья строка определяет анонимную функцию, которая принимает целое число и возвращает список целых чисел. Посмотрите это в действии.

объяснение

Вспомогательная функция fсоздает последовательность в обратном порядке, рекурсивно проверяя, начинается ли предыдущая последовательность с повторного блока. kколичество повторений и pдлина блока.

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 байт

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

Попробуйте онлайн!

Сетчатка , 66 60 байт

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

Ввод представляет собой унарное целое число, используемое !в качестве цифры (хотя это можно изменить на любой другой нечисловой символ). Вывод - это просто строка цифр.

Попробуйте онлайн! (В качестве альтернативы для удобства приведена версия с десятичным вводом. )

Для целей тестирования, это может быть ускорено много с небольшой модификацией, которая позволяет тестировать ввод 220 в течение одной минуты:

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

Попробуйте онлайн! ( Десятичная версия. )

Если вы хотите протестировать еще большие числа, лучше просто набрать им массивный ввод и поставить :после начального +. Это заставит Retina печатать текущую последовательность каждый раз, когда она заканчивает вычисление новой цифры (со всеми цифрами, сдвинутыми по одной).

объяснение

Решение состоит из одной подстановки регулярного выражения, которая применяется ко входу несколько раз, пока результат не перестанет изменяться, что в этом случае происходит из-за того, что регулярное выражение больше не совпадает. В +начале вводит этот цикл. Это 1предел, который говорит Retina только о замене первого соответствия (это относится только к самой первой итерации). На каждой итерации этап заменяет одну !(слева) следующей цифрой последовательности.

Как обычно, если вам нужен учебник по балансировке групп, я отсылаю вас к моему SO-ответу .

Вот аннотированная версия регулярного выражения. Обратите внимание, что цель состоит в том, чтобы захватить максимальное количество повторяющихся блоков в группе 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.

Наконец, после того, как все это сделано, мы записываем обратно $1(тем самым удаляя !), а также количество перехватов в группе, $#1которым соответствует максимальное количество повторений.

Рубин, 84 байта

Ответ Retina вдохновил меня сделать решение на основе регулярных выражений, чтобы найти лучшую последовательность вместо подсчета последовательности в массиве, но с меньшим количеством гениальности (отрицательные взгляды с квантификаторами не разрешены в Ruby, поэтому я сомневаюсь Я мог бы в любом случае напрямую перенести ответ Retina)

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

Учитывая уже сгенерированную последовательность s, она отображает все iот 1до s.length( nиспользовалась в этом случае для сохранения байтов с тех пор n>=s.length), а затем использует это регулярное выражение, чтобы помочь вычислить количество повторений подпоследовательности с длиной 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

Если совпадение найдено этой длины, он вычисляет количество повторений путем деления длины данного матча $&по i, длина подпоследовательности; если совпадений не найдено, оно рассматривается как 1. Затем функция находит максимальное количество повторений из этого сопоставления и добавляет это число в конец строки.