Tantangan ini menimbulkan algoritma untuk pengkodean integer n
sebagai integer lain r
. Berikut ini adalah penjelasan singkat tentang algoritma itu, menggunakan n=60
sebagai contoh.
Algoritma asli
Pertama, kami menyandikan nomor tersebut sebagai string tanda kurung.
- Jika
n = 1
, kembalikan string kosong. - Jika tidak, kami mengambil
n
penguraian utama yang diurutkan naik dan mengganti setiap elemen dengan indeks prima (1-diindeks) dalam tanda kurung.60 = 2*2*3*5 => [1][1][2][3]
- Lakukan ini secara rekursif sampai semua yang kita miliki adalah tanda kurung.
[1][1][2][3] => [][][[1]][[2]] => [][][[]][[[1]]] => [][][[]][[[]]]
- Jika
Setelah kami memiliki serangkaian tanda kurung, kami mengubahnya menjadi bilangan bulat dengan proses berikut.
- Konversikan setiap braket pembuka ke a
1
dan setiap braket penutup menjadi a0
.[][][[]][[[]]] => 10101100111000
- Hapus semua trailing
0
dan final1
.10101100111000 => 1010110011
- Konversi string akhir
0
s dan1
s dari biner ke integer.1010110011 => 691
- Konversikan setiap braket pembuka ke a
Decoding encoding ini
Properti yang menarik dari algoritma ini adalah tidak bersifat surjektif. Tidak setiap bilangan bulat dapat menjadi hasil pengkodean ini.
- Pertama, representasi biner dari hasilnya
r
, harusbalance-able
dalam jumlah0
s tidak boleh melebihi jumlah1
s. Kasus uji falsey pendek adalah4
, yang100
dalam biner. - Kedua, tanda kurung dalam representasi biner harus
sorted ascending
ketika akhir1
dan trailing0
ditambahkan sekali lagi. Kasus uji falsey pendek adalah12 <= 1100 <= 110010 <= (())()
.
Namun, hanya menentukan apakah angka dapat didekodekan dengan cara ini akan membuat tantangan singkat. Sebagai gantinya, tantangannya adalah berulang kali mendekode input yang diberikan sampai salah satu angka yang tidak dapat didekodekan atau siklus tercapai, dan mengembalikan urutan angka yang dihasilkan .
Tantangan
- Diberi nomor
1 <= r <= 2**20 = 1048576
, kembalikan urutan angka yang secarar
berturut - turut diterjemahkan , dimulai denganr
dirinya sendiri dan diakhiri dengan angka yang tidak dapat didekode atau siklus. - Jika nomor yang tidak dapat didekodekan diberikan sebagai input, seperti
4
atau12
, akan mengembalikan daftar yang hanya berisi input. - Urutan yang berakhir dalam suatu siklus harus diindikasikan dengan beberapa cara, baik dengan menambahkan atau menambahkan penanda (pilih bilangan bulat, string, daftar, dll. Apa pun sebagai penanda, tetapi tetap konsisten), atau dengan mengulangi siklus dalam beberapa cara (mengulangi elemen pertama, mengulangi seluruh siklus, mengulangi tanpa batas, dll.).
- Jika ada urutan yang tidak terbatas (dengan meningkatkan selamanya, misalnya), anggap itu perilaku yang tidak terdefinisi.
- Ini golf kode. Jumlah byte terkecil menang.
Contoh decoding yang berhasil
1 -> 1 -> 1100 -> [[]] -> [2] -> 3
-> 3 -> 11 -> 111000 -> [[[]]] -> [[2]] -> [3] -> 5
-> 5 -> 101 -> 101100 -> [][[]] -> 2*[2] -> 2*3 -> 6
-> 6 -> 110 -> 110100 -> [[][]] -> [2*2] -> [4] -> 7
-> 7 -> 111 -> 11110000 -> [[[[]]]] -> [[[2]]] -> [[3]] -> [5] -> 11
-> 11 -> 1011 -> 10111000 -> [][[[]]] -> 2*[[2]] -> 2*[3] -> 2*5 -> 10
-> 10 -> 1010 -> 101010 -> [][][] -> 2*2*2 -> 8
-> 8 -> 1000 ERROR: Unbalanced string
Uji kasus
4 -> [4]
12 -> [12]
1 -> [1, 3, 5, 6, 7, 11, 10, 8]
2 -> [2, 4]
13 -> [13, 13] # cycle is repeated once
23 -> [23, 22, 14, 17]
51 -> [51, 15, 31, 127, 5381]
691 -> [691, 60]
126 -> [126, 1787, 90907]
1019 -> [1019, 506683, 359087867, 560390368728]
Saran dan umpan balik untuk tantangan ini dipersilahkan. Semoga berhasil dan bermain golf dengan baik!
sumber
1
memberi3
?1
- (menambahkan1
dan mengekor nol) ->1100
->[[]]
->[[1]]
->[2]
->3
6
->110
->110100
yang tidak valid, bukan? Jadi haruskah input1
memberi[1,3,5,6]
?7
->111
->11110000
->[[[[]]]]
-> 4th prime = 7? Mungkin saya tidak mengerti algoritmeJawaban:
Python 3 ,
379358339337327310304 byteDugaan: Apakah
13
hanya angka yang akan mengarah pada siklus? (Tidak ada pengecualian yang lebih kecil dari 10 6 ).Memperbaiki bug dan -7 byte berkat Sherlock9 .
-3 byte terima kasih kepada Jonathan Frech .
-16 bytes terima kasih kepada ovs .
-6 byte terima kasih kepada Tn . Xcoder .
Jika ada siklus, itu akan mengulangi seluruh siklus.
Cobalah online!
Penjelasan:
sumber
Pyth, 62 byte
Suite uji
Menunjukkan siklus dengan mengulangi angka terakhir.
sumber