Latar Belakang
Pohon tanpa label mungkin terlihat seperti ini:
o
/ | \
o o o
| / \
o o o
Untuk merender pohon ini, pertama-tama kita beri label pada setiap simpul o
dengan jumlah simpul turunannya:
3
/ | \
1 0 2
| / \
0 0 0
dan kemudian tulis angka-angka dalam daftar dengan cara yang menarik napas pertama, artinya baris demi baris dan kiri ke kanan:
[3, 1, 0, 2, 0, 0, 0]
Ini adalah representasi unik dan tidak ambigu dari pohon di atas, yang berarti bahwa tidak ada dua pohon murni yang berbeda akan memiliki linierisasi yang sama dan bahwa kita dapat merekonstruksi pohon asli dari daftar.
Meskipun setiap pohon sesuai dengan daftar bilangan bulat tertentu, tidak setiap daftar bilangan bulat mewakili pohon linier yang valid: Sebagai contoh [2, 0, 0, 0]
tidak mewakili pohon yang valid, jika kita mencoba untuk de-linierisasi itu kita berakhir dengan pohon ini
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
/ \ / \ / \
0 0 0
tetapi masih memiliki 0
kiri dalam daftar dan tidak ada tempat untuk meletakkannya. Demikian pula [2, 0]
juga bukan linierisasi pohon yang valid, karena pohon de-linierisasi memiliki bercak anak kosong:
2
/ \
0
Tugas
Diberikan daftar integer, putuskan apakah itu linearisasi pohon yang valid menggunakan sesedikit mungkin byte. Anda dapat menulis program atau fungsi lengkap.
Input: Daftar bilangan bulat non-kosong yang tidak kosong.
Output: Nilai kebenaran jika daftar adalah linierisasi pohon, nilai palsu sebaliknya.
Testcases
Sejujurnya[0]
[2, 0, 0]
[1, 1, 1, 1, 1, 0]
[3, 1, 0, 2, 0, 0, 0]
[2, 0, 2, 2, 0, 0, 2, 0, 0]
[3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0]
[1, 5, 3, 0, 2, 1, 4, 0, 1, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0]
Falsy
[0, 1]
[2, 0]
[2, 0, 0, 0]
[1, 0, 1]
[3, 2, 1, 0]
[2, 0, 0, 2, 0, 0]
[4, 1, 0, 3, 0, 0, 0, 0]
[4, 2, 0, 3, 1, 0, 0, 0, 0, 0]
{X0@{+\(_{\}&}/|!}
Kupikir?@
.Labirin , 17 byte
Cobalah online!
Output yang benar adalah
-1
dan output yang salah kosong. Mendefinisikan kebenaran dan kepalsuan di Labyrinth agak sulit, karena cabang-cabang Labyrinth pada dasarnya adalah ternary. Namun, satu-satunya cara untuk membangun sebuah kondisional dengan dua cabang andal, Anda hanya dapat melakukan ini:Dalam hal ini, saya akan mempertimbangkan untuk bergerak lurus ke depan falsy (karena arah gerakan tidak terpengaruh) dan mengubah kebenaran. Ini sesuai dengan nol dan non-nol masing-masing. Alasan saya menggunakan output kosong untuk mewakili nol adalah bahwa, jika Anda mem-pipe output kembali ke program Labirin lain, operator input
?
akan benar-benar mendorong nol jika input kosong, jadi saya menganggap string kosong valid representasi nol.Penjelasan
Algoritma ini masih sama dengan jawaban Mathematica dan Retina saya, tetapi karena aliran kontrol Labyrinth, kali ini kerjanya sedikit berbeda:
-11
semula, sehingga kami ingin penghitung negatif di seluruh daftar dan mencapai nol pada input terakhir. Ini sebenarnya menyederhanakan aliran kontrol di sini.Alih-alih membuat daftar lengkap dan memeriksa apakah mengandung nilai yang salah, ada tiga kemungkinan kondisi pemutusan:
Adapun kode aktual, kita mulai di sudut kiri atas. The
(
ternyata nol implisit di atas tumpukan ke dalam-1
, yang akan menjadi total berjalan. Kami kemudian memasuki loop utama yang sangat ketat dari program+?-)"_,;+
,:Yang tersisa hanya kasus di mana kami telah mengurangi total berjalan ke nol di beberapa titik. IP bergerak ke kanan bawah
,
dan membaca karakter lain untuk memeriksa apakah kita telah mencapai EOF. Jika tidak, nilainya akan positif dan IP berbalik ke barat menuju@
dan program berakhir. Jika kami mencapai EOF, IP berbelok ke timur dan mencetak-1
dengan!
. IP kemudian akan mencari jalan ke kiri bawah@
melalui jalan yang sedikit aneh untuk menghentikan program.sumber
Python, 82 byte
Perlu lebih banyak test case.
sumber
list
ini jika ini adalah Python 2 setidaknya, dan dengan menata ulang dan membalikkan kondisi kedua Anda bisa mendapatkannya hingga 70 byte:lambda l:all(l[x]<len(l)-x for x in range(len(l)))and len(l)==sum(l)+1
all
menjadix<len(l)-y for y,x in enumerate(l)
untuk menyimpan 2 byte lagi untuk mendapatkannya menjadi 68.Pyth, 13 byte
Kami mulai dengan menghitung kepenuhan pohon saat ini di semua titik dalam representasi input. Bagian dari gagasan itu sebagian besar dipinjam dari Martin Ender, jadi terima kasih padanya.
sM._tMQ
Setelah kami memiliki daftar ini, kami memeriksa apakah indeks pertama yang berisi
-1
(x..._1
) adalah panjang dari input minus satu (q...tl(Q)
).Tidak percaya itu berhasil? Cobalah sendiri!
sumber