Wprowadzenie

Sekwencja Gijswijta ( A090822 ) jest naprawdę, NAPRAWDĘ powolna. Ilustrować:

• Pierwsze 3 pojawiają się w 9 kadencji (w porządku).
• Pierwsze 4 pojawiają się w 220 kadencji (daleko, ale wykonalne).
• Pierwsze 5 pojawia się w (w przybliżeniu) 10 ^ (10 ^ 23) th (tylko nie).
• Nikt tak naprawdę nawet nie wie, gdzie jest pierwsza 6 ... podejrzewa się, że jest na ...

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

Możesz założyć, że nie będziesz musiał mieć do czynienia z dwucyfrowym numerem.

Sekwencja jest generowana w następujący sposób:

1. Pierwszy termin to 1.
2. Każdy następny termin to ilość powtarzających się „bloków” poprzedzających go (jeśli istnieje wiele powtarzających się „bloków”, używana jest największa liczba powtarzających się bloków).

Aby to wyjaśnić, oto kilka pierwszych warunków.

1 -> 1, 1(jeden powtarzający się blok ( 1), więc zapisana cyfra to 1)

1, 1 -> 1, 1, 2(dwa powtarzające się bloki ( 1), więc zapisana cyfra to 2)

1, 1, 2 -> 1, 1, 2, 1(jeden powtarzający się blok ( 2lub 1, 1, 2), więc zapisana cyfra to 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (Masz pomysł)

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

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2(dwa powtarzające się bloki ( 1, 1, 2), więc zapisana cyfra to 2)

Zadanie

Twoim zadaniem jest, jak stwierdzono w pytaniu, wygenerowanie n cyfr sekwencji Gijswijt.

Instrukcje

• Wejście będzie liczbą całkowitą n.
• Twój kod może wypisywać cyfry w dowolnej formie (lista, wiele wyników itp.).

To jest kod golfowy, więc wygrywa najkrótszy kod w bajtach.

Pyth, 25 22 21 bajtów

t_u+eSmtfxG*Td1._GGQN

OP potwierdziło, że musimy obsługiwać tylko liczby jednocyfrowe. Umożliwiło to przechowywanie listy jako ciąg cyfr. -> Zapisano 3 bajty

Wypróbuj online: demonstracja

Wyjaśnienie:

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

Oto jak wygeneruję kolejny numer:

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 bajtów z listami

_u+eSmhhrcGd8SlGGtQ]1

Wypróbuj online: demonstracja

Wykorzystuje te same pomysły Martina i Petera. Na każdym kroku dzielę ciąg na kawałki o długości 1, kawałki o długości 2, ... Następnie koduję je zakresem długości i używam maksymalnego pierwszego przebiegu jako następnej liczby.

20 bajtów z ciągami znaków

t_u+eSmhhrcGd8SlGGQN

Wypróbuj online: demonstracja

Łączy pomysły dwóch powyższych kodów.

CJam, 33 31 30 27 bajtów

Podziękowania dla Petera Taylora za uratowanie 1 bajtu.

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

Sprawdź to tutaj.

Wyjaśnienie

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 bajtów)

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

Demo online

To bardzo wspólny wysiłek Martina.

• Sprytne użycie kodowania długości przebiegu ( e`) w celu identyfikacji powtórzeń należy do Martina
• Tak samo jest w W$celu uproszczenia zarządzania stosami
• Wyeliminowałem kilka operacji zwiększania / zmniejszania za pomocą $W>+specjalnej obudowy, jak wyjaśniono w poniższym rozdziale

Moje pierwsze 30-bajtowe podejście:

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

Demo online

Sekcja

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 bajtów

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

Trzeci wiersz definiuje anonimową funkcję, która przyjmuje liczbę całkowitą i zwraca listę liczb całkowitych. Zobacz to w akcji.

Wyjaśnienie

Funkcja pomocnicza fkonstruuje sekwencję w odwrotnej kolejności, rekurencyjnie sprawdzając, czy poprzednia sekwencja zaczyna się od powtarzanego bloku. kto liczba powtórzeń i pdługość bloku.

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 bajtów

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

Wypróbuj online!

Siatkówka , 66 60 bajtów

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

Wejście jest jednostkową liczbą całkowitą używaną !jako cyfra (chociaż można ją zmienić na dowolny inny znak nienumeryczny). Dane wyjściowe to po prostu ciąg cyfr.

Wypróbuj online! (Alternatywnie, dla wygody jest wersja, która pobiera dane dziesiętne. )

Do celów testowych można to znacznie przyspieszyć za pomocą niewielkiej modyfikacji, która pozwala na testowanie wejścia 220 w mniej niż minutę:

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

Wypróbuj online! ( Wersja dziesiętna. )

Jeśli chcesz przetestować jeszcze większe liczby, najlepiej po prostu podać trochę danych wejściowych i wstawić :po początkowej +. Spowoduje to, że Retina wydrukuje bieżącą sekwencję za każdym razem, gdy zakończy obliczanie nowej cyfry (wszystkie cyfry będą wyłączone jeden po drugim).

Wyjaśnienie

Rozwiązanie składa się z pojedynczego podstawienia wyrażenia regularnego, które jest wielokrotnie stosowane do danych wejściowych, aż wynik przestanie się zmieniać, co w tym przypadku dzieje się, ponieważ wyrażenie regularne już nie pasuje. Na +początku wprowadza się tę pętlę. 1Jest granica, która opowiada Retina tylko wymienić pierwszy mecz (ma to znaczenie tylko dla pierwszej iteracji). W każdej iteracji etap zastępuje jeden !(od lewej) następną cyfrą sekwencji.

Jak zwykle, jeśli potrzebujesz podkładu na grupy równoważące, odsyłam cię do mojej SO odpowiedzi .

Oto opatrzona komentarzem wersja wyrażenia regularnego. Pamiętaj, że celem jest przechwycenie maksymalnej liczby powtarzających się bloków w grupie 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.

Na koniec, po tym wszystkim, piszemy $1(usuwając w ten sposób !), a także liczbę przechwyceń w grupie, z $#1którymi odpowiada maksymalna liczba powtórzeń.

Rubinowy, 84 bajtów

Odpowiedź Retiny zainspirowała mnie do opracowania rozwiązania opartego na wyrażeniach regularnych, aby znaleźć najlepszą sekwencję zamiast jakoś zliczać sekwencje w tablicy, ale z mniejszym geniuszem (negatywne spojrzenia z kwantyfikatorami nie są dozwolone w Ruby, więc wątpię W każdym razie mógłbym bezpośrednio przenieść odpowiedź Retiny)

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

Biorąc pod uwagę już wygenerowaną sekwencję s, odwzorowuje ona wszystkie iod 1do s.length( nw tym przypadku była używana do zapisywania bajtów od n>=s.length), a następnie używa tego wyrażenia regularnego, aby pomóc obliczyć liczbę powtórzeń podsekwencji o długości 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

Jeśli znaleziono dopasowanie o tej długości, oblicza liczbę powtórzeń, dzieląc długość danego dopasowania $&przez idługość podsekwencji; jeśli nie znaleziono dopasowania, jest traktowane jak 1. Następnie funkcja wyszukuje maksymalną liczbę powtórzeń z tego odwzorowania i dodaje tę liczbę na końcu ciągu.