Hinweis: Herausforderung kopiert von der Frage, die bei math.stackexchange gestellt wurde .

Vor kurzem habe ich einige Fähigkeiten im Blasen von Blasen erlangt. Zuerst würde ich Blasen wie folgt blasen:

Aber dann wurde es merkwürdig:

Nach einer Weile blies ich einige ziemlich seltsame Blasen:

Nachdem ich Hunderte, vielleicht sogar Tausende solcher Blasen geblasen hatte, runzelte meine Stirn plötzlich die Frage: Auf wie viele verschiedene Arten können Sie diese bei n Blasen anordnen? Wenn beispielsweise n = 1 ist, gibt es nur eine Anordnung. Wenn n = 2 ist, gibt es 2 Anordnungen. Wenn n = 3 ist, gibt es 4 Anordnungen. Wenn n = 4 ist, gibt es 9 Anordnungen.

Hier sind die 9 Arrangements von 4 Blasen:

Nachdem ich all diese wunderbaren Blasen gesprengt hatte, entschloss ich mich, die Freude, ihre Arrangements zu zählen, mit Ihnen zu teilen. Also hier ist deine Aufgabe:

Tor

Schreiben Sie ein Programm, eine Funktion oder Ähnliches, das die Anzahl der Arten zählt, wie Sie nBlasen anordnen können .

Eingang

n, die Anzahl der Blasen. n> 0

Ausgabe

Die Anzahl der Möglichkeiten, wie Sie diese Blasen anordnen können.

Gewinnkriterien

Es wäre wirklich cool, wenn wir eine Blase um Ihren Code werfen könnten. Je kleiner Sie Ihren Code machen, desto einfacher wird es sein, dies zu tun. Die Person, die den Code mit der geringsten Anzahl von Bytes erstellt, gewinnt den Wettbewerb.

Zusatzinformation

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

Im Klartext: Zur Berechnung berechnen a(n)wir d*a(d)*a(n-k)für jeden Divisor djeder positiven ganzen Zahl, die kkleiner oder gleich ist n, addieren diese und dividieren durch n-1.

Um es schneller laufen zu lassen, führen Sie Python 3 aus (ersetzen Sie es /durch //in der obigen Funktion) und merken Sie sich:

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

Wenn Sie dies tun, wird es a(50) = 425976989835141038353sofort berechnet .

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

Diese Antwort ist ein großartiges Beispiel dafür, wie Prolog selbst mit den einfachsten E / A-Formaten zu kämpfen hat. Es funktioniert im wahren Prolog-Stil, indem es das Problem beschreibt und nicht den Algorithmus, mit dem es gelöst werden soll: Es gibt an, was als legale Blasenanordnung gilt, und fordert Prolog auf, alle diese Blasenanordnungen zu generieren und sie dann zu zählen. Die Generierung dauert 55 Zeichen (die ersten beiden Zeilen des Programms). Das Zählen und E / A übernimmt die anderen 43 (die dritte Zeile und die neue Zeile, die die beiden Teile trennt). Ich wette, das ist kein Problem, das das OP Sprachen dazu bringen sollte, mit I / O zu kämpfen! (Hinweis: Die Syntaxhervorhebung von Stack Exchange macht das Lesen schwieriger und nicht einfacher. Deshalb habe ich sie deaktiviert.)

Erläuterung

Beginnen wir mit einer Pseudocode-Version eines ähnlichen Programms, das eigentlich nicht funktioniert:

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

Es sollte ziemlich klar sein, wie dies bfunktioniert: Wir repräsentieren Blasen über sortierte Listen (eine einfache Implementierung von Multisets, die bewirken, dass gleiche Multisets gleich sind), und eine einzelne Blase []hat eine Anzahl von 1, während eine größere Blase eine Anzahl hat Dies entspricht der Gesamtanzahl der Blasen in plus 1. Bei einer Anzahl von 4 würde dieses Programm (sofern es funktioniert) die folgenden Listen generieren:

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

Dieses Programm ist aus mehreren Gründen als Antwort ungeeignet, aber das Dringlichste ist, dass Prolog eigentlich kein mapPrädikat hat (und das Schreiben würde zu viele Bytes erfordern ). Also schreiben wir das Programm stattdessen eher so:

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

Das andere große Problem ist, dass es beim Ausführen in eine Endlosschleife gerät, da die Auswertungsreihenfolge von Prolog so funktioniert. Wir können die Endlosschleife jedoch lösen, indem wir das Programm leicht neu anordnen:

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

Dies könnte ziemlich seltsam aussehen - wir Addition der Zählungen , bevor wir wissen , was sie sind - aber GNU Prolog ist in #=der Lage, diese Art von nichtkausalen Arithmetik Handhabung und weil es die erste Zeile ist b, und das HeadCountund TailCountmüssen beide weniger als Count(was bekannt ist), dient es als Methode, um auf natürliche Weise zu begrenzen, wie oft der rekursive Term übereinstimmen kann, und bewirkt somit, dass das Programm immer beendet wird.

Der nächste Schritt ist das Golfspielen. Entfernen von Leerzeichen, Verwenden von Variablennamen mit einem Zeichen, Verwenden von Abkürzungen wie :-for ifund ,for and, Verwenden von setofanstatt listof(es hat einen kürzeren Namen und führt in diesem Fall zu den gleichen Ergebnissen) und Verwenden von sort0(X,X)anstatt is_sorted(X)(weil is_sortedes eigentlich keine echte Funktion ist) Ich habe es erfunden):

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

Das ist ziemlich kurz, aber es ist möglich, es besser zu machen. Die wichtigste Erkenntnis ist, dass die [H|T]Listensyntax sehr ausführlich ist. Wie Lisp-Programmierer wissen, besteht eine Liste im Grunde genommen nur aus Cons-Zellen, die im Grunde genommen nur Tupel sind, und kaum ein Teil dieses Programms verwendet List-Builtins. Prolog hat mehrere sehr kurze Tupelsyntaxen (mein Favorit ist A-B, aber mein zweiter Favorit ist A/B, den ich hier verwende, weil es in diesem Fall eine einfacher zu lesende Debug-Ausgabe erzeugt). und wir können auch unser eigenes einzelnes Zeichen nilfür das Ende der Liste wählen , anstatt an dem zwei Zeichen festzuhalten [](ich habe gewählt x, aber im Grunde funktioniert alles). Stattdessen [H|T]können wir also verwenden T/Hund die Ausgabe von erhaltenb das sieht so aus (beachte, dass die Sortierreihenfolge bei Tupeln ein wenig anders ist als bei Listen, daher sind diese nicht in der gleichen Reihenfolge wie oben):

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

Dies ist etwas schwerer zu lesen als die obigen verschachtelten Listen, aber es ist möglich. Überspringen Sie in Gedanken das xs und interpretieren Sie es /()als eine Blase (oder einfach /als eine entartete Blase ohne Inhalt, wenn es kein ()danach gibt), und die Elemente haben eine 1-zu-1-Entsprechung (wenn sie ungeordnet sind) mit der oben gezeigten Listenversion .

Natürlich hat diese Listendarstellung, obwohl sie viel kürzer ist, einen großen Nachteil; Es ist nicht in die Sprache integriert, daher können wir nicht sort0überprüfen, ob unsere Liste sortiert ist. sort0ist ohnehin ziemlich ausführlich, so dass es kein großer Verlust ist, es von Hand zu machen (in der Tat [H|T]kommt es auf genau die gleiche Anzahl von Bytes , wenn man es von Hand in der Listendarstellung macht). Die wichtigste Erkenntnis hier ist, dass das Programm in schriftlicher Form prüft, ob die Liste sortiert ist, ob ihr Ende sortiert ist, ob ihr Ende sortiert ist und so weiter. Es gibt viele redundante Überprüfungen, und das können wir ausnutzen. Stattdessen überprüfen wir nur, ob die ersten beiden Elemente in Ordnung sind (wodurch sichergestellt wird, dass die Liste sortiert wird, sobald die Liste selbst und alle ihre Suffixe überprüft wurden).

Das erste Element ist leicht zugänglich; Das ist nur der Kopf der Liste H. Das zweite Element ist jedoch schwieriger zu erreichen und existiert möglicherweise nicht. Zum Glück sind xes weniger als alle Tupel, die wir in Betracht ziehen (über den allgemeinen Vergleichsoperator von Prolog @>=), so dass wir das "zweite Element" einer Singleton-Liste für gut halten können xund das Programm gut funktionieren wird. Um auf das zweite Element tatsächlich zuzugreifen, besteht die schärfste Methode darin, ein drittes Argument (ein out-Argument) hinzuzufügen b, das xim Basisfall und Him rekursiven Fall zurückgegeben wird. Dies bedeutet, dass wir den Kopf des Endes als Ausgabe des zweiten rekursiven Aufrufs von erfassen können B, und natürlich ist der Kopf des Endes das zweite Element der Liste. So bsieht das jetzt aus:

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

Der Basisfall ist einfach genug (leere Liste, Rückgabe einer Anzahl von 0, das "erste Element" der leeren Liste ist x). Der rekursive Fall beginnt auf die gleiche Weise wie zuvor (nur mit der T/HNotation anstatt [H|T]und Hals extra-out-Argument); Wir ignorieren das zusätzliche Argument aus dem rekursiven Aufruf auf dem Kopf, speichern es aber Jin dem rekursiven Aufruf auf dem Schwanz. Dann müssen wir nur sicherstellen, dass die Liste Hgrößer oder gleich ist J(dh "wenn die Liste mindestens zwei Elemente enthält, ist das erste größer oder gleich dem zweiten), um sicherzustellen, dass die Liste sortiert endet.

Leider setofergibt sich ein Fit, wenn wir versuchen, die vorherige Definition von czusammen mit dieser neuen Definition von zu verwenden b, da unbenutzte Parameter mehr oder weniger wie bei SQL behandelt werden GROUP BY, was absolut nicht das ist, was wir wollen. Es ist möglich, es neu zu konfigurieren, um das zu tun, was wir wollen, aber diese Neukonfiguration kostet Zeichen. Stattdessen verwenden wir findall, was ein bequemeres Standardverhalten hat und nur zwei Zeichen länger ist, und geben uns diese Definition von c:

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

Und das ist das komplette Programm; Erzeugen Sie kurzzeitig Blasenmuster und geben Sie dann eine ganze Menge Bytes zum Zählen aus (wir benötigen eine ziemlich lange Zeit findall, um den Generator in eine Liste umzuwandeln, dann eine unglücklicherweise ausführlich benannte length, um die Länge dieser Liste zu überprüfen, sowie das Boilerplate für eine Funktionsdeklaration).

Mathematica, 68 Bytes

Ich wette, dies kann (sogar in Mathematica) mit einer von Grund auf neuen Implementierung besiegt werden, aber hier ist die integrierte Version:

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

ButcherTreeCountist 0-indiziert, daher das [#+1], und gibt eine Liste aller Werte bis zu seinem Argument zurück, daher das Last@. Ansonsten ist es nur das eingebaute Element für diese Funktion. Es muss jedoch ein Paket geladen werden, wie in der ersten Zeile beschrieben.