Hasilkan Urutan Linus

14

Definisi

Dari uraian tentang OEIS A006345 :

Untuk menemukan a(n), pertimbangkan a 1atau a 2. Untuk masing-masing, cari sufiks berulang yang terpanjang, yaitu, untuk masing-masing a(n)=1,2, temukan urutan terpanjang sdengan properti yang a(1),...,a(n)diakhiri dengan urutan tersebut ss. Gunakan digit yang menghasilkan akhiran yang lebih pendek. a(1) = 1.

Contoh Berolahraga

a(1)=1.

Jika a(2)=1, kita akan memiliki urutan di 1 1mana substring terlipat ganda dari akhir berada 1. Jika a(2)=2sebaliknya, maka itu akan menjadi substring kosong. Oleh karena itu a(2)=2.

Kapan n=6, kami memilih antara 1 2 1 1 2 1dan 1 2 1 1 2 2. Dalam pilihan pertama, 1 2 1digandakan secara berurutan dari akhir. Dalam pilihan kedua, itu 2malah. Oleh karena itu, a(6)=2.

Kapan n=9, kami memilih antara 1 2 1 1 2 2 1 2 1 dan 1 2 1 1 2 2 1 2 2. Pada pilihan pertama, substring berurutan terpanjang dua kali lipat adalah 2 1, sedangkan pada pilihan kedua 1 2 2digandakan berturut-turut di akhir. Oleh karena itu a(9)=1.

Tugas

Diberikan n, kembali a(n).

Spesifikasi

  • n akan positif.
  • Anda dapat menggunakan 0-diindeks bukannya 1-diindeks. Jika demikian, sebutkan jawaban Anda. Juga, dalam hal ini, nbisa 0juga.

Testcases

Testcases diindeks 1. Namun, Anda dapat menggunakan 0-diindeks.

n  a(n)
1  1
2  2
3  1
4  1
5  2
6  2
7  1
8  2
9  1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1

Referensi

Biarawati Bocor
sumber
1
Dalam kasus uji n=9, pilihan pertama 1 2 1 1 2 2 1 2 1memiliki substring ganda 2 1di akhir.
Sherlock9
1
Perhatikan bahwa halaman OEIS yang tertaut memiliki solusi Perl golf ~ 43 byte.
liori

Jawaban:

7

Haskell, 146 140 137 133 118 byte

s!l|take l s==take l(drop l s)=l|1<2=s!(l-1)
g[w,x]|w<x=1|1<2=2
a 1=1
a n=g$(\s x->(x:s)!n)(a<$>[n-1,n-2..1])<$>[1,2]
Program man
sumber
Apakah Anda benar-benar membutuhkan (\x->(\s->...? Kalau tidak, Anda bisa menulis (\x s->....
flawr
Itu membantu menyelamatkan beberapa
Program man
Selamat datang di PPCG!
betseg
Alih-alih menggunakan batas atas waras div ..., Anda bisa menggunakan yang lebih pendek n. Semua perbandingan ekstra akan menghasilkan false dan tidak mengubah hasilnya.
Christian Sievers
ooh bagus, saya kira saya berasumsi akan crash jika diberi nilai terlalu besar
Program man
6

Python, 137 byte

def a(n,s=[0],r=lambda l:max([0]+filter(lambda i:l[-i:]==l[-i*2:-i],range(len(l))))):
 for _ in[0]*n:s+=[r(s+[0])>r(s+[1])]
 return-~s[n]

Solusi ini menggunakan pengindeksan berbasis 0.

Loovjo
sumber
6

Jelly , 25 24 22 20 byte

2 byte berkat Dennis.

2;€µḣJf;`€$ṪLµÞḢ
Ç¡Ḣ

Cobalah online!

Port jawaban saya di Pyth .

Ç¡Ḣ   Main chain

 ¡    Repeat for (input) times:
Ç         the helper chain
  Ḣ   Then take the first element



2;€µḣJf;`€$ṪLµÞḢ  Helper chain, argument: z

2;€               append z to 1 and 2, creating two possibilities
   µ         µÞ   sort the possibilities by the following:
    ḣJ                generate all prefixes from shortest to longest
       ;`€            append the prefixes to themselves
      f   $           intersect with the original set of prefixes
           Ṫ          take the last prefix in the intersection
            L         find its length
                 Ḣ   take the first (minimum)
Biarawati Bocor
sumber
4

Mathematica, 84 byte

a@n_:=a@n=First@MinimalBy[{1,2},Array[a,n-1]~Append~#/.{___,b___,b___}:>Length@{b}&]
alephalpha
sumber
2

MATL , 34 byte

vXKi:"2:"K@h'(.+)\1$'XXgn]>QhXK]0)

Cobalah online! atau verifikasi semua kasus uji .

Penjelasan

v             % Concatenate stack vertically: produces empty array
XK            % Copy to clipboard K. This clipboard holds the current sequence
i:            % Take input n. Generate vector [1 2 ... n]
"             % For each k in [1 2 ... n]
  2:          %   Push [1 2]. These are the possible digits for extending the sequence
  "           %     For each j in [1 2]
    K         %       Push contents of clipboard K (current sequence)
    @         %       Push j (1 or 2)
    h         %       Concatenate horizontally: gives a possible extension of sequence
    '(.+)\1$' %       String to be used as regex pattern: maximal-length repeated suffix
    XX        %       Regex match
    gn        %       Convert to vector and push its length: gives length of match
  ]           %    End. We now have the suffix lengths of the two possible extensions
  >           %    Push 1 if extension with "1" has longer suffix than with "2"; else 0 
  Q           %    Add 1: gives 2 if extension with "1" produced a longer suffix, or 1
              %    otherwise. This is the digit to be appended to the sequence
  h           %    Concatenate horizontally
  XK          %    Update clipboard with extended sequence, for the next iteration
]             % End
0)            % Get last entry (1-based modular indexing). Implicitly display
Luis Mendo
sumber
2

Python 2, 94 byte

import re
s='1'
exec"s+=`3-int(re.search(r'(.*)(.)\\1$',s).groups()[1])`;"*input()
print s[-1]

Menggunakan pengindeksan berbasis 0. Uji di Ideone .

Dennis
sumber
2

Pyth , 26 byte

huh.mleq#.<T/lT2._b+RGS2QY

Suite uji.

Penjelasan

Kapan n = 6, kami memilih antara 1 2 1 1 2 1dan 1 2 1 1 2 2.

Kami menghasilkan dua kemungkinan ini, dan kemudian melihat sufiks mereka.

Untuk yang pertama, akhiran adalah: 1, 2 1, 1 2 1, 1 1 2 1, 2 1 1 2 1, 1 2 1 1 2 1.

Kami memfilter sufiks berlipat ganda dengan memeriksa apakah sufiksnya sama setelah memutarnya dengan panjang dibagi 2 (ternyata pemeriksaan ini tidak sempurna, karena menegaskan 1dan 2juga).

Kami mengambil akhiran dua kali lipat terakhir dan kemudian panjangnya.

Kami kemudian memilih kemungkinan yang sesuai dengan panjang minimum yang dihasilkan di atas.

Kemudian kita lanjutkan ke nilai selanjutnya dari n.

Untuk tujuan program ini, pemain golflah yang menghasilkan array yang terbalik.

huh.mleq#.<T/lT2._b+RGS2QY
 u                      QY   repeat Q (input) times,
                             start with Y (empty array),
                             storing the temporary result in G:
                   +RGS2         prepend 1 and 2 to G,
                                 creating two possibilities
   .m             b              find the one that
                                 makes the following minimal:
                ._                   generate all prefixes
       q#                            filter for prefixes as T
                                     that equals:
         .<T/lT2                         T left-rotated
                                         by its length halved
      e                              take the last one
     l                               generate its length
  h                              take the first minimal one
h                                take the first one from the generated
                                 array and implicitly print it out
Biarawati Bocor
sumber
2

Pyth, 46 29 byte

Mengambil beberapa inspirasi dari jawaban Pyth yang sangat bagus dari @Leaky Nun. Mencoba melihat apakah ada cara yang lebih pendek menggunakan string. Masih 3 byte pendek!

huh.melM+kf!x>blTT._bm+dGS2Qk

Anda bisa mencobanya di sini .

Berirama
sumber
Menggunakan red uce bukannya for-loop secara eksplisit menghemat 4 byte
Leaky Nun
2

Retina , 51 42 byte

9 byte berkat Martin Ender.

.+
$*x
+`((.*)(^|2|(?<3>1))\2)x
$1$#3
!`.$

Cobalah online!

Port jawaban ini .

Biarawati Bocor
sumber
2

Perl, 40 byte

$a.=/(.*)(.)\1$/^$2for($a)x$_;$_=$a%5+1

Panjang kode 39 byte dan membutuhkan -psakelar ( +1 byte).

Loop diilhami oleh solusi Perl pada yang relevan halaman OEIS yang , meskipun saya muncul secara independen dengan ekspresi reguler.

Uji di Ideone .

Dennis
sumber
Anda telah mengungguli OEIS, khususnya, Ton Hospel / Phil Carmody ...
Leaky Nun
Tidak bisa dibandingkan karena skrip OEIS tidak mengambil input dan mencetak seluruh urutan.
Dennis
1

JavaScript (ES6), 84

Basis indeks 0

n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

Kurang golf

n=>{
  r = d => (s+d).match(/(.*)\1$/)[0].length;
  c = '1';
  for(s = c; n--; s += c)
    c = r(1) > r(2) ? 2 : 1;
  return c;
}

Uji

F=
n=>eval("s='1';for(r=d=>(s+d).match(/(.*)\\1$/)[0].length;n--;s+=c)c=r(1)>r(2)?2:1")

for(n=0;n<20;n++)console.log(n,F(n))

edc65
sumber