In der Mengenlehre, die natürlichen Zahlen werden normalerweise als reine Mengen codiert , d. h. Mengen, die nur die leere Menge oder andere reine Mengen enthalten. Es sind jedoch nicht alle reinen Mengen natürliche Zahlen. Bei dieser Herausforderung geht es darum, zu entscheiden, ob eine gegebene reine Menge eine Kodierung einer natürlichen Zahl darstellt oder nicht.
Die Kodierung natürlicher Zahlen funktioniert folgendermaßen 1 :
- Null ist die leere Menge:
- Für eine Zahl :
Somit sind die Kodierungen der ersten paar natürlichen Zahlen
Die Aufgabe
- Bestimmen Sie anhand einer Zeichenfolge, die eine reine Menge darstellt, ob diese Menge eine natürliche Zahl gemäß der obigen Konstruktion codiert.
- Beachten Sie jedoch, dass die Elemente einer Menge nicht geordnet sind, sodass ist nicht die einzige gültige Darstellung von da z. B. dieselbe Menge darstellt.
- Sie können verwendet werden
[]
,()
oder<>
statt{}
. - Sie können davon ausgehen, dass die Sätze ohne das
,
Trennzeichen als angegeben sind. - Sie können davon ausgehen , es wird keine doppelten Elemente in der Eingabe, zB
{{},{}}
sind keine gültige Eingabe, und dass der Eingang wohlgeformt ist , zB keine{{},
,{,{}}
oder ähnliches.
Testfälle
Wahr:
{}
{{}}
{{},{{}}}
{{{}},{}}
{{},{{}},{{},{{}}}}
{{{},{{}}},{},{{}}}
{{{{}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
{{{{{}},{}},{{}},{}},{{}},{},{{},{{}}}}
{{},{{}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}},{{{}},{}},{{},{{}},{{},{{}}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}
Falsch:
{{{}}}
{{{{}}}}
{{{{}},{}}}
{{},{{}},{{{}}}}
{{{},{{}}},{{}}}
{{{{{}}},{}},{{}},{}}
{{},{{}},{{},{{}}},{{},{{}},{{{}}}}}
{{{{{}},{}},{{{}}},{}},{{}},{},{{},{{}}}}
{{{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}},{{{{{}},{}},{{}},{}},{{{}},{}},{{}}},{{{{}},{}},{{}},{}},{{{}},{}},{{}},{}}
Verwandte Themen: Natürliche Konstruktion (Geben Sie die eingestellte Kodierung einer bestimmten natürlichen Zahl aus.)
1 Siehe https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers
code-golf
decision-problem
set-theory
Laikoni
quelle
quelle
Antworten:
JavaScript (Node.js) ,
534844 ByteProbieren Sie es online! Testfälle meist schamlos aus @ Arnauld's Antwort gestohlen. Erläuterung: Wenn eine Menge eine natürliche Zahl darstellt, muss die natürliche Zahl der Größe der Menge entsprechen, und die Elemente müssen (sofern die Unterscheidbarkeit der Elemente gewährleistet ist) die Darstellungen der natürlichen Zahlen sein, die darunter liegen. und diese müssen daher kürzere Längen haben. Dies gilt natürlich trivialerweise für die leere Menge. Bearbeiten: 5 Bytes dank @Arnauld gespeichert. 4 Bytes gespart dank @Cowsquack.
quelle
!e[a.length-1]
sollte 3 Bytes speicherna[e.length]&&
für 5 Bytes!g=(A,a=eval(A))=>a.every(e=>a[e.length]&&g(e))
Würde das sicherlich funktionieren?Python 3 ,
695844 Bytes11 Bytes dank Erik dem Outgolfer.
14 Bytes dank Herrn Xcoder.
Probieren Sie es online!
quelle
Wolfram Language (Mathematica) ,
6059 BytesProbieren Sie es online!
Der Kern dieser Lösung ist die Funktion
Das konvertiert eine Liste des Formulars
{0,1,2,...,n-1}
in beliebiger Reihenfolge in die Ausgaben
(insbesondere{}
in0
) und alles andere in die reelle ZahlE
.Rufen Sie diese Funktion auf
f
. Bei einer Eingabe wie"{{{}},{}}"
:f
auf jeder Ebenef[{f[{f[{}]}], f[{}]}]
.f
Werte ergibt eine natürliche Zahl für eine Eingabe, die diese repräsentiert. Zum Beispielf[{f[{f[{}]}], f[{}]}]
=f[{f[{0}], 0}]
=f[{1, 0}]
=2
. Alles andere wird produzierenE
.E
.quelle
Brachylog (v2), 9 Bytes
Probieren Sie es online!
Wie bei Entscheidungsproblemen üblich , handelt es sich um ein vollständiges Programm. Eingabe von der Standardeingabe mit eckigen Klammern. Ausgabe auf Standardausgabe als
true.
versusfalse.
.Erläuterung
Obwohl ich oben sagte, dass dies ein vollständiges Programm ist, ist es tatsächlich interessanter als das; es ist sowohl ein volles Programm als auch eine Funktion. Bei Verwendung als vollständiges Programm wird gedruckt,
true.
ob der Satz eine natürliche Zahl ist oderfalse.
nicht. Wenn es als Funktion verwendet wird, "normalisiert" es eine natürliche Zahl (dh es normalisiert alle seine Elemente und sortiert sie nach Wert; dieses Programm verwendet Listen intern, keine Mengen) oder "löst eine Ausnahme aus" (tatsächlich ein Fehler) ist Prolog), wenn die Eingabe keine natürliche Zahl ist.Das Verhalten des vollständigen Programms ist leicht zu erklären: Es ist rein implizit in Brachylogs Behandlung vollständiger Programme enthalten, die keine E / A-Anweisungen enthalten. Das fragliche Verhalten lautet: "Führen Sie die Funktion aus, nehmen Sie ihre Eingabe von der Standardeingabe und bestätigen Sie, dass ihre Ausgabe mit der Beschreibung des ersten Befehlszeilenarguments übereinstimmt. Wenn die Zusicherung fehlschlägt oder das Programm eine Ausnahme auslöst, drucken Sie
false.
, andernfalls drucken Sietrue.
". . In diesem Fall fehlt das Befehlszeilenargument (dh "alles geht"), sodass das Ausnahme- / Nicht-Ausnahme-Verhalten der Funktion die Ausgabe ergibt.Wie für das Funktionsverhalten:
Eine natürliche Zahl besteht aus zwei Teilen: den Elementen der natürlichen Zahl, die mit der Zahl selbst in Verbindung gebracht werden. Alle seine Elemente sind also auch natürliche Zahlen. Wir können eine natürliche Zahl erkennen, indem wir a) überprüfen, ob alle ihre Elemente natürliche Zahlen sind, b) überprüfen, ob das größte Element der Menge mit der Menge ohne das größte Element identisch ist.
Wenn wir Listen anstelle von Mengen verwenden (also eckige Klammern), müssen wir sie in eine konsistente Reihenfolge bringen, damit Gleichheitsvergleiche funktionieren (in diesem Fall sortiert nach "Wert"). Die Standardsortierreihenfolge von Brachylog sortiert das Präfix einer Liste vor der Liste selbst, was praktisch ist, dass natürliche Zahlen nach numerischen Werten sortiert werden. Wir können also einfach alle unsere Zahlen rekursiv sortieren, um sie in eine einheitliche Reihenfolge zu bringen. Tatsächlich können wir über die Funktion, die wir rekursiv definieren, beide Ergebnisse gleichzeitig erzielen: rekursives Sortieren der Elemente der Zahl und Verifizieren, dass es sich um eine natürliche Zahl handelt.
Die Funktion besteht somit aus vier Hauptteilen.
↰ᵐ
ist der rekursive Aufruf, der sicherstellt, dass jedes Element eine natürliche Zahl ist, und jedes Element in eine normalisierte Form konvertiert.o
Das normalisiert die Zahl selbst (ihre Elemente sind bereits normalisiert, wir müssen sie also nur noch sortieren). Stellen Sie dann.t~k|
sicher, dass wir die gewünschte Struktur haben, indem Sie prüfen, ob das größte Element und die anderen Elemente identisch sind. Eine leere Liste (dh 0) hat kein letztes Element, daher wird ein Assertionsfehler mitt
; Das|Ė
behandelt diesen Fall, indem es einen expliziten Fallback für den Fall ausgibt, dass die Eingabeliste leer ist.quelle
K (ngn / k) ,
262427 BytesProbieren Sie es online!
Die Eingabe ist eine JSON-Zeichenfolge, die von
`j@
(ngn / k-spezifische Syntax) analysiert wird.{
}
ist eine rekursive Funktion mit Argumentx
. es gibt die natürliche Zahl zurück, die durch die Menge dargestellt wirdx
, oder null (0N
), wenn es keine Zahl darstellt .$[
;
;
]
ist wenn-dann-sonst. 0 ist falsch, andere ganze Zahlen sind wahr!#x
die ganzen Zahlen von 0 (einschließlich) bis zur Länge vonx
(ausschließlich)^
ohneo'x
Rekursion (o
) für jedes ('
) Element vonx
#
Länge^
ist Null?~
nicht@
wirkt als ein Dummy letztes Verb so dass~
und^
mit bestehend erhalten{
}
anstatt an sie angelegt zu werden ,quelle
Gelee , 10 Bytes
Probieren Sie es online!
quelle
Japt , 9 Bytes
Port von Neils JS-Lösung . Bitte stimmen Sie dem zu, wenn Sie dies tun.
Probieren Sie es aus oder führen Sie alle Testfälle aus
quelle
Rot , 81 Bytes
Probieren Sie es online!
Ähnlich wie bei Leaky Nun's Python 3
quelle
Gelee , 8 Bytes
Da die Eingabe eine Zeichenfolge sein muss, ist diese Übermittlung nur als vollständiges Programm gültig.
Probieren Sie es online! oder überprüfen Sie alle Testfälle
Wie es funktioniert
Dies ergibt eine kanonische Darstellung der Eingabe, die ausschließlich aus sortierten Arrays besteht.
quelle
Gelee , 7 Bytes
Dies ist eine Portierung von Leaky Nuns Python-Antwort .
Da die Eingabe eine Zeichenfolge sein muss, ist diese Übermittlung nur als vollständiges Programm gültig.
Probieren Sie es online! oder überprüfen Sie alle Testfälle
Wie es funktioniert
quelle
Wolfram Language (Mathematica) , 52 Byte
Probieren Sie es online!
quelle