In der Informatik verwenden wir oft Bäume in vielen verschiedenen Formen und Darstellungen. Die drei Hauptmethoden zum Serialisieren von Binärbäumen sind Präfix-, Infix- und Postfix-Notation. Zum Beispiel der folgende Binärbaum:
(Quelle: Niederländische Olympiade in Informatik, Finale, 2012/13)
kann in Präfixnotation als abrxdbe
, im Infix als rbxabde
und im Postfix als dargestellt werden rxbbeda
.
In diesem Fall werden Sie mit einem vollständigen Binärbaum konfrontiert, der in der Infixnotation dargestellt wird. Ihre Aufgabe ist es , diesen Baum in die Präfixnotation zu konvertieren . Ihre Eingabe in stdin besteht aus 2 n -1 Kleinbuchstaben, az und nicht mehr, die mit einem Zeilenumbruchzeichen für eine beliebige Ganzzahl n enden, sodass 1 ≤ n ≤ 16. Die maximale Anzahl von Zeichen, die Sie erhalten, beträgt also 65535. Geben Sie den Baum auf die gleiche Weise an stdout aus, jedoch im Präfixformat.
Dies ist Code Golf, also gewinnt der kürzeste Code, gezählt in Bytes. Die Stimmen wirken als Gleichstand, und wenn diese ebenfalls zusammenfallen, Datum und Uhrzeit der Einreichung.
quelle
Antworten:
GolfScript, 23 Zeichen
Diese Lösung verwendet einen anderen Ansatz als Howard: Grundsätzlich werden die Eingabezeichen nach der Liste der Zweige sortiert, die erforderlich sind, um dieses Zeichen von der Wurzel des Baums aus zu erreichen.
Beachten Sie, dass die neue Zeile am Ende der Eingabe erforderlich ist (dh die Eingabelänge muss eine Zweierpotenz sein). Das
n-
am Ende des Codes ist erforderlich, um einen zusätzlichen Zeilenumbruch am Anfang der Ausgabe zu unterdrücken. Wenn eine solche neue Zeile akzeptabel ist, können diese Zeichen für eine Punktzahl von 21 Zeichen weggelassen werden .Wie gewohnt können Sie diesen Code online testen.
Erläuterung:
.,\
berechnet die Länge der Eingabe und verschiebt sie unter die Eingabezeichenfolge auf dem Stapel. Es wird als Startwert des Schleifenzählers verwendet, der zum Erstellen der folgenden Sortierschlüssel verwendet wird. (Der Code basiert darauf, dass dies eine Zweierpotenz ist. Andernfalls führt die unten stehende Bitmanipulation nicht zu den erwarteten Ergebnissen. Eine ausreichend große Zweierpotenz würde jedoch funktionieren.){ }$
sortiert die Zeichen in der Eingabezeichenfolge nach dem im Block berechneten Sortierschlüssel:;
wirft einfach das Zeichen weg, das als Eingabe für den Block angegeben wurde; Die tatsächlichen Zeichenwerte sind uns hier egal, nur ihre Positionen innerhalb der Zeichenfolge.).
Inkrementiert den Schleifenzähler auf dem Stapel (der auf die Länge der Eingabezeichenfolge initialisiert wurde) und erstellt eine Kopie davon.2base
konvertiert diese Kopie in ein Array von Bits (ohne führende Nullen; deshalb müssen wir mit dem Zählen von einer ausreichend großen Zweierpotenz beginnen, anstatt einfach von Null).{)!}do
hackt wiederholt das niedrigste Bit vom Array ab, bis das abgeschnittene Bit a ist1
.Da die resultierenden Sortierschlüssel Arrays sind, werden
$
sie lexikografisch verglichen. So[1]
sortiert beispielsweise das Array (das dem Wurzelknoten entspricht) vor[1 0]
(das dem linken Kind des Wurzelknotens entspricht) und[1 1]
(dem rechten Kind des Wurzelknotens).Am Ende
/
wird der Schleifenzähler entfernt, indem er als Länge der Chunks verwendet wird, in die die Ausgabezeichenfolge aufgeteilt wird (danke, Peter!), Undn-
die neue Zeile von der sortierten Eingabezeichenfolge entfernt wird. (Der GolfScript-Interpreter fügt der Ausgabe nach dem Drucken des Stapelinhalts eine weitere neue Zeile hinzu.)quelle
\;
den Schleifenzähler zu entfernen, können Sie/
den String in Abschnitte aufteilen, die größer sind als er ist. (Dasn-
wird es auch dann wieder aus dem so erstellten Array ziehen).GolfScript, 28 Zeichen
Sie können den Code online testen .
Kommentierter Code:
quelle
GolfScript (29 Zeichen)
Online-Demo
Funktioniert mit oder ohne den nachgestellten Zeilenumbruch in der Eingabe.
quelle
APL (48)
(Ja, der APL-Zeichensatz passt in ein Byte .)
Erläuterung:
{
...}⍞
: Eingabe lesen, Funktion einspeisen1=⍴⍵:⍵
: Wenn die Eingabelänge eins ist, sind wir fertig⋄
: Andernfalls:(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵
: Erstellen Sie ein Bitfeld mit Stellen, an denen die Eingabe aufgeteilt werden soll (erstes Zeichen, mittleres Zeichen und Zeichen nach dem mittleren Zeichen).⍵⊂⍨
: Teilen Sie die Eingabe an diesen Stellena←1⌽⌽
: Drehen Sie die Sub-Arrays so, dass das mittlere Zeichen an erster Stelle steht, die linke Hand an zweiter Stelle und die rechte Hand an dritter Stelle steht, und speichern Sie ina
.⊃,/∇¨1↓a
: Führen Sie die Funktion für die letzten beiden Elemente von erneut ausa
und verketten Sie die Ergebnisse(⊃a),
: und verketten Sie das mit dem ersten Element ina
quelle
Python 3 - 76
quelle
C 108 Zeichen
Mein Code verwendet eine rekursive Funktion, die das Zeichen immer in der Mitte des Puffers druckt und sich mit dem Teil der Zeichenfolge vor und dem Teil der Zeichenfolge nach dem gedruckten Zeichen aufruft. (Teilen und Erobern)
ungolfed:
quelle