Drehen Sie ein neues Blatt um

19

Sie erhalten einen Baum, der in der Tradition der Informatik die Wurzel oben und die Blätter unten hat. Die Blattknoten sind mit Zahlen beschriftet. Ihr Ziel ist es, das markierte Spezialblatt zu nehmen -1und es als neue Wurzel nach oben zu bewegen.

[3, [[16], -1], [4]] --> [[[[4], 3], [16]]]

Bildbeschreibung hier eingeben

Sie können sich vorstellen, das Spezialblatt nach oben zu drehen und den Rest des Baumes hängen zu lassen. Halten Sie den Baum in der Ebene, während Sie ihn drehen, um die richtige Reihenfolge aller Zweige von links nach rechts zu erhalten.

Der neue Baum hat bis auf alle Blätter des ursprünglichen Baumes -1.

Eingang:

Ein Baum, dessen Blätter eindeutige positive ganze Zahlen sind, mit Ausnahme eines Blattes von -1. Die Wurzel des Baumes wird mindestens zwei Äste haben.

Die Eingabe wird als verschachtelte Liste [3, [[16], -1], [[4]]]oder als Zeichenfolgendarstellung angegeben. Trennzeichen sind optional und stehen Ihnen frei, aber benachbarte Zahlen müssen getrennt werden.

Ausgabe:

Geben Sie den gespiegelten Baum im gleichen Format wie Ihre Eingabe aus oder drucken Sie ihn aus. Die Reihenfolge der Listeneinträge muss korrekt sein. Die direkte Änderung ist in Ordnung.

Wenn es sich bei Ihrer Eingabe / Ausgabe um einen Datentyp handelt, muss dieser standardmäßig im erforderlichen Format gedruckt werden. Built-Ins, die im Grunde genommen die Aufgabe für Sie erledigen, sind nicht erlaubt.

Testfälle:

>> [3, [[16], -1], [4]]
[[[[4], 3], [16]]]

>> [2, -1]
[[2]]

>> [44, -1, 12]
[[12, 44]]

>> [[[[-1]]], [[[[4]]]]]
[[[[[[[[[4]]]]]]]]]

>> [[1, 2, 3], [4, -1, 6], [7, 8, 9]]
[[6, [[7, 8, 9], [1, 2, 3]], 4]]

>> [9, [8, [7, [6, -1, 4], 3], 2], 1]
[[4, [3, [2, [1, 9], 8], 7], 6]]
xnor
quelle
1
Das Beispiel scheint nicht mit dem Diagramm übereinzustimmen. Die 4hat zwei Klammern mehr als die 3, ist aber nur 1 Schicht tiefer dargestellt.
Isaacg

Antworten:

7

CJam, 24 24 22 Bytes

l~{):T]{s$}$(+T1+}gW<p

Probieren Sie es online aus .

Danke Dennis für das Entfernen von 2 Bytes.

Erläuterung

l~          e# Read the input.
{           e# Do:
    ):T     e# Save the last item to T.
    ]       e# Wrap everything else (as an array) and the last item into an array,
    {s$}$   e#   where the one with -1 (having "-" if stringified) is the first item.
    (+      e# Insert the second array into the first array as the first item,
            e#   or just move the -1 to the end if the first item is already -1.
    T1+     e# Check if the array before this iteration ended with -1.
}g          e# Continue the loop if it did't.
W<p         e# Remove the -1 and print.
jimmy23013
quelle
Sie können {s$}$mit umgekehrter Sortierreihenfolge verwenden. Außerdem würde eine anonyme Funktion ein Byte über ein volles Programm speichern.
Dennis
1
@ Tennis Danke. Aber wenn es eine Funktion ist, brauche ich wahrscheinlich eine zusätzliche [.
Jimmy23013
6

Pyth, 26 25 24 23 Bytes

L?y.>b1}\-`Jtb.xyahbJ]J

Demonstration. Testgeschirr.

Dies definiert eine Funktion, ydie eine verschachtelte Pyth-Liste als Eingabe verwendet.

Aufgrund der ternären ?Funktion und der try - except - Funktion sind in dieser rekursiven Funktion drei Fälle zu untersuchen .x. In der Funktion ist die Eingabe b.

Der erste Fall tritt auf, wenn }\-`Jtbes wahr ist. Dies testet, ob es -in der Zeichenfolgendarstellung einen tb"Schwanz" von gibt b, der alles bandere als sein erstes Element ist. tbist auch gespeichert in J. Da alle Bezeichnungen mit Ausnahme von positiv sind -1, gilt dies genau dann, wenn sich das -1nicht im ersten Element der Liste befindet.

In diesem Fall verschieben wir uns mit zyklisch nach rechts bum 1 .>b1und rufen die Funktion dann rekursiv auf. Dies stellt sicher, dass wir mit dem Element -1als Kopf (erstes Element) der Liste zum nächsten Schritt übergehen.

In den nächsten beiden Fällen ist das oben Gesagte falsch, ebenso -1wie im Kopf der Liste.

Im zweiten Fall ahbJwird kein Fehler ausgelöst. Ein Fehler wird nur dann ausgelöst, wenn hbes sich um eine Ganzzahl handelt. Wenn dies nicht der Fall ist, hbhandelt es sich um eine Liste, und wir müssen den Baum so drehen, dass das -1Blatt näher an der Wurzel liegt. ahbJerreicht dies durch Anhänge Jam Ende als ein einziges Element hb, das effektiv die Wurzel des Baumes aus bewegt bzu hb.

Im dritten und letzten Fall wird ein Fehler ausgelöst. Somit hbist ein einzelnes Element. Da muss der Test im ersten Fall hbsein -1. So können wir den Rest bnämlich Jin einer Liste verpackt zurückgeben, nämlich ]J.

isaacg
quelle