Stellt dieses Set eine natürliche Zahl dar?

26

In der Mengenlehre, die natürlichen Zahlen N={0,1,2,3,...} 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:Set(0)={}
  • Für eine Zahl :n>0Set(n)=Set(n1){Set(n1)}

Somit sind die Kodierungen der ersten paar natürlichen Zahlen

  • 0{}
  • 1{0}{{}}
  • 2{0,1}{{},{{}}}
  • 3{0,1,2}{{},{{}},{{},{{}}}}
  • 4{0,1,2,3}{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}

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.{{},{{}},{{},{{}}}}3{{{}},{},{{{}},{}}}
  • 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

Laikoni
quelle
13
Die Testfälle sehen aus wie ein Programm in einem (noch) nicht implementierten Esolang :)
Galen Ivanov
2
Kann die Eingabe eine Datenstruktur (verschachtelte Listen) anstelle einer Zeichenfolge sein?
ngn
3
Ich dachte, es wäre für einen Moment Brain-Flak .
Belhenix
5
@ngn Nein, die Eingabe muss eine Zeichenfolge sein.
Laikoni
4
@KirillL. Technisch waren diese Antworten anfangs nicht gültig, da die Herausforderung immer lautete: "Angesichts einer Zeichenfolge, die eine reine Menge darstellt", obwohl ich den Punkt sehe, dass das Zulassen verschachtelter Datenstrukturen interessante Golfmöglichkeiten bietet. Es fällt mir jedoch schwer zu entscheiden, wo die Grenze zwischen einer zulässigen Datenstruktur und einem zu nachgiebigen Eingabeformat gezogen werden soll. Aus Gründen der Einfachheit und Eindeutigkeit habe ich mich daher entschlossen, Eingaben auf Zeichenfolgen zu beschränken .
Laikoni

Antworten:

11

JavaScript (Node.js) , 53 48 44 Byte

f=a=>(a=eval(a)).every(e=>a[e.length]&&f(e))

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

Neil
quelle
!e[a.length-1]sollte 3 Bytes speichern
Arnauld
1
@Arnauld Oder noch besser, a[e.length]&&für 5 Bytes!
Neil
@JoKing Ugh, ich habe gerade Arnauld kopiert ... String-Eingabe kostet 14 Bytes :-(
Neil
g=(A,a=eval(A))=>a.every(e=>a[e.length]&&g(e))Würde das sicherlich funktionieren?
Kritixi Lithos
@Cowsquack Ah, schön, das spart eigentlich 4 Bytes, danke!
Neil
6

Python 3 , 69 58 44 Bytes

11 Bytes dank Erik dem Outgolfer.

14 Bytes dank Herrn Xcoder.

f=lambda s:all(len(e)<len(s)*f(e)for e in s)

Probieren Sie es online!

Undichte Nonne
quelle
@ Mr.Xcoder fertig
Undichte Nonne
Oh wow, schöne Verbesserung!
Mr. Xcoder
@ Mr.Xcoder und dann merke ich jetzt, dass es das gleiche ist wie Neils Antwort ... so technisch besiegte Neil mich
Leaky Nun
5

Wolfram Language (Mathematica) , 60 59 Bytes

E!=(If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&//@ToExpression@#)&

Probieren Sie es online!

Der Kern dieser Lösung ist die Funktion

If[Sort@#===Range[t=Tr[1^#]]-1,t,E]&

Das konvertiert eine Liste des Formulars {0,1,2,...,n-1}in beliebiger Reihenfolge in die Ausgabe n(insbesondere {}in 0) und alles andere in die reelle Zahl E.

Rufen Sie diese Funktion auf f. Bei einer Eingabe wie "{{{}},{}}":

  1. Konvertieren Sie den String in einen Mathematica-Ausdruck.
  2. Bewerben Sie sich fauf jeder Ebene f[{f[{f[{}]}], f[{}]}].
  3. Die Auswertung aller fWerte ergibt eine natürliche Zahl für eine Eingabe, die diese repräsentiert. Zum Beispiel f[{f[{f[{}]}], f[{}]}]= f[{f[{0}], 0}]= f[{1, 0}]= 2. Alles andere wird produzieren E.
  4. Wir testen, ob das Ergebnis eine natürliche Zahl ist, indem wir prüfen, ob dies nicht der Fall ist E.
Mischa Lawrow
quelle
3

Brachylog (v2), 9 Bytes

↰ᵐo.t~k|Ė

Probieren Sie es online!

Wie bei üblich , handelt es sich um ein vollständiges Programm. Eingabe von der Standardeingabe mit eckigen Klammern. Ausgabe auf Standardausgabe als true.versus false..

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 oder false.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 Sie true.". . 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:

↰ᵐo.t~k|Ė
↰ᵐ          Map a recursive call to this function over the list
  o         Sort the list
   .   |    Assert that the following operation need not change the list:
    t         Take the last (i.e. greatest) element of the list
     ~k       Append an arbitrary element to the resulting list
   .   |    Output the unchanged list
       |    Exception handler: if the above threw an exception,
        Ė     Assert that the input is empty, and output an empty list

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. oDas 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 mit t; Das behandelt diesen Fall, indem es einen expliziten Fallback für den Fall ausgibt, dass die Eingabeliste leer ist.

ais523
quelle
2

K (ngn / k) , 26 24 27 Bytes

~^{$[#(!#x)^o'x;0N;#x]}@`j@

Probieren Sie es online!

Die Eingabe ist eine JSON-Zeichenfolge, die von `j@(ngn / k-spezifische Syntax) analysiert wird.

{ }ist eine rekursive Funktion mit Argument x. es gibt die natürliche Zahl zurück, die durch die Menge dargestellt wird x, oder null ( 0N), wenn es keine Zahl darstellt .

$[ ; ; ]ist wenn-dann-sonst. 0 ist falsch, andere ganze Zahlen sind wahr

!#xdie ganzen Zahlen von 0 (einschließlich) bis zur Länge von x(ausschließlich)

^ ohne

o'xRekursion ( 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 ,

ngn
quelle
0

Japt , 9 Bytes

Port von Neils JS-Lösung . Bitte stimmen Sie dem zu, wenn Sie dies tun.

e@Ê>XÊ©ßX

Probieren Sie es aus oder führen Sie alle Testfälle aus

              :Implicit input of array U
e             :Does every element in U return true
 @            :When passed through the following function as X
  Ê           :Length of U
   >          :Greater than
    XÊ        :Length of X
      ©       :Logical AND with
       ßX     :A recursive call of the programme with X passed as the new value of U
Zottelig
quelle
0

Rot , 81 Bytes

func[a][p: 1 foreach e to-block a[p: p *(pick[1 0](length? e)< length? a)* f e]p]

Probieren Sie es online!

Ähnlich wie bei Leaky Nun's Python 3

Galen Ivanov
quelle
0

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

߀Ṣ   Helper link. Argument: A (array)

߀    Recursively map the helper link over A.
  Ṣ   Sort the result.

Dies ergibt eine kanonische Darstellung der Eingabe, die ausschließlich aus sortierten Arrays besteht.

ÇṖƤƑ  Main link. Argument: A (array)

Ç     Call the helper link to canonicalize the array.
   Ƒ  Fixed; call the link to the left and test if it returns its argument unchanged.
 ṖƤ       Pop prefix; for each non-empty prefix of the result, remove its last element.
Dennis
quelle
0

Gelee , 7 Bytes

Ẉ<La߀Ạ

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

Ẉ<La߀Ạ  Main link. Argument: A (array)

Ẉ        Width; compute the length of A's elements.
  L      Yield the length of A.
 <       Compare them, yielding an array of Booleans.
    ߀   Recursively map the main link over A.
   a     Take the logical AND of the Booleans and the results of the map.
      Ạ  All; yield 1 if and only if all ANDs yielded 1.
Dennis
quelle