Imagine un río recto y un camino que cruza el río n veces a través de puentes. El camino no gira sobre sí mismo y es infinitamente largo. Este camino se consideraría un meandro abierto. Un meandro abierto es una curva abierta, que no se cruza a sí misma y se extiende infinitamente en ambos extremos, que interseca una línea n veces.

Un meandro válido puede describirse completamente por el orden de los puntos de intersección que visita.

El número de patrones distintos de intersección con n intersecciones que puede ser un meandro es el enésimo número meandric . Por ejemplo, n = 4:

Los primeros números de esta secuencia son:

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

Esta es la secuencia OEIS A005316 .

Desafío

Escriba un programa / función que tome un entero positivo n como entrada e imprima el enésimo número meandric .

Especificaciones

• Se aplican las reglas estándar de E / S.
• Las lagunas estándar están prohibidas .
• Su solución puede estar indexada a 0 o indexada a 1 pero especifique cuál.
• Este desafío no se trata de encontrar el enfoque más corto en todos los idiomas, sino de encontrar el enfoque más corto en cada idioma .
• Su código se puntuará en bytes , generalmente en la codificación UTF-8, a menos que se especifique lo contrario.
• Las funciones integradas que calculan esta secuencia están permitidas, pero se recomienda incluir una solución que no se base en una función integrada.
• Se alientan las explicaciones, incluso para los idiomas "prácticos" .

Casos de prueba

Estos están indexados a 0. Tenga en cuenta que no necesita manejar números tan grandes si su idioma no puede por defecto.

Input      Output

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

En algunos formatos mejores:

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

Pruébalo en línea!

Ahora 1 indexado (anteriormente estaba 0 indexado pero 1 indexado salvó un byte debido a una peculiaridad afortunada con respecto al comportamiento de los meandros).

Explicación

Esto puede ser lo mismo que el enlace publicado por Jenny_mathy , pero no terminé leyendo el periódico, así que esta es solo la lógica detrás de mi método.

Usaré la siguiente ilustración provista en OEIS para visualizar los resultados.

Cada meandro válido puede describirse completamente por el orden de los puntos de intersección que visita. Esto puede observarse trivialmente en la imagen; el segmento de entrada siempre está en el mismo lado (de lo contrario, el número sería el doble). Podemos representar la tendencia de los segmentos de entrada y salida a sus respectivos infinitos simplemente agregando a cada orden un punto a cada lado, es decir, el orden (2, 1, 0)sería (-1, 2, 1, 0, 3).

Con esto en mente, la tarea es encontrar el número de órdenes, o permutaciones del rango hasta n, que no se cruzan entre sí. Las intersecciones son solo un problema entre pares de puntos para los cuales el segmento de conexión se encuentra en el mismo lado. Para dos pares de puntos consecutivos en una permutación cuyos segmentos comparten un lado, si se cruzan o no es equivalente a si uno, y solo uno, de los puntos de un par está entre los dos elementos del otro par. Como tal, podemos determinar si un pedido es válido si no hay pares con un punto contenido por otro par con un segmento en el mismo lado.

Finalmente, habiendo determinado la validez de cada permutaciones, la salida de la función se reduce al número de permutaciones que se consideran 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])

Pruébalo en línea!

Basado en una extensión de las ideas en Iwan Jensen, Enumeraciones de meandros planos , 1999 al caso de meandros abiertos. Esto pasa por n = 1, ..., 16 en aproximadamente 20 segundos en TIO.

APL (Dyalog Classic) , 127 115 bytes

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

Pruébalo en línea!