Remarque, défi copié à partir de la question posée sur math.stackexchange .

Récemment, j'ai acquis une certaine habileté à souffler des bulles. Au début, je soufflais des bulles comme ceci:

Mais les choses ont commencé à devenir étranges:

Après un moment, je soufflais des bulles assez étranges:

Après avoir soufflé des centaines, voire des milliers de ces bulles, mon front s'est soudain plissé avec la question: Étant donné n bulles, combien de façons différentes pouvez-vous les organiser? Par exemple, si n = 1, il n'y a qu'un seul arrangement. Si n = 2, il y a 2 dispositions. Si n = 3, il y a 4 dispositions. Si n = 4, il y a 9 dispositions.

Voici les 9 arrangements de 4 bulles:

Après avoir soufflé toutes ces merveilleuses bulles, j'ai décidé que je devrais partager le plaisir de compter leurs arrangements avec vous. Voici donc votre tâche:

Objectif

Écrivez un programme, une fonction ou similaire qui compte le nombre de façons dont vous pouvez organiser les nbulles.

Contribution

n, le nombre de bulles. n> 0

Sortie

Le nombre de façons dont vous pouvez organiser ces bulles.

Critères gagnants

Ce serait vraiment cool si nous pouvions faire exploser une bulle autour de votre code. Plus votre code est petit, plus il sera facile de le faire. Ainsi, la personne qui crée le code avec le moins d'octets gagnera le concours.

Informations supplémentaires

OEIS

Python 2, 92 87 octets

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 clair: pour calculer, a(n)nous calculons d*a(d)*a(n-k)pour chaque diviseur dde chaque entier positif kinférieur ou égal à n, additionnons tout cela et divisons par n-1.

Pour le faire fonctionner plus rapidement, exécutez en Python 3 (en le remplaçant /par //dans la fonction ci-dessus) et mémorisez:

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

Si vous faites cela, il calcule a(50) = 425976989835141038353instantanément.

GNU Prolog, 98 octets

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

Cette réponse est un excellent exemple de la façon dont Prolog peut lutter avec même les formats d'E / S les plus simples. Il fonctionne dans le vrai style Prolog en décrivant le problème plutôt que l'algorithme pour le résoudre: il spécifie ce qui compte comme un arrangement de bulles légal, demande à Prolog de générer tous ces arrangements de bulles, puis les compte. La génération prend 55 caractères (les deux premières lignes du programme). Le comptage et les E / S prennent les 43 autres (la troisième ligne et la nouvelle ligne qui sépare les deux parties). Je parie que ce n'est pas un problème que l'OP s'attendait à ce que les langues aient du mal avec les E / S! (Remarque: la mise en évidence de la syntaxe de Stack Exchange rend la lecture plus difficile, pas plus facile, je l'ai donc désactivée).

Explication

Commençons par une version pseudocode d'un programme similaire qui ne fonctionne pas réellement:

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

Le fonctionnement devrait être assez clair b: nous représentons des bulles via des listes triées (qui sont une implémentation simple de multisets qui font que des multisets égaux se comparent égaux), et une seule bulle []a un nombre de 1, une plus grande bulle ayant un nombre égal au nombre total de bulles à l'intérieur plus 1. Pour un nombre de 4, ce programme générerait (s'il fonctionnait) les listes suivantes:

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

Ce programme ne convient pas comme réponse pour plusieurs raisons, mais le plus urgent est que Prolog n'a pas réellement de mapprédicat (et l'écrire prendrait trop d'octets). Donc, à la place, nous écrivons le programme plus comme ceci:

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

L'autre problème majeur ici est qu'il ira dans une boucle infinie lors de son exécution, en raison du fonctionnement de l'ordre d'évaluation de Prolog. Cependant, nous pouvons résoudre la boucle infinie en réorganisant légèrement le programme:

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

Cela peut sembler assez étrange - nous additionnons les nombres avant de savoir ce qu'ils sont - mais GNU Prolog #=est capable de gérer ce type d'arithmétique non causale, et parce que c'est la toute première ligne de b, et le HeadCountet TailCountdoivent tous deux être inférieurs à Count(ce qui est connu), il sert de méthode pour limiter naturellement le nombre de fois que le terme récursif peut correspondre, et entraîne ainsi la fin du programme.

La prochaine étape consiste à jouer un peu au golf. Supprimer les espaces, utiliser des noms de variable à un seul caractère, utiliser des abréviations comme :-pour ifet ,pour and, utiliser setofplutôt que listof(il a un nom plus court et produit les mêmes résultats dans ce cas), et utiliser sort0(X,X)plutôt que is_sorted(X)(car ce is_sortedn'est pas réellement une fonction réelle, Je l'ai fait):

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

C'est assez court, mais il est possible de faire mieux. L'idée clé est que [H|T]c'est vraiment verbeux au fur et à mesure que les syntaxes de liste vont. Comme les programmeurs de Lisp le savent, une liste est essentiellement composée uniquement de cellules contre, qui ne sont en fait que des tuples, et pratiquement aucune partie de ce programme n'utilise de listes intégrées. Prolog a plusieurs syntaxes de tuple très courtes (ma préférée est A-B, mais ma deuxième préférée est A/B, que j'utilise ici parce qu'elle produit une sortie de débogage plus facile à lire dans ce cas); et nous pouvons également choisir notre propre caractère unique nilpour la fin de la liste, plutôt que d'être coincé avec les deux caractères [](j'ai choisi x, mais fondamentalement tout fonctionne). Donc, au lieu de [H|T], nous pouvons utiliser T/Het obtenir la sortie deb qui ressemble à ceci (notez que l'ordre de tri sur les tuples est un peu différent de celui sur les listes, donc ceux-ci ne sont pas dans le même ordre que ci-dessus):

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

C'est plus difficile à lire que les listes imbriquées ci-dessus, mais c'est possible; sauter mentalement le xs et interpréter /()comme une bulle (ou tout simplement /comme une bulle dégénérée sans contenu, s'il n'y en a pas ()après), et les éléments ont une correspondance 1 à 1 (si désordonnée) avec la version de liste montrée ci-dessus .

Bien sûr, cette représentation de liste, bien qu'elle soit beaucoup plus courte, présente un inconvénient majeur; il n'est pas intégré à la langue, nous ne pouvons donc pas utiliser sort0pour vérifier si notre liste est triée. sort0est assez verbeux de toute façon, cependant, le faire à la main n'est pas une énorme perte (en fait, le faire à la main sur la [H|T]représentation de liste revient exactement au même nombre d'octets). L'aperçu clé ici est que le programme écrit vérifie si la liste est triée, si sa queue est triée, si sa queue est triée, etc. il y a beaucoup de contrôles redondants, et nous pouvons l'exploiter. Au lieu de cela, nous allons simplement vérifier que les deux premiers éléments sont en ordre (ce qui garantit que la liste finira par être triée une fois la liste elle-même et tous ses suffixes vérifiés).

Le premier élément est facilement accessible; c'est juste la tête de la liste H. Le deuxième élément est cependant plus difficile d'accès et peut ne pas exister. Heureusement, xc'est moins que tous les tuples que nous considérons (via l'opérateur de comparaison généralisée de Prolog @>=), donc nous pouvons considérer que le "deuxième élément" d'une liste singleton est xet le programme fonctionnera bien. Quant à l'accès réel au deuxième élément, la méthode la plus ters consiste à ajouter un troisième argument (un argument out) à b, qui renvoie xdans le cas de base et Hdans le cas récursif; cela signifie que nous pouvons saisir la tête de la queue en tant que sortie du deuxième appel récursif à B, et bien sûr la tête de la queue est le deuxième élément de la liste. Alors bressemble à ceci maintenant:

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

Le cas de base est assez simple (liste vide, retourne un compte de 0, le "premier élément" de la liste vide est x). Le cas récursif commence de la même manière que précédemment (juste avec la T/Hnotation plutôt que [H|T], et Hcomme argument supplémentaire); nous ignorons l'argument supplémentaire de l'appel récursif sur la tête, mais le stockons Jdans l'appel récursif sur la queue. Ensuite, tout ce que nous avons à faire est de nous assurer qu'il Hest supérieur ou égal à J(c'est- à -dire "si la liste a au moins deux éléments, le premier est supérieur ou égal au second) afin de s'assurer que la liste finit par être triée.

Malheureusement, setofjette un coup si nous essayons d'utiliser la définition précédente de cavec cette nouvelle définition de b, car il traite les paramètres de sortie inutilisés de la même manière qu'un SQL GROUP BY, ce qui n'est pas du tout ce que nous voulons. Il est possible de le reconfigurer pour faire ce que nous voulons, mais cette reconfiguration coûte des caractères. Au lieu de cela, nous utilisons findall, qui a un comportement par défaut plus pratique et ne fait que deux caractères de plus, ce qui nous donne cette définition de c:

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

Et c'est le programme complet; générer des schémas de bulles, puis passer une charge entière d'octets à les compter (nous avons besoin d'un temps assez long findallpour convertir le générateur en liste, puis d'un nom malheureusement verbeux lengthpour vérifier la longueur de cette liste, plus le passe-partout pour une déclaration de fonction).

Mathematica, 68 octets

Je parie que cela peut être battu (même dans Mathematica) avec une implémentation à partir de zéro, mais voici la version intégrée:

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

ButcherTreeCountest indexé 0, d'où le [#+1], et renvoie une liste de toutes les valeurs jusqu'à son argument, d'où le Last@. Mais sinon, c'est juste la fonction intégrée pour cette fonction. Cependant, cela nécessite de charger un package, ce que fait la première ligne.