Imaginez une rivière droite et une route qui traverse la rivière n fois par des ponts. La route ne boucle pas sur elle-même et est infiniment longue. Cette route serait considérée comme un méandre ouvert. Un méandre ouvert est une courbe ouverte, qui ne se coupe pas et s'étend à l'infini aux deux extrémités, qui coupe une ligne n fois.

Un méandre valide peut être entièrement décrit par l'ordre des points d'intersection qu'il visite.

Le nombre de motifs distincts d'intersection avec n intersections qu'un méandre peut être est le nième nombre moyen . Par exemple, n = 4:

Les premiers nombres de cette séquence sont:

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

Il s'agit de la séquence OEIS A005316 .

Défi

Écrire un programme / fonction qui prend un entier positif n en entrée et imprime le nième nombre moyen .

Caractéristiques

• Les règles d'E / S standard s'appliquent.
• Les failles standard sont interdites .
• Votre solution peut être indexée 0 ou indexée 1 mais veuillez préciser laquelle.
• Ce défi ne consiste pas à trouver l'approche la plus courte dans toutes les langues, mais plutôt à trouver l' approche la plus courte dans chaque langue .
• Votre code sera noté en octets , généralement dans le codage UTF-8, sauf indication contraire.
• Les fonctions intégrées qui calculent cette séquence sont autorisées mais l'inclusion d'une solution qui ne repose pas sur une intégrée est encouragée.
• Des explications, même pour les langues "pratiques", sont encouragées .

Cas de test

Ceux-ci sont indexés 0. Notez que vous n'avez pas besoin de gérer des nombres aussi gros si votre langue ne le peut pas par défaut.

Input      Output

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

Dans quelques meilleurs formats:

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

Python 3 , 208 188 187 187 184 180 177 171 octets

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

Essayez-le en ligne!

Maintenant indexé 1 (était auparavant indexé 0 mais l'indexation 1 a sauvé un octet en raison d'une bizarrerie chanceuse concernant le comportement des méandres).

Explication

Cela peut être le même que le lien publié par Jenny_mathy , mais je n'ai pas fini par lire le document, c'est donc juste la logique derrière ma méthode.

J'utiliserai l'illustration suivante fournie sur OEIS afin de visualiser les résultats.

Chaque méandre valide peut être décrit entièrement par l'ordre des points d'intersection qu'il visite. Cela peut être trivialement observé dans l'image; le segment d'entrée est toujours du même côté (sinon le nombre serait double). Nous pouvons représenter la tendance des segments d'entrée et de sortie à leur infinité respective en ajoutant simplement à chaque ordre un point de chaque côté - c'est-à-dire que l'ordre (2, 1, 0)deviendrait(-1, 2, 1, 0, 3) .

Dans cette optique, la tâche consiste à trouver le nombre d'ordres, ou permutations de la plage jusqu'à n, qui ne se croisent pas. Les intersections ne sont un problème qu'entre paires de points pour lesquels le segment de connexion se trouve du même côté. Pour deux paires de points consécutifs quelconques dans une permutation dont les segments partagent un côté, qu'ils se coupent ou non, cela équivaut à savoir si l'un, et un seul, des points d'une paire se trouve entre les deux éléments de l'autre paire. En tant que tel, nous pouvons déterminer si un ordre est valide par s'il n'y a pas de paires avec un point contenu par une autre paire avec un segment du même côté.

Enfin, après avoir déterminé la validité de chaque permutations, la sortie de la fonction se résume au nombre de permutations jugées valides.

Haskell , 199 octets

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

Essayez-le en ligne!

Basé sur une extension des idées dans Iwan Jensen, Enumerations of plane sinders , 1999 au cas des méandres ouverts. Cela passe par n = 1,…, 16 en environ 20 secondes sur TIO.

APL (Dyalog Classic) , 127 115 octets

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

Essayez-le en ligne!