Dalam informatika, kita sering menggunakan pohon dalam berbagai bentuk dan representasi. Tiga metode utama serialisasi pohon biner adalah awalan, infiks dan notasi postfix. Sebagai contoh, pohon biner berikut:
(sumber: Olimpiade Belanda di Informatika, final, 2012/13)
dapat direpresentasikan dalam notasi prefix as abrxdbe
, in infix as rbxabde
dan postfix as rxbbeda
.
Dalam hal ini, Anda dihadapkan dengan pohon biner lengkap yang diwakili dalam notasi infiks . Tugas Anda adalah mengubah pohon ini menjadi notasi awalan . Anda masukan pada stdin akan 2 n -1 karakter abjad huruf kecil, az dan tidak lebih, berakhir dengan karakter baris baru, untuk setiap bilangan bulat n sehingga 1 ≤ n ≤ 16. Dengan demikian, jumlah maksimum karakter yang Anda akan dapatkan adalah 65535. Keluarkan pohon ke stdout dengan cara yang sama, tetapi kemudian dalam format awalan.
Ini adalah kode golf, jadi kode terpendek, yang dihitung dalam byte, akan menang. Suara akan bertindak sebagai pemutus dasi, dan jika itu mengikat juga, tanggal dan waktu pengiriman.
sumber
Jawaban:
GolfScript, 23 karakter
Solusi ini menggunakan pendekatan yang berbeda dari Howard: pada dasarnya, ia mengurutkan karakter input sesuai dengan daftar cabang yang diperlukan untuk mencapai karakter itu dari akar pohon.
Perhatikan bahwa baris baru di akhir input diperlukan (mis. Panjang input harus memiliki kekuatan dua). Di
n-
akhir kode diperlukan untuk menekan baris baru ekstra di awal output; jika baris baru tersebut dapat diterima, karakter tersebut dapat dihilangkan dengan skor 21 karakter.Seperti biasa, Anda dapat menguji kode ini secara online.
Penjelasan:
.,\
menghitung panjang input, dan memindahkannya di bawah string input pada stack. Ini akan digunakan sebagai nilai awal dari penghitung loop yang digunakan untuk membuat kunci sortir di bawah ini. (Kode mengandalkan ini menjadi kekuatan dua; jika tidak, manipulasi bit di bawah ini tidak akan menghasilkan hasil yang diharapkan. Namun, kekuatan dua yang cukup besar akan bekerja.){ }$
mengurutkan karakter dalam string input sesuai dengan tombol sortir yang dihitung di dalam blok:;
hanya membuang karakter yang diberikan sebagai input ke blok; kami tidak peduli dengan nilai karakter aktual di sini, hanya tentang posisi mereka dalam string.).
menambah penghitung lingkaran pada tumpukan (yang diinisialisasi dengan panjang string input) dan membuat salinannya.2base
mengkonversi salinan ini ke array bit (menghilangkan nol terkemuka; itu sebabnya kita perlu mulai menghitung dari kekuatan dua yang cukup besar, daripada hanya dari nol).{)!}do
berulang kali memotong bit terendah dari array sampai bit yang dipotong adalah a1
.Karena kunci sortir yang dihasilkan adalah array, maka
$
membandingkannya secara leksikografis. Jadi, misalnya, array[1]
(yang sesuai dengan simpul root) mengurutkan sebelumnya[1 0]
(yang sesuai dengan anak kiri dari simpul root) dan[1 1]
(anak kanan dari simpul root).Pada akhirnya,
/
hilangkan counter loop dengan menggunakannya sebagai panjang potongan untuk membagi string output menjadi (terima kasih, Peter!), Dann-
lepaskan baris baru dari string input yang diurutkan. (Interpreter GolfScript akan menambahkan baris baru ke output setelah mencetak isi tumpukan.)sumber
\;
menyingkirkan penghitung lingkaran, Anda dapat/
membagi string menjadi bagian yang lebih besar dari sebelumnya. (n-
Akan bahkan kemudian menariknya kembali dari array yang dibuat).GolfScript, 28 karakter
Anda dapat menguji kode secara online .
Kode beranotasi:
sumber
GolfScript (29 karakter)
Demo online
Bekerja dengan atau tanpa baris baru di input.
sumber
APL (48)
(Ya, rangkaian aplikasi APL cocok dengan satu byte .)
Penjelasan:
{
...}⍞
: baca input, umpan berfungsi1=⍴⍵:⍵
: jika panjang input adalah satu, kita sudah selesai⋄
: jika tidak:(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵
: buat bitfield tempat untuk membagi input (karakter pertama, karakter tengah, dan karakter yang melewati karakter tengah)⍵⊂⍨
: pisahkan input di tempat-tempat inia←1⌽⌽
: putar sub-array sehingga karakter tengah adalah yang pertama, tangan kiri adalah yang kedua dan tangan kanan yang ketiga, dan simpan dia
.⊃,/∇¨1↓a
: jalankan fungsi lagi pada dua elemen terakhira
dan gabungkan hasilnya(⊃a),
: dan menyatukannya dengan item pertama dia
sumber
Python 3 - 76
sumber
C, 108 karakter
Kode saya menggunakan fungsi rekursif, yang selalu mencetak karakter di tengah buffer, dan menyebut dirinya dengan bagian string sebelum dan bagian string setelah karakter dicetak. (Memecah dan menaklukkan)
ungolfed:
sumber