Hintergrund
Ein unbeschrifteter Baum kann folgendermaßen aussehen:
o
/ | \
o o o
| / \
o o o
Um diesen Baum zu linearisieren, kennzeichnen wir zuerst jeden Knoten o
mit der Anzahl der untergeordneten Knoten:
3
/ | \
1 0 2
| / \
0 0 0
und schreiben Sie dann die Zahlen in einer Liste auf eine atemlose Weise, dh Zeile für Zeile und von links nach rechts:
[3, 1, 0, 2, 0, 0, 0]
Dies ist eine einzigartige und eindeutige Darstellung des obigen Baums, was bedeutet, dass keine zwei verschiedenen reinen Bäume die gleichen Linearisierungen haben und dass wir den ursprünglichen Baum aus der Liste rekonstruieren können.
Obwohl jeder Baum einer bestimmten Ganzzahlliste entspricht, stellt nicht jede Ganzzahlliste einen gültigen linearisierten Baum dar: Zum Beispiel [2, 0, 0, 0]
stellt er keinen gültigen Baum dar. Wenn wir versuchen, ihn zu delinearisieren, erhalten wir diesen Baum
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
/ \ / \ / \
0 0 0
aber noch eine 0
links in der Liste und nirgends zu setzen. Ebenso [2, 0]
ist auch keine gültige Baumlinearisierung, da der de-linearisierte Baum einen leeren untergeordneten Punkt hat:
2
/ \
0
Aufgabe
Entscheiden Sie anhand einer Ganzzahlliste, ob es sich um eine gültige Linearisierung eines Baums handelt, indem Sie so wenig Bytes wie möglich verwenden. Sie können ein vollständiges Programm oder eine Funktion schreiben.
Eingabe: Eine nicht leere Liste nicht negativer Ganzzahlen.
Ausgabe: Ein wahrer Wert, wenn die Liste eine Linearisierung eines Baums ist, andernfalls ein falscher Wert.
Testfälle
Wahrheit[0]
[2, 0, 0]
[1, 1, 1, 1, 1, 0]
[3, 1, 0, 2, 0, 0, 0]
[2, 0, 2, 2, 0, 0, 2, 0, 0]
[3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0]
[1, 5, 3, 0, 2, 1, 4, 0, 1, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0]
Falsch
[0, 1]
[2, 0]
[2, 0, 0, 0]
[1, 0, 1]
[3, 2, 1, 0]
[2, 0, 0, 2, 0, 0]
[4, 1, 0, 3, 0, 0, 0, 0]
[4, 2, 0, 3, 1, 0, 0, 0, 0, 0]
{X0@{+\(_{\}&}/|!}
Meiner Ansicht nach?@
.Labyrinth , 17 Bytes
Probieren Sie es online aus!
Die Wahrheitsausgabe ist
-1
und die Falschausgabe ist leer. Die Definition von Wahrheit und Falschheit im Labyrinth ist etwas schwierig, da die Zweige des Labyrinths hauptsächlich ternär sind. Die einzige Möglichkeit, eine Bedingung mit zuverlässig zwei Zweigen zu erstellen, besteht jedoch nur darin:In diesem Fall würde ich in Betracht ziehen, mich geradeaus falsch zu bewegen (weil die Bewegungsrichtung nicht beeinflusst wird) und wahrheitsgemäß zu werden. Diese entsprechen Null bzw. Nicht-Null. Der Grund, warum ich eine leere Ausgabe verwende, um Null darzustellen, ist, dass der Eingabeoperator, wenn Sie die Ausgabe zurück in ein anderes Labyrinth-Programm leiten
?
würden, tatsächlich eine Null drücken würde, wenn die Eingabe leer ist. Daher halte ich die leere Zeichenfolge für gültig Darstellung von Null.Erläuterung
Der Algorithmus ist immer noch der gleiche wie in meinen Antworten von Mathematica und Retina, aber aufgrund des Kontrollflusses von Labyrinth funktioniert er diesmal etwas anders:
-11
zunächst so, dass der Zähler in der gesamten Liste negativ sein soll und bei der letzten Eingabe Null drücken soll. Dies vereinfacht hier tatsächlich den Kontrollfluss.Anstatt die vollständige Liste zu erstellen und zu überprüfen, ob sie den falschen Wert enthält, gibt es drei mögliche Beendigungsbedingungen:
Der eigentliche Code beginnt in der oberen linken Ecke. Das
(
schaltet die implizite Null auf der Oberseite des Stapels in einen-1
, die die laufenden Summe wird. Wir betreten dann die sehr enge Hauptschleife des Programms+?-)"_,;+
:Das lässt nur die Fälle übrig, in denen wir die laufende Summe irgendwann auf Null reduziert haben. Die IP-Adresse bewegt sich nach rechts unten
,
und liest ein anderes Zeichen, um zu überprüfen, ob wir EOF erreicht haben. Wenn nicht, ist der Wert positiv und die IP dreht sich nach Westen in Richtung@
und das Programm wird beendet. Wenn wir EOF erreicht haben, dreht sich die IP nach Osten und druckt die-1
mit!
. Die IP wird sich dann@
über einen etwas seltsamen Pfad nach links unten bewegen, um das Programm zu beenden.quelle
Python, 82 Bytes
Benötigen Sie weitere Testfälle.
quelle
list
wenn dies mindestens Python 2 ist. Wenn Sie die zweite Bedingung neu anordnen und invertieren, können Sie sie auf 70 Byte bringen:lambda l:all(l[x]<len(l)-x for x in range(len(l)))and len(l)==sum(l)+1
all
zux<len(l)-y for y,x in enumerate(l)
2 weiteren Bytes speichern Sie es auf 68 zu bekommenPyth, 13 Bytes
Wir beginnen mit der Berechnung der aktuellen Füllung des Baums an allen Punkten in der Eingabedarstellung. Dieser Teil der Idee ist größtenteils von Martin Ender entlehnt, also dank ihm.
sM._tMQ
Sobald wir diese Liste haben, prüfen wir, ob der erste Index, der
-1
(x..._1
) enthält, die Länge der Eingabe minus eins (q...tl(Q)
) ist.Glauben Sie nicht, dass es funktioniert? Versuch es selber!
quelle