pengantar

Urutan Gijswijt ( A090822 ) terkenal benar-benar lambat. Menggambarkan:

• 3 pertama muncul dalam istilah ke-9 (baik-baik saja).
• 4 pertama muncul dalam jangka waktu 220 (jauh, tapi layak).
• 5 pertama muncul pada (kurang lebih) istilah 10 ^ (10 ^ 23) (tidak ada).
• Tidak ada yang benar-benar tahu di mana 6 yang pertama ... diduga itu ada di ...

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

Anda dapat berasumsi bahwa Anda tidak perlu berurusan dengan nomor dua digit.

Urutannya dibuat seperti ini:

1. Istilah pertama adalah 1.
2. Setiap istilah setelah itu adalah jumlah "blok" berulang sebelumnya (jika ada beberapa "blok" berulang, jumlah terbesar blok berulang digunakan).

Untuk memperjelas, berikut adalah beberapa istilah pertama.

1 -> 1, 1(satu blok berulang ( 1), sehingga digit yang direkam adalah 1)

1, 1 -> 1, 1, 2(dua blok berulang ( 1), sehingga digit yang direkam adalah 2)

1, 1, 2 -> 1, 1, 2, 1(satu blok berulang ( 2atau 1, 1, 2), sehingga digit yang direkam adalah 1)

1, 1, 2, 1 -> 1, 1, 2, 1, 1 (Anda mendapatkan ide)

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

1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2(dua blok berulang ( 1, 1, 2), sehingga digit yang direkam adalah 2)

Tugas

Tugas Anda adalah, sebagaimana dinyatakan dalam pertanyaan, untuk menghasilkan n digit dari urutan Gijswijt.

Instruksi

• Input akan berupa bilangan bulat n.
• Kode Anda dapat menampilkan digit dalam bentuk apa pun (daftar, banyak keluaran, dll.).

Ini adalah kode golf, jadi kode terpendek dalam byte menang.

Pyth, 25 22 21 byte

t_u+eSmtfxG*Td1._GGQN

OP mengonfirmasi bahwa kita hanya perlu menangani angka satu digit. Ini memungkinkan untuk menyimpan daftar sebagai rangkaian angka. -> Disimpan 3 byte

Cobalah online: Demonstrasi

Penjelasan:

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

Dan inilah cara saya menghasilkan angka berikutnya:

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 byte dengan daftar

_u+eSmhhrcGd8SlGGtQ]1

Cobalah online: Demonstrasi

Menggunakan ide yang sama dari Martin dan Peter. Pada setiap langkah saya membagi string menjadi potongan-potongan dengan panjang 1, potongan-potongan panjang 2, ... Kemudian saya rentang-panjang-encode mereka dan menggunakan run pertama maksimal sebagai nomor berikutnya.

20 byte dengan string

t_u+eSmhhrcGd8SlGGQN

Cobalah online: Demonstrasi

Menggabungkan ide-ide dari dua kode di atas.

CJam, 33 31 30 27 byte

Terima kasih kepada Peter Taylor untuk menghemat 1 byte.

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

Uji di sini.

Penjelasan

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

Demo online

Ini sangat banyak upaya bersama dengan Martin.

• Penggunaan cerdas run-length encoding ( e`) untuk mengidentifikasi pengulangan adalah milik Martin
• Begitu juga penggunaan W$untuk menyederhanakan manajemen tumpukan
• Saya menghilangkan beberapa operasi kenaikan / penurunan dengan menggunakan $W>+casing khusus, seperti yang dijelaskan dalam diseksi di bawah ini

Pendekatan 30 byte pertama saya:

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

Demo online

Pembedahan

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 byte

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

Baris ketiga mendefinisikan fungsi anonim yang mengambil bilangan bulat dan mengembalikan daftar bilangan bulat. Lihat itu dalam aksi.

Penjelasan

Fungsi helper fmembangun urutan secara terbalik, dengan memeriksa secara berulang apakah urutan sebelumnya dimulai dengan blok yang diulang. kadalah jumlah pengulangan, dan ppanjang blok.

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 byte

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

Cobalah online!

Retina , 66 60 byte

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

Input adalah bilangan bulat yang digunakan ! sebagai digit (meskipun itu dapat diubah menjadi karakter non-numerik lainnya). Output hanyalah serangkaian angka.

Cobalah online! (Atau, untuk kenyamanan inilah versi yang mengambil input desimal. )

Untuk tujuan pengujian, ini dapat dipercepat banyak dengan modifikasi kecil, yang memungkinkan pengujian input 220 dalam waktu kurang dari satu menit:

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

Cobalah online! ( Versi desimal. )

Jika Anda ingin menguji angka yang bahkan lebih besar, yang terbaik adalah memberi makan beberapa input besar dan menempatkan :setelah awal+ . Ini akan membuat Retina mencetak urutan saat ini setiap kali selesai menghitung digit baru (dengan semua digit off-by-one).

Penjelasan

Solusinya terdiri dari substitusi regex tunggal, yang diterapkan pada input berulang kali sampai hasilnya berhenti berubah, yang dalam hal ini terjadi karena regex tidak lagi cocok. The +di awal memperkenalkan loop ini. The 1batas yang menceritakan Retina hanya untuk menggantikan pertandingan pertama (ini hanya relevan untuk iterasi pertama). Di setiap iterasi, tahap mengganti satu !(dari kiri) dengan digit berikutnya dari urutan.

Seperti biasa, jika Anda memerlukan primer pada kelompok penyeimbang, saya merujuk Anda ke jawaban SO saya .

Ini adalah versi regex yang beranotasi. Perhatikan bahwa tujuannya adalah untuk menangkap jumlah maksimum blok berulang dalam kelompok 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.

Akhirnya, setelah semua ini dilakukan, kami menulis kembali $1(dengan demikian menghapus !) serta jumlah tangkapan dalam grup $#1yang sesuai dengan jumlah maksimum pengulangan.

Ruby, 84 byte

Jawaban Retina mengilhami saya untuk melakukan solusi berbasis regex untuk menemukan urutan terbaik alih-alih entah bagaimana menghitung urutan dalam array, tetapi dengan sedikit jenius (tampilan negatif dengan quantifier sepertinya tidak diizinkan di Ruby, jadi saya ragu Saya bisa langsung menjawab jawaban Retina)

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

Diberikan urutan yang sudah dibuat s, memetakan semua idari 1ke s.length( ndigunakan dalam kasus ini untuk menyimpan byte sejak n>=s.length) dan kemudian menggunakan regex ini untuk membantu menghitung jumlah pengulangan suatu urutan dengan panjang 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

Jika kecocokan ditemukan dengan panjang itu, ia menghitung jumlah pengulangan dengan membagi panjang kecocokan yang diberikan $&dengan i, panjang dari urutan berikutnya; jika tidak ditemukan kecocokan, itu diperlakukan sebagai 1. Fungsi kemudian menemukan jumlah pengulangan maksimum dari pemetaan ini dan menambahkan nomor itu ke akhir string.