Wyobraź sobie prostą rzekę i drogę, która biegnie przez rzekę n razy przez mosty. Droga nie zapętla się i jest nieskończenie długa. Ta droga byłaby uważana za otwarty zakręt. Otwarty meander jest otwartą krzywą, że nie przecinają się i rozciąga się bezstopniowo siebie na obu końcach, który przecina linię n razy.

Prawidłowego meandra można opisać całkowicie według kolejności punktów przecięcia, które odwiedza.

Liczba różnych wzorów przecięcia z n przecięciami, którymi może być meander, jest n-tą liczbą meandryczną . Na przykład n = 4:

Pierwsze kilka liczb tej sekwencji to:

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

Jest to sekwencja OEIS A005316 .

Wyzwanie

Napisz program / funkcję, która przyjmuje na wejściu dodatnią liczbę całkowitą n i wypisuje n-tą liczbę meandryczną .

Dane techniczne

• Obowiązują standardowe zasady we / wy .
• Standardowe luki są zabronione .
• Twoje rozwiązanie może mieć indeks 0 lub indeks 1, ale określ, które z nich.
• Wyzwanie to nie polega na znalezieniu najkrótszego podejścia we wszystkich językach, chodzi raczej o znalezienie najkrótszego podejścia w każdym języku .
• Twój kod będzie oceniany w bajtach , zwykle w kodowaniu UTF-8, chyba że określono inaczej.
• Wbudowane funkcje, które obliczają tę sekwencję są dozwolone, ale zalecane jest rozwiązanie, które nie opiera się na wbudowanej.
• Zachęca się do wyjaśnień, nawet w przypadku „praktycznych” języków .

Przypadki testowe

Są one indeksowane na 0. Pamiętaj, że nie musisz obsługiwać tak dużych cyfr, jeśli Twój język domyślnie nie może.

Input      Output

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

W kilku lepszych formatach:

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

Python 3 , 208 188 187 184 180 177 171 bajtów

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

Wypróbuj online!

Teraz indeksowane 1 (poprzednio indeksowane 0, ale indeksowanie 1 uratowało bajt z powodu szczęśliwego dziwactwa dotyczącego zachowania meandrów).

Wyjaśnienie

Może to być to samo, co link opublikowany przez Jenny_mathy , ale nie skończyłem czytać gazety, więc taka jest logika mojej metody.

Będę korzystał z poniższej ilustracji na OEIS w celu wizualizacji wyników.

Każdy ważny meander może być całkowicie opisany przez kolejność punktów przecięcia, które odwiedza. Można to trywialnie zaobserwować na obrazie; segment wejściowy jest zawsze po tej samej stronie (w przeciwnym razie liczba byłaby podwójna). Możemy przedstawić tendencję zarówno segmentów wejściowych, jak i wyjściowych do ich nieskończoności, po prostu dodając do każdego zamówienia punkt po każdej stronie - to znaczy, porządek (2, 1, 0)stałby (-1, 2, 1, 0, 3).

Mając to na uwadze, zadaniem jest znalezienie liczby zamówień lub permutacji zakresu do n, które się nie przecinają. Przecięcia są tylko problemem między parami punktów, dla których segment łączący leży po tej samej stronie. Dla dowolnych dwóch par kolejnych punktów w permutacji, których segmenty dzielą bok, to czy przecinają się, jest równoważne z tym, czy jeden i tylko jeden z punktów jednej pary znajduje się między dwoma elementami drugiej pary. W związku z tym możemy ustalić, czy zamówienie jest ważne na podstawie tego, czy nie ma par z jednym punktem zawartym przez inną parę z segmentem po tej samej stronie.

Wreszcie, po ustaleniu ważności każdej permutacji, wynik działania sprowadza się do liczby permutacji uznanych za ważne.

Haskell , 199 bajtów

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])

Wypróbuj online!

Na podstawie rozszerzenia pomysłów Iwana Jensena, Wyliczenia meandrów płaskich , 1999 na przypadek meandrów otwartych. W TIO przebiega przez n = 1,…, 16 w około 20 sekund.

APL (Dyalog Classic) , 127 115 bajtów

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

Wypróbuj online!