Imagine um rio reto e uma estrada que atravessa o rio n vezes por pontes. A estrada não se curva e é infinitamente longa. Essa estrada seria considerada um meandro aberto. Um meandro aberto é uma curva aberta, que não se cruza e se estende infinitamente nas duas extremidades, que cruza uma linha n vezes.

Um meandro válido pode ser descrito inteiramente pela ordem dos pontos de interseção que ele visita.

O número de padrões distintos de interseção com n interseções que um meandro pode ser é o enésimo número meandrico . Por exemplo, n = 4:

Os primeiros números desta sequência são:

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

Esta é a sequência OEIS A005316 .

Desafio

Escreva um programa / função que use um número inteiro positivo n como entrada e imprima o enésimo número meandrico .

Especificações

• Aplicam- se as regras de E / S padrão .
• As brechas padrão são proibidas .
• Sua solução pode ser indexada 0 ou 1, mas especifique qual.
• Esse desafio não é encontrar a abordagem mais curta em todos os idiomas, mas sim encontrar a abordagem mais curta em cada idioma .
• Seu código será pontuado em bytes , geralmente na codificação UTF-8, a menos que especificado de outra forma.
• Funções internas que computam essa sequência são permitidas, mas é recomendável incluir uma solução que não dependa de uma interna.
• Explicações, mesmo para idiomas "práticos", são incentivadas .

Casos de teste

Estes são 0 indexados. Observe que você não precisa manipular números desse tamanho se o seu idioma não puder por padrão.

Input      Output

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

Em alguns formatos melhores:

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

Python 3 , 208 188 187 184 180 177 171 bytes

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

Experimente online!

Agora indexado a 1 (anteriormente era indexado a 0, mas a indexação 1 salvou um byte devido a uma peculiaridade de sorte em relação ao comportamento dos meandros).

Explicação

Pode ser o mesmo que o link postado por Jenny_mathy , mas eu não acabei lendo o artigo, então essa é apenas a lógica por trás do meu método.

Usarei a ilustração a seguir fornecida no OEIS para visualizar os resultados.

Cada meandro válido pode ser descrito inteiramente pela ordem dos pontos de interseção que visita. Isso pode ser observado trivialmente na imagem; o segmento de entrada está sempre do mesmo lado (caso contrário, o número seria duplo). Podemos representar a tendência dos segmentos de entrada e saída para seus respectivos infinitos, simplesmente adicionando a cada ordem um ponto de cada lado - ou seja, a ordem (2, 1, 0)se tornaria (-1, 2, 1, 0, 3).

Com isso em mente, a tarefa é encontrar o número de ordens, ou permutações do intervalo até n, que não se cruzam entre si. As interseções são apenas uma questão entre pares de pontos para os quais o segmento de conexão fica do mesmo lado. Para quaisquer dois pares de pontos consecutivos em uma permutação cujos segmentos compartilham um lado, se eles se cruzam ou não, é equivalente a se um e apenas um dos pontos de um par estão entre os dois elementos do outro par. Assim, podemos determinar se uma ordem é válida se não há pares com um ponto contido em outro par com um segmento do mesmo lado.

Finalmente, tendo determinado a validade de cada permutação, a saída da função se resume ao número de permutações consideradas válidas.

Haskell , 199 bytes

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

Experimente online!

Baseado em uma extensão das idéias de Iwan Jensen, Enumerations of plane meanders , 1999, no caso de meandros abertos. Isso passa por n = 1,…, 16 em cerca de 20 segundos no TIO.

APL (Dyalog Classic) , 127 115 bytes

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

Experimente online!