Odwróć nowy liść

19

Dostajesz drzewo, które w tradycji informatycznej ma korzeń u góry i liście u dołu. Węzły liści są oznaczone liczbami. Twoim celem jest zabranie specjalnego liścia oznaczonego -1i przesunięcie go w górę, aby był nowym korzeniem.

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

wprowadź opis zdjęcia tutaj

Możesz sobie wyobrazić obrócenie specjalnego liścia do góry i pozwolenie, by reszta drzewa zwisała z niego. Utrzymywanie drzewa w płaszczyźnie podczas obracania go, aby uzyskać prawidłową kolejność wszystkich gałęzi od lewej do prawej.

Nowe drzewo ma wszystkie liście oryginalnego drzewa oprócz -1.

Wejście:

Drzewo, którego liście są wyraźnymi dodatnimi liczbami całkowitymi, z wyjątkiem jednego liścia -1. Korzeń drzewa będzie miał co najmniej dwie odgałęzienia.

Dane wejściowe są podawane jako zagnieżdżona lista [3, [[16], -1], [[4]]]lub jej ciąg znaków. Ograniczniki są opcjonalne i zależą od ciebie, ale sąsiednie liczby muszą być oddzielone.

Wynik:

Wyjdź lub wydrukuj przewrócone drzewo w tym samym formacie co dane wejściowe. Kolejność wpisów na liście musi być poprawna. Modyfikacja na miejscu jest w porządku.

Jeśli dane wejściowe / wyjściowe są typem danych, domyślnie musi to być drukowany w wymaganym formacie. Wbudowane, które w zasadzie wykonują zadanie za Ciebie, nie są dozwolone.

Przypadki testowe:

>> [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
źródło
1
Przykład wydaje się nie zgadzać z diagramem. 4Posiada dwa kolejne nawiasy wokół niego niż 3, ale jest tylko 1 warstwa diagramed głębiej.
isaacg

Odpowiedzi:

7

CJam, 24 24 22 bajtów

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

Wypróbuj online .

Dzięki Dennis za usunięcie 2 bajtów.

Wyjaśnienie

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
źródło
Możesz użyć {s$}$z odwróconą kolejnością sortowania. Również anonimowa funkcja zaoszczędziłaby jeden bajt w całym programie.
Dennis
1
@Dennis Thanks. Ale jeśli jest to funkcja, chyba potrzebuję dodatkowej [.
jimmy23013
6

Pyth, 26 25 24 23 bajtów

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

Demonstracja. Uprząż testowa.

Definiuje funkcję, yktóra pobiera zagnieżdżoną listę Pythów jako dane wejściowe.

Istnieją trzy przypadki, w celu zbadania tej funkcji rekurencyjnej, ze względu na trójskładnikowych ?, a próba - z wyjątkiem funkcji .x. W funkcji wejście to b.

Pierwszy przypadek występuje, gdy }\-`Jtbjest prawdą. To sprawdza, czy -w reprezentacji ciągu tbznajduje się „ogon” b, który jest bwyjątkiem z wyjątkiem pierwszego elementu. tbjest również przechowywany w J. Ponieważ wszystkie etykiety są dodatnie, z wyjątkiem -1, będzie to prawdą wtedy i tylko wtedy, gdy -1nie będzie w pierwszym elemencie listy.

W takim przypadku cyklicznie przesuwamy w prawo bo 1 za pomocą .>b1, a następnie wywołujemy funkcję rekurencyjnie. To gwarantuje, że przejdziemy do następnego kroku z elementem zawierającym -1jako nagłówek (pierwszy element) listy.

W następnych dwóch przypadkach powyższe jest fałszem, więc -1znajduje się na czele listy.

W drugim przypadku ahbJnie zgłasza błędu. Błąd zostanie wygenerowany tylko wtedy, gdy hbjest liczbą całkowitą. Jeśli tak nie jest, to hbjest lista i musimy obrócić drzewo, aby -1liść był bliżej korzenia. ahbJdokonuje tego poprzez dołączenie Jjako jednego elementu na końcu hb, który skutecznie przenosi korzeń drzewa od bdo hb.

W trzecim i ostatnim przypadku generowany jest błąd. Zatem hbjest jednym elementem. Ze względu na test w pierwszym przypadku hbmusi być -1. W ten sposób możemy zwrócić resztę b, a mianowicie J, zawinięte w listę, a mianowicie ]J.

isaacg
źródło