Terinspirasi oleh A014486 .
Tantangan
Diberikan input integer pada basis 10, buat representasi untuk hutan biner yang sesuai dengan input tersebut. Representasi termasuk, tetapi tidak terbatas pada, array bersarang dan string.
Bagaimana?
Ubah input menjadi biner. 1
s mewakili cabang, dan 0
s mewakili daun.
Untuk membuatnya lebih mudah dipahami, mari gunakan 834
(1101000010 dalam biner) sebagai contoh.
Kita mulai dengan digit pertama. Digit pertama adalah a 1
, jadi kami menggambar cabang:
\ / 1
atau sebagai array, {{1}}
Digit berikutnya adalah 1
, jadi kami menggambar lebih banyak cabang (kami bergerak dari kiri ke kanan):
\ / 1 \ / 1
atau sebagai array, {{1, {1}}}
Digit berikutnya adalah 0
, jadi kami menempatkan daun:
0 \ / 1 \ / 1
atau sebagai array, {{1, {1, 0}}}
Digit berikutnya adalah a 1
, jadi kami menempatkan cabang:
\ / 0 1 \ / 1 \ / 1
atau sebagai array, {{1, {1, 0, {1}}}}
Mengulangi proses, kita mendapatkan pohon berikut setelah digit ke-8:
0 0 \ / 0 1 \ / 1 0 \ / 1
atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}}
Untuk digit yang tersisa, kami menggambar lebih banyak pohon:
Digit ke-9 adalah 0
, jadi kami menempatkan daun (aww, ini adalah pemotretan muda!)
0 0 \ / 0 1 \ / 1 0 \ / 1 0
atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}, 0}
Ketika kita menggunakan semua digit, kita berakhir dengan ini:
0 0 \ / 0 1 \ / 1 0 0 \ / \ / 1 0 1
atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0}}
Itu terlihat aneh, jadi kami membuat nol untuk melengkapi pohon:
0 0 \ / 0 1 \ / 1 0 0 0 \ / \ / 1 0 1
atau sebagai array, {{1, {1, 0, {1, 0, 0}}, 0}, 0, {1, 0, 0}}
Perhatikan bahwa mendatarkan array menghasilkan angka asli dalam biner, tetapi dengan nol yang empuk.
Kriteria
- Output harus jelas menunjukkan pemisahan pohon dan cabang (jika bukan array bersarang, tolong jelaskan format output Anda).
- Mengekstraksi semua digit dari output harus identik dengan representasi biner dari input (dengan nol yang diisi dari proses di atas).
Uji kasus
Output mungkin berbeda selama memenuhi kriteria.
0 -> {0} 1 -> {{1, 0, 0}} 44 -> {{1, 0, {1, {1, 0, 0}, 0}}} 63 -> {{1, {1, {1, {1, {1, {1, 0, 0}, 0}, 0}, 0}, 0}, 0}, 0}} 404 -> {{1, {1, 0, 0}, {1, 0, {1, 0, 0}}}} 1337 -> {{1, 0, {1, 0, 0}}, {1, {1, {1, 0, 0}, {1, 0, 0}}, 0}}
Mencetak gol
Ini adalah kode-golf , sehingga byte terendah menang!
sumber
Jawaban:
JavaScript (ES6),
968980797473 byteMenentukan fungsi
f
yang mengembalikan array bersarang. Kode HTML hanya untuk pengujian.sumber
$&
dilakukan tanpa.replace
?" : PBefunge,
138117104 byteCobalah online!
Penjelasan
Baris 1 membaca angka dari stdin, dan baris 2 mengubah angka itu menjadi urutan biner yang disimpannya di playfield pada baris 10. Baris 3 hingga 5 kemudian beralih di atas angka-angka biner, menghasilkan representasi pohon yang sesuai saat setiap digit diproses. Tumpukan Befunge digunakan untuk melacak kedalaman ke dalam pohon dan berapa banyak ruang daun yang tersisa di setiap tingkat sehingga kami tahu kapan harus membuat cabang baru. Baris 6 dan 7 menangani
0
bantalan terakhir untuk mengisi semua daun kosong.Untuk bermain golf ini sebanyak mungkin, saya menghapus koma dari output serta kawat gigi luar yang asing. Ini masih belum mengalahkan solusi Mathematica, tetapi sudah menyenangkan mencoba.
Jika Anda ingin melihat seperti apa bentuknya dengan format output verbose asli, saya menyimpan versi kode yang lebih lama di sini (131 byte).
sumber
Mathematica,
167161 byteFungsi anonim. Mengambil nomor sebagai input, dan mengembalikan daftar angka yang disarang secara acak sebagai output. Jeda baris ditambahkan untuk kejelasan. Menggunakan beberapa mekanisme yang melibatkan kelanjutan, tetapi saya terlalu lelah untuk memikirkannya lagi.
sumber
#[[1]]
untuk#&@@#
harus menyimpan byte.!#~FreeQ~1
bukannya#~MemberQ~1
menyimpan byte juga.Mathematica,
11510910810498 byteMenghasilkan pesan kesalahan yang dapat diabaikan dengan aman. Menghasilkan hutan biner. Ini sedikit berbeda dari output sampel karena
1
aHead
, bukan elemen pertama dari daftar. (misalnya,1[0, 0]
bukannya{1, 0, 0}
)Versi bebas kesalahan (104 byte)
Penjelasan
Konversikan input ke daftar base-2. Menyimpannya dalam
i
.SetDelay
f
berikut ini (dievaluasi kapan punf
dipanggil):Switch
pernyataan.Pertama, jika
i
kosong, output0
. Jika tidak, output elemen pertamai
dan jatuhkan dari daftar. Gunakan output sebagai variabel kontrol.Jika variabel kontrol adalah
0
, output0
. Jika ya1
, output1[f, f]
(rekursif).Meskipun
i
tidak kosong, teruslah meneleponf
. Keluarkan hasilnya, dibungkus denganList
.Contoh
Solusi alternatif (120 byte)
Identik dengan solusi 104 byte saya tetapi mengubah output ke dalam format yang diberikan dalam pertanyaan.
sumber
Python 2,
133118117 byteSebagian rekursif, sebagian berulang. Saya mencoba menggunakan integer, tetapi pohon dimulai dengan bit yang paling signifikan, jadi saya tidak berpikir itu sepadan.
Cobalah online
sumber
Java 8, 367 byte
Golf:
Tidak Disatukan:
sumber
DUP , 84 byte (82 karakter)
Untuk alasan bermain golf, saya menyingkirkan kurung kurawal luar dan koma karena tidak diperlukan untuk merekonstruksi pohon.
Output contoh:
Penjelasan:
Cobalah dengan penerjemah DUP Javascript online di quirkster.com atau klon repositori GitHub saya dari penerjemah DUP saya yang ditulis dalam Julia.
sumber