Pohon pembagi estetis adalah pohon pembagi input n
yang, untuk setiap nomor komposit m
, memiliki dua anak simpul yang merupakan pasangan pembagi yang paling dekat dengan akar kuadrat dari m
. Simpul kiri harus pembagi yang lebih kecil m
dan simpul kanan harus pembagi yang lebih besar m
. Bilangan prima di pohon seharusnya tidak memiliki simpul anak. Pohon Anda mungkin dalam bentuk seni teks atau gambar. Aturan untuk output seni teks adalah sebagai berikut.
Aturan jarak
Untuk menghapus node di pohon, kami memiliki aturan berikut:
- Node pada kedalaman tertentu dari root semua harus berada pada baris teks yang sama dalam output.
/ \ TIDAK / \ / \ / 3 2 3 2
- Untuk node kiri, cabang yang masuk harus di kanan atas jika node adalah angka satu digit, yang lain, tepat di atas digit terakhir. Contoh:
/ DAN / 3 720
- Untuk node kanan, cabang yang masuk harus di kiri atas jika node adalah angka satu digit, atau di atas angka pertama. Contoh:
\ AND \ 7 243
- Untuk cabang kiri yang keluar, cabang harus mulai satu ruang di sebelah kiri nomor. Contoh:
275 / 11
- Untuk cabang kanan keluar, cabang harus mulai satu ruang di sebelah kanan nomor. Contoh:
275 \ 25
- Setiap dua node pada tingkat pohon yang sama harus memiliki minimal dua ruang di antara mereka. Pada saat yang sama, setiap dua sub pohon pada tingkat pohon yang sama harus memiliki ruang sesedikit mungkin di antara mereka.
Pohon ini tidak berfungsi karena sub pohon ** ** terlalu dekat. 504 / \ / \ / \ / \ 21 24 / \. / \ / \. / \ 3 7. 4 6 . / \ / \ .2 2 2 3 Sementara pohon ini memang memiliki ruang yang cukup di antara cabang-cabangnya. 504 / \ / \ / \ / \ / \ 21 ... 24 / \ ... / \ / \ ... / \ 3 7 ... 4 6 ... / \ / \ ... 2 2 2 3
- Jika ada dua sub pohon yang terlalu berdekatan pada pohon, mereka dapat dipisahkan dengan menambahkan satu baris cabang
/\
ke pohon di atas orang tua.
441 / \ Baris terakhir belum diisi dan kami sudah kehabisan ruang. 21 21 / \ / \ Tambahkan baris cabang lainnya 441 / \ Hampir, tetapi 7 dan 3 terlalu berdekatan. / \ Satu baris lagi harus melakukannya. 21 21 / \ / \ 3 7 3 7 Tambahkan baris cabang lainnya 441 / \ Dan kita sudah selesai. / \ / \ 21 21 / \ / \ 3 7 3 7
Contohnya
Sebagai contoh lengkap, pohon pembagi 24 akan terlihat seperti ini:
24
/ \
/ \
4 6
/ \ / \
2 2 2 3
4 dan 6 adalah pasangan pembagi paling dekat dengan akar kuadrat dari 24. 4 ada di sebelah kiri, karena lebih kecil. Pada baris berikutnya, angka 2 di sebelah kiri 3, karena lebih kecil.
Pohon pembagi untuk 63 akan terlihat seperti:
63 and NOT like this 63
/ \ / \
7 9 3 21
/ \ / \
3 3 7 3
Pada pohon yang salah, 3 dan 21 bukan pasangan pembagi yang paling dekat dengan akar kuadrat dari 63, dan 3 dan 7 tidak diurutkan dengan benar. Namun, penempatan cabang pada 21 benar.
Untuk 42, Anda harus memiliki:
42 and NOT 42
/ \ / \
6 7 21 2
/ \ / \
2 3 3 7
Mari kita lihat 720. Perhatikan bahwa kita membutuhkan lima tingkat cabang dari 720
sehingga sub pohon 24
dan 30
spasi benar. Juga, perhatikan bahwa 24
dan 30
memiliki dua tingkat cabang karena 4
dan 6
memiliki simpul anak yang perlu spasi yang benar dan simpul anak 30
perlu berada pada tingkat yang sama dengan simpul anak-anak 24
.
720
/ \
/ \
/ \
/ \
/ \
24 30
/ \ / \
/ \ / \
4 6 5 6
/ \ / \ / \
2 2 2 3 2 3
Tantangan
- Tugas Anda adalah untuk membangun pohon pembagi yang ditata secara estetika dan ditempatkan dengan benar untuk input
n
, di manan
bilangan bulat positif lebih besar dari 1. - Output Anda mungkin berisi spasi awal dan akhir dan baris baru awal dan akhir, tetapi sebaliknya harus sesuai dengan aturan spasi yang diberikan di atas.
- Output Anda diperbolehkan menjadi: seni teks, gambar (format lain yang akan ditambahkan, jika perlu).
- Untuk gambar, pastikan simpul pohon Anda memiliki jarak yang baik, dan simpul pada ketinggian yang sama di pohon berada pada ketinggian yang sama pada gambar.
- Ini kode golf. Jumlah byte terkecil (atau setara) menang.
Penghargaan kepada Stewie Griffin karena memikirkan ide ini, dan banyak terima kasih kepada Peter Taylor, Martin Ender, Mego, dan Eyss Iʀᴋ atas bantuan mereka dalam menulis ulang spesifikasi. Seperti biasa, setiap saran atau koreksi sangat dihargai. Semoga berhasil dan bermain golf dengan baik!
Lebih banyak kasus uji:
2
4
/ \
2 2
20
/ \
4 5
/ \
2 2
323
/ \
17 19
362880
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
576 630
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
24 24 21 30
/ \ / \ / \ / \
/ \ / \ / \ / \
4 6 4 6 3 7 5 6
/ \ / \ / \ / \ / \
2 2 2 3 2 2 2 3 2 3
1286250
/ \
/ \
/ \
/ \
/ \
1050 1225
/ \ / \
/ \ / \
/ \ / \
30 35 35 35
/ \ / \ / \ / \
5 6 5 7 5 7 5 7
/ \
2 3
sumber
Jawaban:
Python 2 ,
711651575559554547539540530522 byteSetelah empat bulan mencoba menulis jawaban ini, berlari ke dinding, meninggalkannya selama seminggu, bilas, ulangi, saya akhirnya menyelesaikan jawaban seni ASCII yang tepat untuk tantangan ini. Yang tersisa hanyalah bermain golf, jadi, saran bermain golf sangat disambut. Cobalah online!
Golf: -60 byte dari penggantian nama beberapa fungsi yang sering digunakan dan mengubah bagaimana hasilnya dikembalikan. -73 byte dari mengubah bagaimana ketinggian subtree diperiksa, bagaimana variabel spasi dihitung, dan bagaimana hasilnya dikembalikan. -3 byte dari
isdigit()
penggantian FlipTack . Golf -16 byteisdigit()
penggantian yang lebih jauh dan mengganti "" denganE
. -5 byte dari perbaikan kecil dan berubah dari Python 3 ke Python 2. -7 byte dari memodifikasi bagaimana hasilnya dikembalikan. -8 byte dari perubahan kecil menjadi bagaimanaA
didefinisikan,mengubah cara, menghapusT
didefinisikan, dan menambahkanW
, menggunakan hipotesis bahwa setiap subtree dengan setidaknya satu cabang lebih panjang dari mitranya, secara keseluruhan harus lebih panjang dari mitranyaQ
sama sekali, dan mengedit bagaimana hasilnya dikembalikan. -10 byte dari menggunakanA<10
bukanL(S(A))<2
untukA
danB
. -8 byte dari mengubah defaultH
menjadi[0]
karena kode menghindari masalah argumen default yang bisa berubah dengan tidak pernah bermutasiH
, mengubah caraq
didefinisikan dengan menggunakan(B>9)
alih-alih1-(B<10)
, menghapusp
sama sekali, dan membuatF
sebagai penggantip+q-M
.Perbaikan bug: Hipotesis salah, berlawanan dengan contoh di
11**9 = 2357947691
. +1 bytePenjelasan
Seluruh fungsi dapat diringkas menjadi sekitar empat langkah:
n
,A
danB
.A
danB
, gambar sesuai kebutuhan.Saya akan melewati setiap langkah secara berurutan.
Langkah 1. Ini adalah langkah termudah, terus terang. Periksa setiap angka
z
antara 1 dan akar kuadrat untuk dapat dibagin
dan ambil yang terbesarz
dann//z
yang cocok. Kembalikan hanyastr(n)
jikan
prima (salah satuA==1
atauB==n
)Langkah 2. Gambarlah subpohon
A
danB
dan dapatkan jumlah/\
cabang antar simpul dalam subpohon. Untuk melakukan ini, kita mendapatkan indeks dari setiap langkah yang memiliki angka di dalamnya, dapatkan perbedaan pertama dari indeks, dan kurangi 1 lagi. Setelah kami memiliki ketinggian, kami membandingkannya untuk mendapatkan yang terbesar, dan menggambar ulang subtree dengan ketinggian baru.Saya memiliki kecurigaan bahwa subtree yang lebih tinggi secara keseluruhan selalu memiliki cabang selama atau sama dengan cabang pada subtree yang lebih pendek, dan saya dapat menggunakannya untuk memasukkan kode, tetapi saya belum memiliki bukti mengenai hal ini.Contoh balasan dalam11**9 = 2357947691
.Langkah 3. Langkah ini adalah waktu yang dibutuhkan berbulan-bulan untuk menulis. Langkah 2 membutuhkan beberapa hari untuk menulis dan men-debug, tetapi menemukan formula yang tepat untuk penspasian membutuhkan waktu lama. Saya akan melihat apakah saya bisa menyingkat apa yang saya temukan menjadi beberapa paragraf. Perhatikan bahwa beberapa kode dalam penjelasan ini sejak itu telah dikeluarkan dari kode asli.
Pertama,
p
,q
,h
,P
,Q
,s
danM
.p
adalah jumlah karakter dari ujung cabang kiri/
ke ujung kanan subtree kiri.q
adalah jumlah karakter dari ujung kiri subtree kanan ke ujung cabang kanan/
.h
adalah jumlah cabang antara root dan sub pohon.P
danQ
hanyalah kebalikan darip
danq
dan berguna untuk menempatkan ruang di sekitar/\
cabang hingga ke akarn
.s
adalah jumlah spasi yang ditambahkan antara dua subpohon.M
paling sederhana; itu panjangnyan
. Letakkan secara grafis:Rumus untuk menentukan
p
adalah inip = len(x[0]) - x[0].rindex(str(A)[-1]) - (A<10)
:, panjang, minus indeks nol karakter terakhir dalam A, minus koreksi untuk satu digitA
s.Rumus untuk menentukan
q
adalah iniq = y[0].index(str(B)[0]) + (B>9)
:, indeks karakter pertama dalam B, ditambah koreksi untuk pengindeksan nol, minus koreksi untuk satu digitB
s (digabungkan menjadi satu koreksi untuk beberapa digitB
s).Rumus untuk menentukan
h
apakah ini:h = H[0] or (p+q+M%2+2-M)//2 or 1
. Entah kita ambil dari standarH
yang berarti kita menggambar ulang pohon, kita gunakan(from_the_left + from_the_right + parity_space + 2 - len(root)) // 2)
, atau kita menggunakan jumlah minimum tingkat cabang, 1.Rumus untuk menentukan
s
apakah ini:s = 2*h+M-p-q
. Kami mengurangip
danq
dari jumlah spasi di antara cabang-cabang root yang terlebar2*h + M
.Langkah 4. Dan akhirnya kami menyatukan semuanya. Pertama kita membuat root,,
[" "*(P+h)+Z+" "*(Q+h)]
lalu kita masukkan cabang ke bawah ke sub pohon[" "*(P+J)+"/"+" "*(2*h+M-2*J-2)+"\\"+" "*(Q+J)for J in G(h)][::-1]
,, dan akhirnya kita menempatkan di bawah pohon yang ditempatkan dengan benar[(" "*(2*h+M-p-q)).join([(I<L(w)and w[I]or" "*L(w[0]))for w in(x,y)])for I in G(max(L(x),L(y)))]
,.Dan lagi! Kami memiliki pohon pembagi yang menyenangkan secara estetika!
Tidak melakukan pelanggaran:
sumber
isdigit
cek Anda'/'<x[i].strip()[0]<':'
?Mathematica,
9686817978 byteTerima kasih @MartinEnder untuk 2 byte.
Outputnya terlihat seperti ini:
Penjelasan
Buat daftar pembagi input. Temukan elemen yang paling dekat dengan akar kuadrat dari input. (
Max
untuk meratakan output)Temukan pembagi lainnya dengan membagi input dengan pembagi yang ditemukan di atas, terapkan input sebagai kepala hasil.
Ulangi proses ini.
Jika inputnya prima, jangan lakukan apa pun.
Memformat output.
Sunting: Versi yang lebih estetis (258 byte)
Outputnya terlihat seperti ini:
sumber
Sqrt@#
->#^.5
(tentu saja Anda tidak dapat menggunakan notasi infiks untukNearest
tetapi kemudian Anda dapat menggunakanMax@
).Arang , 302 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Karena versi verbose sangat verbose, ia adalah transliterasi JavaScript dari algoritma utama:
sumber