Observe, o desafio copiado da pergunta feita em math.stackexchange .

Recentemente, adquiri bastante habilidade em soprar bolhas. No começo, eu soprava bolhas assim:

Mas então as coisas começaram a ficar estranhas:

Depois de um tempo, eu estava soprando algumas bolhas bem estranhas:

Depois de soprar centenas, talvez até milhares dessas bolhas, minha testa de repente se enrugou com a pergunta: Dadas n bolhas, quantas maneiras diferentes você pode organizá-las? Por exemplo, se n = 1, há apenas 1 arranjo. Se n = 2, existem 2 arranjos. Se n = 3, existem 4 arranjos. Se n = 4, existem 9 arranjos.

Aqui estão os 9 arranjos de 4 bolhas:

Depois de soprar todas essas bolhas maravilhosas, decidi compartilhar o prazer de contar seus arranjos com você. Então, aqui está sua tarefa:

Objetivo

Escreva um programa, função ou similar que conte o número de maneiras pelas quais você pode organizar nbolhas.

Entrada

n, o número de bolhas. n> 0

Saída

O número de maneiras pelas quais você pode organizar essas bolhas.

Critérios Vencedores

Seria muito legal se pudéssemos fazer uma bolha no seu código. Quanto menor o código, mais fácil será fazê-lo. Portanto, a pessoa que cria o código com o menor número de bytes vence o concurso.

Informação 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

Em inglês simples: para calcular a(n), calculamos d*a(d)*a(n-k)para cada divisor dde todo número inteiro positivo kmenor ou igual a n, somar tudo isso e dividir por n-1.

Para torná-lo mais rápido, execute o Python 3 (substituindo /por //na função acima) e memorize:

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

Se você fizer isso, ele calcula a(50) = 425976989835141038353instantaneamente.

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 resposta é um ótimo exemplo de como o Prolog pode enfrentar até os formatos de E / S mais simples. Ele funciona no verdadeiro estilo Prolog, descrevendo o problema, em vez do algoritmo para resolvê-lo: especifica o que conta como um arranjo legal de bolhas, pede ao Prolog para gerar todos esses arranjos e depois os conta. A geração ocupa 55 caracteres (as duas primeiras linhas do programa). A contagem e a E / S levam as outras 43 (a terceira linha e a nova linha que separa as duas partes). Aposto que esse não é um problema que o OP esperava que os idiomas lutassem com a E / S! (Nota: o destaque da sintaxe do Stack Exchange torna isso mais difícil de ler, não mais fácil, então eu o desativei).

Explicação

Vamos começar com uma versão em pseudocódigo de um programa semelhante que realmente não 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).

Deve ficar bem claro como bfunciona: estamos representando bolhas por meio de listas classificadas (que são uma implementação simples de multisets que faz com que multisets iguais sejam comparados com iguais) e um único balão []conta 1, com um balão maior contando igual à contagem total de bolhas dentro de mais 1. Para uma contagem de 4, este programa (se funcionasse) geraria as seguintes listas:

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

Este programa é inadequado como resposta por vários motivos, mas o mais premente é que o Prolog não possui um mappredicado (e escrever isso levaria muitos bytes). Então, em vez disso, escrevemos o programa mais ou menos assim:

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

O outro grande problema aqui é que ele entrará em um loop infinito quando executado, devido à maneira como a ordem de avaliação do Prolog funciona. No entanto, podemos resolver o loop infinito reorganizando o programa levemente:

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

Isso pode parecer bastante estranho - estamos adicionando as contagens antes de sabermos o que elas são - mas o GNU Prolog #=é capaz de lidar com esse tipo de aritmética não-causal, e porque é a primeira linha de b, e a HeadCounte TailCountdeve ser menor que Count(que é conhecido), serve como um método para limitar naturalmente quantas vezes o termo recursivo pode corresponder e, portanto, faz com que o programa seja sempre encerrado.

O próximo passo é jogar um pouco de golfe. Removendo o espaço em branco, usando nomes de variáveis ​​de um caractere, usando abreviações como :-for ife ,for and, usando em setofvez de listof(ele tem um nome mais curto e produz os mesmos resultados nesse caso) e usando em sort0(X,X)vez de is_sorted(X)(porque is_sortedna verdade não é uma função real, Eu inventei):

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

Isso é bastante curto, mas é possível fazer melhor. O principal insight é que [H|T]é realmente detalhado conforme as sintaxes da lista. Como os programadores do Lisp saberão, uma lista é basicamente feita apenas de células contras, que são basicamente apenas tuplas, e quase nenhuma parte deste programa está usando os recursos da lista. O Prolog possui várias sintaxes de tupla muito curtas (a minha favorita é A-Ba segunda preferida A/B, que estou usando aqui porque, nesse caso, produz saída de depuração mais fácil de ler); e também podemos escolher nosso próprio caractere único nilpara o final da lista, em vez de ficarmos presos ao caractere de dois caracteres [](eu escolhi x, mas basicamente tudo funciona). Então, em vez de [H|T], podemos usar T/He obter saída deb que se parece com isso (observe que a ordem de classificação nas tuplas é um pouco diferente da das listas, portanto, elas não estão na mesma ordem acima):

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

É um pouco mais difícil de ler do que as listas aninhadas acima, mas é possível; pule mentalmente xs e interprete /()como uma bolha (ou simplesmente /como uma bolha degenerada sem conteúdo, se não houver ()depois dela), e os elementos têm uma correspondência 1 para 1 (se desordenada) com a versão da lista mostrada acima .

Obviamente, essa representação da lista, apesar de muito mais curta, tem uma grande desvantagem; não está embutido no idioma; portanto, não podemos usar sort0para verificar se nossa lista está classificada. sort0de qualquer maneira, é bastante detalhado, portanto, fazê-lo manualmente não é uma perda enorme (de fato, fazê-lo manualmente na [H|T]representação da lista chega exatamente ao mesmo número de bytes). O principal insight aqui é que o programa, como escrito, verifica se a lista está classificada, se a cauda está classificada, se a cauda está classificada, e assim por diante; existem muitas verificações redundantes e podemos explorar isso. Em vez disso, apenas verificaremos se os dois primeiros elementos estão em ordem (o que garante que a lista seja classificada assim que a lista em si e todos os seus sufixos forem verificados).

O primeiro elemento é facilmente acessível; isso é apenas o chefe da lista H. O segundo elemento é bastante mais difícil de acessar e pode não existir. Felizmente, xé menor do que todas as tuplas que estamos considerando (por meio do operador de comparação generalizada do Prolog @>=), para que possamos considerar o "segundo elemento" de uma lista de singleton xe o programa funcionará bem. Quanto ao acesso real ao segundo elemento, o método tersest é adicionar um terceiro argumento (um argumento out) a b, que retorna xno caso base e Hno caso recursivo; isso significa que podemos pegar a cabeça da cauda como uma saída da segunda chamada recursiva para Be, é claro, a cabeça da cauda é o segundo elemento da lista. Então, bfica assim agora:

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

O caso base é bastante simples (lista vazia, retorna uma contagem de 0, o "primeiro elemento" da lista vazia é x). O caso recursivo começa da mesma forma como antes (apenas com a T/Hnotação em vez de [H|T], e Hcomo um extra para fora argumento); desconsideramos o argumento extra da chamada recursiva na cabeça, mas a armazenamos na Jchamada recursiva na cauda. Então, tudo o que precisamos fazer é garantir que Hseja maior ou igual a J(ou seja, "se a lista tiver pelo menos dois elementos, o primeiro for maior ou igual ao segundo) para garantir que a lista termine.

Infelizmente, setofisso se encaixa se tentarmos usar a definição anterior de cjuntamente com essa nova definição de b, porque ele trata parâmetros não utilizados de maneira mais ou menos da mesma maneira que um SQL GROUP BY, que não é exatamente o que queremos. É possível reconfigurá-lo para fazer o que queremos, mas essa reconfiguração custa caracteres. Em vez disso, usamos findall, que possui um comportamento padrão mais conveniente e tem apenas dois caracteres a mais, dando-nos esta definição de c:

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

E esse é o programa completo; gere padrões de bolhas de maneira concisa e depois gaste toda uma carga de bytes contando-os (precisamos de um tempo bastante longo findallpara converter o gerador em uma lista, depois de um nome infelizmente verbal lengthpara verificar o comprimento dessa lista, além do padrão para uma declaração de função).

Mathematica, 68 bytes

Aposto que isso pode ser derrotado (mesmo no Mathematica) com uma implementação a partir do zero, mas aqui está a versão interna:

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

ButcherTreeCounté indexado em 0, daí o [#+1], e retorna uma lista de todos os valores até seu argumento, portanto, o Last@. Mas, caso contrário, é apenas o componente interno para esta função. No entanto, requer o carregamento de um pacote, que é o que a primeira linha faz.