Balikkan lembaran baru

19

Anda diberi pohon, yang dalam tradisi ilmu komputer, memiliki akar di bagian atas dan daun di bagian bawah. Node daun diberi label dengan angka. Tujuan Anda adalah untuk mengambil daun khusus yang ditandai -1dan memindahkannya ke atas untuk menjadi root baru.

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

masukkan deskripsi gambar di sini

Anda dapat membayangkan memutar daun khusus ke atas dan membiarkan sisa pohon menggantungnya. Menyimpan pohon di pesawat sambil memutarnya untuk mendapatkan urutan kiri-ke-kanan yang benar dari semua cabang.

Pohon baru memiliki semua daun pohon asli kecuali untuk -1.

Memasukkan:

Sebuah pohon yang daunnya bilangan bulat positif berbeda, kecuali satu daun -1. Akar pohon akan memiliki setidaknya dua cabang yang terlepas.

Input diberikan sebagai daftar bersarang seperti [3, [[16], -1], [[4]]]atau representasi stringnya. Pembatas adalah opsional dan terserah Anda, tetapi angka yang berdekatan perlu dipisahkan.

Keluaran:

Keluarkan atau cetak pohon terbalik dalam format yang sama dengan input Anda. Urutan entri daftar harus benar. Modifikasi di tempat baik-baik saja.

Jika input / output Anda adalah tipe data, itu harus salah satu yang mencetak dalam format yang diperlukan secara default. Built-in yang pada dasarnya melakukan tugas untuk Anda tidak diizinkan.

Kasus uji:

>> [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]]
Tidak
sumber
1
Contohnya tampaknya tidak sejalan dengan diagram. The 4memiliki dua kurung lebih di sekitarnya dari 3, tetapi diagramed hanya 1 lapisan yang lebih dalam.
isaacg

Jawaban:

7

CJam, 24 24 22 byte

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

Cobalah online .

Terima kasih Dennis untuk menghapus 2 byte.

Penjelasan

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
sumber
Anda dapat menggunakan {s$}$, dengan urutan terbalik. Juga, fungsi anonim akan menghemat satu byte lebih dari satu program penuh.
Dennis
1
@Dennis Terima kasih. Tetapi jika itu adalah fungsi, saya kira saya akan membutuhkan tambahan [.
jimmy23013
6

Pyth, 26 25 24 23 byte

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

Demonstrasi. Uji Harness.

Ini mendefinisikan fungsi,, yyang mengambil daftar Pyth bersarang sebagai input.

Ada tiga kasus untuk dieksplorasi dalam fungsi rekursif ini, karena ternary ?,, dan fungsi coba - kecuali .x,. Dalam fungsinya, inputnya adalah b.

Kasus pertama terjadi ketika }\-`Jtbbenar. Ini menguji apakah ada -dalam representasi string tb, "ekor" darib , yang semuanya bkecuali elemen pertamanya. tbjuga disimpan di J. Karena semua label positif kecuali untuk -1, ini akan menjadi benar jika dan hanya jika -1tidak ada dalam elemen pertama dari daftar.

Dalam hal ini, kita menggeser bsecara siklis dengan 1 dengan .>b1, dan kemudian memanggil fungsi secara rekursif. Ini memastikan bahwa kita akan maju ke langkah berikutnya dengan elemen yang mengandung -1sebagai kepala (elemen pertama) dari daftar.

Dalam dua kasus berikutnya, yang di atas adalah falsy, begitu -1juga di kepala daftar.

Dalam kasus kedua, ahbJjangan melempar kesalahan. Kesalahan akan terjadi jika dan hanya jika hbbilangan bulat. Jika ini bukan masalahnya, maka hbdaftar, dan kita perlu memutar pohon sehingga -1daunnya lebih dekat ke akar. ahbJmenyelesaikan ini dengan menambahkan Jsebagai elemen tunggal di akhir hb, yang secara efektif memindahkan akar pohon dari bke hb.

Dalam kasus ketiga dan terakhir, kesalahan dilemparkan. Dengan demikian, hbmerupakan elemen tunggal. Karena tes dalam kasus pertama, hbharus -1. Dengan demikian, kita dapat mengembalikan sisa b, yaitu J, dibungkus dalam daftar, yaitu ]J.

isaacg
sumber