Anda mungkin mengenal ahli matematika von Koch dengan kepingan saljunya yang terkenal. Namun ia memiliki masalah ilmu komputer yang lebih menarik. Memang, mari kita lihat dugaan ini:
Diberikan pohon dengan n
simpul (dengan demikian n-1
ujung). Temukan cara untuk menghitung node dari 1
ke n
dan, sesuai, tepi dari 1
ke n-1
cara seperti itu, bahwa untuk setiap tepi k
perbedaan angka simpul yang sama dengan k
. Dugaannya adalah bahwa ini selalu mungkin.
Berikut ini contoh untuk membuatnya sangat jelas:
TUGAS ANDA
Kode Anda akan mengambil sebagai input pohon, Anda dapat mengambil format yang Anda inginkan tetapi untuk kasus uji saya akan menyediakan pohon dengan busur mereka dan daftar node mereka.
Misalnya ini adalah input untuk pohon dalam gambar:
[a,b,c,d,e,f,g]
d -> a
a -> b
a -> g
b -> c
b -> e
e -> f
Kode Anda harus mengembalikan pohon dengan nomor node dan tepi. Anda dapat mengembalikan output yang lebih grafis tetapi saya akan memberikan output semacam ini untuk kasus uji:
[a7,b3,c6,d1,e5,f4,g2]
d -> a 6
a -> b 4
a -> g 5
b -> c 3
b -> e 2
e -> f 1
KASUS UJI
[a,b,c,d,e,f,g] [a7,b3,c6,d1,e5,f4,g2]
d -> a d -> a 6
a -> b a -> b 4
a -> g => a -> g 5
b -> c b -> c 3
b -> e b -> e 2
e -> f e -> f 1
[a,b,c,d] [a4,b1,c3,d2]
a -> b a -> b 3
b -> c => b -> c 2
b -> d b -> d 1
[a,b,c,d,e] [a2,b3,c1,d4,e5]
a -> b a -> b 1
b -> c b -> c 2
c -> d => c -> d 3
c -> e c -> e 4
Ini adalah kode-golf ini jawaban terpendek dalam byte yang menang!
Catatan: Ini lebih kuat dari dugaan Ringel-Kotzig , yang menyatakan setiap pohon memiliki label anggun. Karena dalam dugaan Koch tidak mungkin untuk melewatkan bilangan bulat untuk pelabelan yang bertentangan dengan pelabelan anggun dalam dugaan Ringel-Kotzig. Pelabelan yang anggun telah ditanyakan sebelumnya di sini .
sumber
Jawaban:
Jelly , 30 byte
Cobalah online! (Gunakan
GṄ³çG
sebagai footer untuk membuat output lebih cantik.)Input mirip dengan contoh, misalnya
abcdef
dan[d,a],[a,b],[a,g],[b,c],[b,e],[e,f]
Keluarkan daftar misalnya
a,b,c,d,e,f
dalam urutan.Catatan: Program saya menghasilkan nilai yang berbeda dari kasus uji karena ada beberapa kemungkinan yang semuanya valid.
Penjelasan
Hemat 1 byte dengan menunjukkan semua solusi yang mungkin:
Cobalah online! (Gunakan
GṄ³çG⁷³G
sebagai footer untuk membuat output lebih cantik)Gunakan konverter untuk menyalin-tempel test case ke dalam daftar input.
sumber
Ruby, 108 byte
fungsi lamba, menerima larik array 2-elemen yang mengandung tepi (di mana setiap tepi dinyatakan sebagai pasangan angka yang sesuai dengan catatan yang relevan.)
Tidak digabungkan dalam program uji
Keluaran
output adalah array 2 elemen, mengandung:
penomoran simpul baru
penomoran tepi.
Misalnya tepi pertama dari contoh pertama
[4,1]
adalah antara node 6 dan 1 di bawah penomoran simpul baru dan karenanya edge 6-1 = 5.Sebenarnya ada beberapa soluton untuk setiap test case. yang
return
berhenti fungsi sekali yang pertama ditemukan.sumber