Tenga en cuenta que el desafío se copió de la pregunta realizada en math.stackexchange .

Recientemente, obtuve bastante habilidad para soplar burbujas. Al principio soplaría burbujas como esta:

Pero luego las cosas comenzaron a ponerse extrañas:

Después de un tiempo, estaba soplando algunas burbujas bastante extrañas:

Después de soplar cientos, tal vez incluso miles de tales burbujas, mi frente de repente se arrugó con la pregunta: Dadas n burbujas, ¿de cuántas maneras diferentes puedes organizarlas? Por ejemplo, si n = 1, solo hay 1 disposición. Si n = 2, hay 2 arreglos. Si n = 3, hay 4 arreglos. Si n = 4, hay 9 arreglos.

Aquí están los 9 arreglos de 4 burbujas:

Después de soplar todas estas burbujas maravillosas, decidí compartir el placer de contar sus arreglos contigo. Así que aquí está tu tarea:

Gol

Escriba un programa, función o similar que cuente la cantidad de formas en que puede organizar nburbujas.

Entrada

n, la cantidad de burbujas. n> 0

Salida

La cantidad de formas en que puede organizar estas burbujas.

Criterios ganadores

Sería genial si pudiéramos soplar una burbuja alrededor de su código. Cuanto más pequeño sea su código, más fácil será hacerlo. Entonces la persona que crea el código con la menor cantidad de bytes ganará el concurso.

Información extra

OEIS

Python 2, 92 87 bytes

a=lambda n:n<2or sum((k%d<1)*d*a(d)*a(n-k)for k in range(1,n)for d in range(1,1+k))/~-n

En inglés simple: para calcular a(n), calculamos d*a(d)*a(n-k)para cada divisor dde cada entero positivo kmenor o igual que n, sumamos todos estos y dividimos por n-1.

Para que funcione más rápido, ejecute en Python 3 (reemplazando /con //en la función anterior) y memorice:

import functools
a = functools.lru_cache(None)(a)

Si haces esto, se calcula al a(50) = 425976989835141038353instante.

GNU Prolog, 98 bytes

b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.
c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

Esta respuesta es un gran ejemplo de cómo Prolog puede luchar incluso con los formatos de E / S más simples. Funciona en el verdadero estilo de Prolog mediante la descripción del problema, en lugar del algoritmo para resolverlo: especifica qué cuenta como un arreglo legal de burbujas, le pide a Prolog que genere todos esos arreglos de burbujas y luego los cuenta. La generación toma 55 caracteres (las dos primeras líneas del programa). El conteo y la E / S toman las otras 43 (la tercera línea y la nueva línea que separa las dos partes). ¡Apuesto a que no es un problema que el OP espera que los idiomas tengan problemas con las E / S! (Nota: el resaltado de sintaxis de Stack Exchange hace que sea más difícil de leer, no más fácil, así que lo desactivé).

Explicación

Comencemos con una versión de pseudocódigo de un programa similar que en realidad no funciona:

b(Bubbles,Count) if map(b,Bubbles,BubbleCounts)
                and sum(BubbleCounts,InteriorCount)
                and Count is InteriorCount + 1
                and is_sorted(Bubbles).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Debe quedar bastante claro cómo bfunciona: estamos representando burbujas a través de listas ordenadas (que son una implementación simple de multisets que hace que los multisets iguales se comparen igual), y una sola burbuja []tiene un recuento de 1, y una burbuja más grande tiene un recuento igual al recuento total de las burbujas en el interior más 1. Para un recuento de 4, este programa generaría (si funcionara) las siguientes listas:

[[],[],[],[]]
[[],[],[[]]]
[[],[[],[]]]
[[],[[[]]]]
[[[]],[[]]]
[[[],[],[]]]
[[[],[[]]]]
[[[[],[]]]]
[[[[[]]]]]

Este programa no es adecuado como respuesta por varias razones, pero la más apremiante es que Prolog en realidad no tiene un mappredicado (y escribirlo tomaría demasiados bytes). Entonces, en cambio, escribimos el programa más así:

b([], 0).
b([Head|Tail],Count) if b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and Count is HeadCount + TailCount + 1
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

El otro problema importante aquí es que entrará en un bucle infinito cuando se ejecute, debido a la forma en que funciona el orden de evaluación de Prolog. Sin embargo, podemos resolver el bucle infinito reorganizando ligeramente el programa:

b([], 0).
b([Head|Tail],Count) if Count #= HeadCount + TailCount + 1
                    and b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Esto puede parecer bastante extraño: estamos sumando los recuentos antes de saber qué son, pero GNU Prolog's #=es capaz de manejar ese tipo de aritmética no causal, y porque es la primera línea de b, y el HeadCounty TailCountdebe ser menor que Count(que es conocido), sirve como un método para limitar naturalmente cuántas veces puede coincidir el término recursivo, y por lo tanto hace que el programa termine siempre.

El siguiente paso es jugar golf un poco más abajo. Eliminar espacios en blanco, usar nombres de variables de un solo carácter, usar abreviaturas como :-for ify ,for and, usar en setoflugar de listof(tiene un nombre más corto y produce los mismos resultados en este caso), y usar en sort0(X,X)lugar de is_sorted(X)(porque en is_sortedrealidad no es una función real, Lo inventé):

b([],0).
b([H|T],N):-N#=A+B+1,b(H,A),b(T,B),sort0([H|T],[H|T]).
c(X,Y):-setof(A,b(A,X),L),length(L,Y).

Esto es bastante corto, pero es posible hacerlo mejor. La idea clave es que [H|T]es realmente detallada a medida que avanzan las sintaxis de listas. Como sabrán los programadores de Lisp, una lista está compuesta básicamente por celdas de contras, que son básicamente solo tuplas, y casi ninguna parte de este programa está utilizando listas integradas. Prolog tiene varias sintaxis de tuplas muy cortas (mi favorita es A-B, pero mi segunda favorita es A/B, que estoy usando aquí porque produce una salida de depuración más fácil de leer en este caso); y también podemos elegir nuestro propio carácter único nilpara el final de la lista, en lugar de quedarnos atrapados con los dos caracteres [](elegí x, pero básicamente todo funciona). Entonces, en lugar de [H|T], podemos usar T/Hy obtener resultados deb que se ve así (tenga en cuenta que el orden de clasificación en las tuplas es un poco diferente al de las listas, por lo que no están en el mismo orden que el anterior):

x/x/x/x/x
x/x/x/(x/x)
x/(x/x)/(x/x)
x/x/(x/x/x)
x/(x/x/x/x)
x/x/(x/(x/x))
x/(x/x/(x/x))
x/(x/(x/x/x))
x/(x/(x/(x/x)))

Esto es bastante más difícil de leer que las listas anidadas anteriores, pero es posible; omita mentalmente el xs, e interprete /()como una burbuja (o simplemente /como una burbuja degenerada sin contenido, si no hay ()después), y los elementos tienen una correspondencia 1 a 1 (si está desordenada) con la versión de la lista que se muestra arriba .

Por supuesto, esta representación de la lista, a pesar de ser mucho más corta, tiene un gran inconveniente; no está integrado en el idioma, por lo que no podemos usar sort0para verificar si nuestra lista está ordenada. sort0Sin embargo, es bastante detallado, por lo que hacerlo a mano no es una gran pérdida (de hecho, hacerlo a mano en la [H|T]representación de la lista tiene exactamente el mismo número de bytes). La idea clave aquí es que el programa, como escrito, verifica si la lista está ordenada, si su cola está ordenada, si su cola está ordenada, y así sucesivamente; Hay muchas comprobaciones redundantes, y podemos explotarlas. En su lugar, solo verificaremos para asegurarnos de que los dos primeros elementos estén en orden (lo que garantiza que la lista terminará ordenada una vez que la lista misma y todos sus sufijos estén verificados).

El primer elemento es fácilmente accesible; ese es solo el encabezado de la lista H. Sin embargo, el segundo elemento es bastante difícil de acceder y puede no existir. Afortunadamente, xes menor que todas las tuplas que estamos considerando (a través del operador de comparación generalizada de Prolog @>=), por lo que podemos considerar que el "segundo elemento" de una lista singleton es xy el programa funcionará bien. En cuanto al acceso real al segundo elemento, el método de prueba es agregar un tercer argumento (un argumento de salida) a b, que retorna xen el caso base y Hen el caso recursivo; Esto significa que podemos tomar la cabeza de la cola como una salida de la segunda llamada recursiva By, por supuesto, la cabeza de la cola es el segundo elemento de la lista. Así se bve así ahora:

b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.

El caso base es bastante simple (lista vacía, devuelve un recuento de 0, el "primer elemento" de la lista vacía es x). El caso recursivo comienza de la misma manera que antes (solo con la T/Hnotación en lugar de [H|T], y Hcomo un argumento extra); ignoramos el argumento adicional de la llamada recursiva en la cabeza, pero lo almacenamos Jen la llamada recursiva en la cola. Entonces todo lo que tenemos que hacer es asegurarnos de que Hsea ​​mayor o igual que J(es decir, "si la lista tiene al menos dos elementos, el primero es mayor o igual que el segundo) para garantizar que la lista termine ordenada.

Desafortunadamente, setofarroja un ajuste si tratamos de usar la definición anterior de cjunto con esta nueva definición de b, porque trata los parámetros no utilizados de manera más o menos igual que un SQL GROUP BY, que no es lo que queremos. Es posible reconfigurarlo para hacer lo que queremos, pero esa reconfiguración cuesta personajes. En su lugar, utilizamos findall, que tiene un comportamiento predeterminado más conveniente y tiene solo dos caracteres más, lo que nos da esta definición de c:

c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

Y ese es el programa completo; generosamente genere patrones de burbujas, luego gaste una carga completa de bytes contándolos (necesitamos un tiempo bastante largo findallpara convertir el generador en una lista, luego desafortunadamente un nombre detallado lengthpara verificar la longitud de esa lista, más la plantilla para una declaración de función).

Mathematica, 68 bytes

Apuesto a que esto se puede superar (incluso en Mathematica) con una implementación desde cero, pero aquí está la versión incorporada:

<<NumericalDifferentialEquationAnalysis`
Last@ButcherTreeCount[#+1]&

ButcherTreeCountestá indexado en 0, de ahí el [#+1], y devuelve una lista de todos los valores hasta su argumento, de ahí el Last@. Pero, de lo contrario, es solo la función incorporada para esta función. Sin embargo, requiere cargar un paquete, que es lo que hace la primera línea.