Ein "Reimschema" ist eine Folge von Buchstaben a
bis z
, so dass die ersten Vorkommen der Zeichen in aufsteigender Reihenfolge (ohne Lücken) beginnen a
. Zum Beispiel (mit markiertem erstem Vorkommen):
abccdbebdcfa
^^^ ^ ^ ^
Die Anzahl der Reimlängenschemata N
ergibt sich aus den Bell-Zahlen B(N)
. ( OEIS A000110 )
Die Herausforderung
Ihre Aufgabe ist es, eine Aufzählung dieser Reimschemata zu implementieren, dh eine bijektive Abbildung von ganzen Zahlen auf Reimschemata. Sie erhalten eine positive Ganzzahl N <= 26
sowie eine nicht negative Ganzzahl 0 <= i < B(N)
. Alternativ können Sie den Bereich verwenden 1 <= i <= B(N)
. Sie sollten ein Reimschema der Länge ausgeben N
, sodass jeder i
eine andere Zeichenfolge ergibt.
Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.
Sie können entweder Groß- oder Kleinbuchstaben verwenden (konsistent).
Ihr Code muss in der Lage sein, jede gültige Eingabe in angemessener Zeit zu verarbeiten (z. B. nicht länger als ein paar Stunden für den N = 26
schlimmsten Fall i
). Dies sollte Lösungen ermöglichen, die exponentiell mit skalieren N
(für kleine Basen), auch in langsamen Sprachen, aber Lösungen, die linear mit skalieren i
(dh B(N)
) , verbieten . Dies bedeutet insbesondere, dass Sie nicht alle gültigen Reimschemata mit einer Länge durchlaufen können, N
bis Sie die i
Schemata verworfen haben.
Es gelten die Standardregeln für Code-Golf .
Beispiele
Die genaue Zuordnung der i
zu Schemata (dh die Reihenfolge der Schemata für eine gegebene N
) liegt bei Ihnen. Angenommen, Sie haben die lexikografische Reihenfolge gewählt. Ihre Lösung sollte der folgenden Tabelle entsprechen ( -
wobei ungültige Eingaben angegeben werden):
N\i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 a - - - - - - - - - - - - - -
2 aa ab - - - - - - - - - - - - -
3 aaa aab aba abb abc - - - - - - - - - -
4 aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd
Hier ist ein kurzes CJam-Skript, das alle gültigen Reimschemata für eine bestimmte Länge generiert (aber versuchen Sie nicht mehr als 10, sonst warten Sie eine Weile).
Verwandte Herausforderungen
quelle
N
) ausgeben , vorausgesetzt, das ist nicht ganz einfach und ich war einfach zu dumm, um es zu finden.Antworten:
CJam,
6866 BytesProbieren Sie es online aus.
Dies ist mein erstes CJam-Programm. Es war ursprünglich ein Port meiner Perl-Lösung und anfangs mehr als 130 Byte lang. Weitere Golfvorschläge sind willkommen.
Wie bei meinem Perl-Programm besteht es aus zwei Teilen.
Um die Arrays von Teil 1 Add erstellt debuggen
]_`o~
zwischen Parts 1 & 2. Ist n5
, werden die Felder wie folgt aussehen:[[1 1 1 1 1 1] [1 2 3 4 5] [2 5 10 17] [5 15 37] [15 52]]
. Die 0-Indizes jedes Arrays werden nicht verwendet. Sie erleichtern lediglich die Berechnung von Offsets. Die Arrays werden folgendermaßen berechnet:Es behält eine Kopie des alten Arrays bei, während das nächste berechnet wird. Die Arrays werden in Teil 2 in umgekehrter Reihenfolge gelesen und verworfen.
quelle
Python 2, 153
Es verwendet alphabetische Reihenfolge und 0-basierte Indexierung.
l
Bezeichnen wir die Länge eines Suffixes der Buchstaben unda
die Anzahl der unterschiedlichen Buchstaben, die im vorhergehenden Teil verwendet wurden. Dann könnte eine Funktionp(l,a)
, die die Anzahl der Möglichkeiten zur Auswahl der verbleibenden Buchstaben berechnet, 40 Bytes umfassen:Dies ist jedoch für die Abfrage zu langsam, sodass stattdessen die erforderlichen Werte vorberechnet und im
u
Array gespeichert werden . Wenn in jeder Stufe der Berechnung der nächste Buchstabe dera
bereits verwendete ist, ist n = k * p (l - 1, a) + n ', wobei k der mit 0 indizierte Buchstabe des Alphabets ist und n' ist Der Wert vonn
für den nächsten Funktionsaufruf, der die Informationen zu den verbleibenden Buchstaben enthält. Wenn ein neuer Buchstabe verwendet wird, ist n = a * p (l - 1, a) + n ' .quelle
Haskell (GHC 7.10), 150 Bytes
Der Operator
n # i
berechnet dasi
th (null-indizierte) Reimlängenscheman
. Es wird in O (n²) (Big Integer) -Operationen ausgeführt und nutzt die faulen unendlichen Listen von Haskell für die automatische Speicherung. Probeläufe:(Wenn das Maximum von N 25 statt 26 wäre,
.fromEnum
könnte das entfernt werden, da B (25) in ein 64-Bit passtInt
.)quelle
Perl 257 + 1 (-p Flag) = 258Perl 182 + 10 (-pMbignum Flags) = 192
Vielen Dank an dev-nul für das Speichern vieler Bytes! Ich habe es jetzt neu geschrieben, basierend auf dem, was ich aus der CJam-Version gelernt habe.
Berechnet den Reim in aufsteigender alphabetischer Reihenfolge, 0 indiziert.
Zwei Teile: Teil 1 hat
128 bis90 Bytes und berechnet eine Matrix für Teil 2. Teil 2 hat129 bis92 Bytes und führt einige einfache Berechnungen durch, um jeden Buchstaben zu berechnen.Wenn ich die Matrix loswerden und durch zwei einfache Zahlen ersetzen könnte, könnte ich für jede Zahl einen einzelnen Pfad durch die Matrix berechnen und eine Menge Bytes sparen!Anscheinend funktioniert diese Idee nicht!Leider gibt es nicht die richtigen Reime für Wertei
über 9007199254740992 aus, aber es funktioniert wunderbar für niedrige Werte!Ich habe die Bignum-Bibliothek für 11 Byte hinzugefügt.Es wird von der Kommandozeile mit ausgeführtperl -pMbignum bell-rhyme.pl
.-pMbignum
= 10 Bytes. Es ist auch sehr schnell für jeden Eingabewert.quelle
Oracle SQL 11.2,
412284283 ByteLeider wird es nur bis zu einer Länge von 8 ausgeführt. Ein größerer Wert führt zu: ORA-01489: Ergebnis der Zeichenfolgenverkettung ist zu lang
Nicht golfen
Die a-Ansicht generiert die: i-Buchstaben in Spalte a und ihren Wert in b.
In der rekursiven Sicht v wird die zu erstellende Zeichenfolge als Parameter v, der Wert des letzten in c verwendeten Buchstabens und der Wert des größten in n verwendeten Buchstabens verwendet. Der Parameter n entspricht der Länge der Zeichenfolge ohne doppelten Buchstaben. Dafür ist der reguläre Ausdruck vorgesehen.
Ein Buchstabe ist gültig, wenn sein Wert <= der Wert des größten bereits verwendeten Buchstabens ist oder der nächste zu verwendende Buchstabe ist.
Irgendwie benötigt die Abfrage den Teil LENGTH (s) <: n, damit sie ausgeführt werden kann. In der Funktionsweise der Abfrage muss etwas fehlen.
Das Haupt-SELECT filtert die ungültigen Eingaben und die kürzeren Zeichenfolgen heraus, die erstellt werden, bevor die gewünschte Länge erreicht ist.
412-Byte-Version
Versuchen Sie nicht, die 412-Byte-Abfrage mit 26 auszuführen. Dadurch wird die Datenbank in den eingeschränkten Modus versetzt, zumindest in meiner xe-Version, die in einem Docker-Container auf einem MacBook ausgeführt wird. Ich könnte die Exadata bei der Arbeit anprobieren, aber leider muss ich immer noch arbeiten, um meinen Lebensunterhalt zu verdienen.
quelle
Mathematica, 136 Bytes
Der Vollständigkeit halber hier meine Golf-Referenzimplementierung. Im Gegensatz zu den vorhandenen Antworten läuft dies nicht in Polynomialzeit (es ist in
N
mit Basis 2 exponentiell ), sondern erfüllt die Zeitbeschränkung (der schlimmste Fall würde immer noch in weniger als einer halben Stunde laufen).Die Idee ist folgende:
Für jedes Reimschema können wir die Positionen identifizieren, an denen sich das maximale Zeichen bisher erhöht:
Wir können diese Markierungen als Binärzahl behandeln, wodurch es einfach ist, alle derartigen Strukturen zu durchlaufen. Wir müssen von 2 n-1 bis 2 n (oder umgekehrt) iterieren, woraus die exponentielle Zeitkomplexität resultiert.
i
, subtrahieren wir sie voni
. Ansonsten haben wir die Struktur des angeforderten Reimschemas gefunden.i
(oder was davon übrig bleibt) als eine gemischte Basiszahl dar, wobei die Gewichtung der Ziffern durch die Anzahl der zulässigen Zeichen in den verbleibenden Positionen bestimmt wird.Ich frage mich, ob dies eine kürzere Lösung in einigen der anderen eingereichten Sprachen ermöglichen würde, da keine Memoisierung oder Vorberechnung erforderlich ist.
quelle