Bayangkan sebuah sungai lurus dan jalan yang melintasi sungai dan berkali-kali melalui jembatan. Jalan itu tidak berputar sendiri dan panjangnya tak terhingga. Jalan ini akan dianggap sebagai jalan berliku yang terbuka. Sebuah liku terbuka adalah kurva terbuka, yang tidak berpotongan itu sendiri dan meluas jauh di kedua ujungnya, yang memotong garis n kali.

Berliku-liku yang valid dapat dijelaskan sepenuhnya oleh urutan titik persimpangan yang dikunjungi.

Jumlah pola persimpangan yang berbeda dengan n persimpangan dapat berliku adalah angka ke - n berliku . Misalnya, n = 4:

Beberapa angka pertama dari urutan ini adalah:

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...

Ini adalah urutan OEIS A005316 .

Tantangan

Tulis program / fungsi yang mengambil bilangan bulat positif n sebagai input dan mencetak angka meandric ke - n .

Spesifikasi

• Aturan I / O standar berlaku.
• Celah standar yang dilarang .
• Solusi Anda dapat diindeks 0 atau diindeks 1 tetapi harap tentukan yang mana.
• Tantangan ini bukan tentang menemukan pendekatan terpendek dalam semua bahasa, melainkan tentang menemukan pendekatan terpendek dalam setiap bahasa .
• Kode Anda akan dinilai dalam byte , biasanya dalam pengkodean UTF-8, kecuali ditentukan lain.
• Fungsi built-in yang menghitung urutan ini diperbolehkan tetapi termasuk solusi yang tidak bergantung pada built-in dianjurkan.
• Penjelasan, bahkan untuk bahasa "praktis", dianjurkan .

Uji kasus

Ini adalah 0-diindeks. Perhatikan bahwa Anda tidak perlu menangani angka sebesar ini jika bahasa Anda tidak dapat secara default.

Input      Output

1          1
2          1
11         1828
14         30694
21         73424650
24         1649008456
31         5969806669034

Dalam beberapa format yang lebih baik:

1 2 11 14 21 24 31
1, 2, 11, 14, 21, 24, 31

Python 3 , 208 188 187 184 180 177 171 byte

lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

Cobalah online!

Sekarang 1-diindeks (sebelumnya 0-diindeks tetapi 1-pengindeksan disimpan byte karena peruntungan beruntung tentang perilaku berkelok-kelok).

Penjelasan

Ini mungkin sama dengan tautan yang diposting oleh Jenny_mathy , tapi akhirnya saya tidak membaca koran, jadi ini hanya logika di balik metode saya.

Saya akan menggunakan ilustrasi berikut yang disediakan pada OEIS untuk memvisualisasikan hasil.

Setiap berliku-liku yang valid dapat dijelaskan sepenuhnya oleh urutan titik persimpangan yang dikunjungi. Ini mungkin diamati secara sepele dalam gambar; segmen entri selalu di sisi yang sama (jika tidak angkanya akan berlipat ganda). Kita dapat mewakili kecenderungan dari kedua segmen masuk dan keluar ke infinitas masing-masing dengan hanya menambahkan ke setiap pesanan titik di kedua sisi - yaitu, urutannya (2, 1, 0)akan menjadi (-1, 2, 1, 0, 3).

Dengan mengingat hal ini, tugasnya adalah menemukan jumlah pesanan, atau permutasi dari rentang hingga n, yang tidak berpotongan dengan diri mereka sendiri. Persimpangan hanya merupakan masalah antara pasangan poin yang segmen penghubungnya berada di sisi yang sama. Untuk setiap dua pasang titik berurutan dalam permutasi yang segmennya berbagi sisi, apakah mereka berpotongan atau tidak setara dengan apakah satu, dan hanya satu, dari titik satu pasangan adalah antara dua elemen dari pasangan lainnya. Dengan demikian, kita dapat menentukan apakah pesanan valid dengan apakah tidak ada pasangan dengan satu titik yang terkandung oleh pasangan lain dengan segmen di sisi yang sama.

Akhirnya, setelah menentukan validitas setiap permutasi, output fungsi turun ke jumlah permutasi yang ditemukan valid.

Haskell , 199 byte

1!x=x
-1!(-1:x)=1:x
n!(i:x)=i:(n-i)!x
0#([],[])=1
0#_=0
n#(a,b)=sum$((n-1)#)<$>(-1:a,-1:b):[(a,-i:b)|i:a<-[a]]++[(-j:a,b)|j:b<-[b]]++[(j!a,i!b)|i:a<-[a],j:b<-[b],i+j>=0]
f n=n#([],[-1,1])+n#([1],[1])

Cobalah online!

Berdasarkan perpanjangan gagasan dalam Iwan Jensen, Enumerations of meanders pesawat , 1999 untuk kasus open meander. Ini berjalan melalui n = 1,…, 16 dalam waktu sekitar 20 detik pada TIO.

APL (Dyalog Classic) , 127 115 byte

⊃⊃⌽{↓⍉(⊃,/c),∘(+/)⌸(≢¨c←{1↓¨⍳¨⍨0,¨((×2↑¯1⌽⍵)/¯1 1⌽¨⊂⍵),(⊂∊#⍵#),(××/m,≠/m)/⊂1↓¯1↓(⊢-⍵×~)⍵∊m←2↑¯1⌽⍵}¨⊃⍵)/⊃⌽⍵}⍣⎕⌽1,⊂⍳2

Cobalah online!