Diberikan bilangan bulat positif n > 2
. Kami mengonversinya menjadi array sebagai berikut:
- Jika sama dengan
2
mengembalikan array kosong - Jika tidak, buat array semua
n
faktor utama yang diurutkan naik, lalu setiap elemen ganti dengan indeksnya dalam urutan bilangan prima dan akhirnya konversi setiap elemen menjadi array
Misalnya, mari kita konversi angka 46
menjadi array. Pertama, konversikan ke berbagai faktor utamanya:
[2, 23]
Jumlah 23
ini 9
prime th, jadi ganti 2
dengan array kosong dan 23
dengan [9]
. Array sekarang menjadi:
[[], [9]]
Faktor utama 9
adalah 3
dan 3
, jadi:
[[], [3, 3]]
Lakukan hal yang sama untuk keduanya 3
:
[[], [[2], [2]]]
Dan akhirnya:
[[], [[[]], [[]]]]
Sekarang, untuk menyandikannya, kita cukup mengganti masing-masing braket terbuka dengan 1
dan setiap braket penutup 0
, lalu hapus semua nol akhir dan jatuhkan satu 1
dari ujungnya. Ini adalah nomor biner kami. Menggunakan contoh di atas:
[ ] [ [ [ ] ] [ [ ] ] ]
| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V
1 0 1 1 1 0 0 1 1 0 0 0
Sekarang cukup masukkan tiga nol terakhir dan terakhir 1
. Angka menjadi 10111001
yang 185
dalam desimal. Itu adalah output yang diharapkan. Perhatikan bahwa dalam kurung konversi array ke biner dari array utama tidak termasuk.
Memasukkan
Bilangan bulat positif n
lebih besar dari 2
.
Keluaran
Integer yang dikodekan n
.
Aturan dan format IO
- Aturan standar berlaku.
- Input dapat berupa string atau angka (tetapi jika string harus dalam basis 10).
- Output dapat berupa string atau angka (tetapi jika string harus dalam basis 10).
- Ini adalah kode-golf , jawaban terpendek dalam byte menang!
Uji kasus
Lebih banyak kasus uji berdasarkan permintaan.
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478
2
karena kiriman tidak diperlukan untuk menanganinya.Jawaban:
Sekam ,
3531302926252422201915 byte-7 byte terima kasih kepada @Zgarb!
Menyimpan tambahan 4 byte, secara tidak langsung, berkat Zgarb
Cobalah online!
Penjelasan
sumber
φ
, fixpoint lambda!`:0:1
bisa`Jḋ2
.Jelly ,
22 2019 byte-1 berkat Erik the Outgolfer (angka nol ekor dari kedua sisi
t
,, bukan dari kananœr
)Tautan monadik yang mengambil bilangan bulat lebih besar dari 2 dan mengembalikan bilangan bulat lebih besar dari 0 (2 akan mengembalikan 0 sesuai dengan spesifikasi asli juga).
Cobalah online!
Bagaimana?
Ini hampir persis mereplikasi deskripsi yang diberikan, hanya dengan beberapa manipulasi ordinal untuk pembuatan array biner ...
sumber
Python 2 ,
212177 byteCobalah online!
Kurangnya prime builtin benar-benar menyakiti jumlah byte, dan itu kali keluar pada TIO dengan bilangan prima yang lebih besar. Penggunaan XNOR 's cek primality.
Python 2 + gmpy2 , 175 byte
Cobalah online!
Versi ini tidak berhenti pada kasus uji yang lebih besar (yaitu 10.000 - 1.0008).
sumber
Mathematica,
125119 byteMenggunakan pendekatan yang sedikit berbeda; mengkonversi indeks utama menjadi
{1, index, 0}
, dan 2 menjadi{1, 0}
.Cobalah di Wolfram Sandbox
Pemakaian:
sumber
Jelly , 35 byte
Cobalah online!
sumber
J,
747366 byteCobalah online!
Ini adalah kekacauan nyata yang tentunya membutuhkan golf lebih lanjut (misalnya, penghapusan definisi fungsi eksplisit). Saya pikir tinju yang telah saya lakukan adalah terutama apa yang memunculkan bytecount karena saya benar-benar tidak tahu apa yang saya lakukan di sana (sudah banyak trial and error). Juga, saya cukup yakin bahwa ada beberapa built-in yang saya lupakan (misalnya saya merasa
_2,~_1,
mungkin memiliki built-in).Penjelasan (ungolfed)
Pembukaan
Duduk santai, karena ini tidak akan menjadi penjelasan singkat. Ironisnya, bahasa singkat telah dipasangkan dengan orang yang bertele-tele.
Saya akan membagi ini menjadi beberapa fungsi
encode
mengkodekan integer menggunakan _1 dan _2 alih-alih [dan]convert
mengonversi daftar _1 dan _2 menjadi daftar 1 dan 0drop
menjatuhkan 1 terakhir dan membuntuti noldecode
mengkonversi dari daftar biner ke angkaSaya akan berjalan melalui panggilan sampel untuk 46, yang dinyatakan dalam format ungolfed selesai
Menyandi
Ada banyak hal untuk dijelaskan di sini.
Perhatikan bahwa definisi fungsi eksplisit
3 : '[function]'
mengevaluasi fungsi seolah-olah berada pada REPL dengan argumen yang tepat menggantikan setiap instance dariy
(ini berarti bahwa saya dapat menghindari harus menggunakan caps ([:
), atops (@
), dan ats (@:
) dengan biaya beberapa byte).Inilah yang terlihat untuk setiap iterasi berturut-turut pada input 46
Fungsi ini menggunakan merugikan (
::
) untuk bersarang nilai dalam "tanda kurung" (tanda kurung yang digunakan di sini adalah -1 dan -2). Pada dasarnya, setiap kali kami memfaktisasi dan mengonversikan ke indeks bilangan prima, _1 diawali dan _2 ditambahkan, yang bertindak sebagai tanda kurung. Ketika fungsi dipanggil pada elemen-elemen itu, ia hanya mengembalikannya apa adanya karenaq:
akan kesalahan saat mencoba memfaktorkan bilangan negatif. Ini juga beruntung bahwaq:
tidak tidak kesalahan berusaha untuk pd 1 dan bukannya mengembalikan array kosong (seperti yang diinginkan).Mengubah
Konversi jauh lebih sederhana. Itu hanya menghapus semua tinju, serta elemen pertama, dan kemudian mengubah semuanya menjadi 1 dan 0 (hanya dengan menambahkan 2)
Penurunan
Ini membalikkan daftar, menemukan yang pertama dan kemudian menjatuhkan semua nilai hingga yang itu, lalu membalikkan daftar lagi.
Membaca sandi
Decode adalah fungsi
#.
bawaan yang mengambil daftar 1s dan 0s dan mengubahnya menjadi angka biner.sumber
Retina ,
244227225 byteCobalah online!
Ini adalah pendekatan lurus ke depan mengikuti algoritma yang ditunjukkan dalam pertanyaan. Generasi indeks utama adalah kompleksitas eksponensial sehingga akan habis untuk input yang lebih besar
Penjelasan:
sumber
Haskell ,
162160155 byteCobalah online!
Penjelasan:
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
mendefinisikan daftar tak terbatas tupel bilangan prima dan indeks mereka:[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...]
.Fungsi
(%)
mengambil daftar inir
dan angkan
dan mengubah angka menjadi representasi array faktor terbalik. Ini dilakukan dengan melangkah majur
sampai kita menemukan prime yang membelahn
. Kami kemudian rekursif menentukan representasi dari indeks utama ini dan membungkusnya dengan0
dan1
dan tambahkan representasin
dibagi dengan perdana itu.Sebab
n=46
, ini menghasilkan daftar[0,0,0,1,1,0,0,1,1,1,0,1]
yang kemudian nol depan (snd.span(<1)
) dan berikutnya1
(tail
) dijatuhkan. Setelah itu daftar dikonversi ke angka desimal oleh mengalikan elemen-bijaksana dengan daftar kekuatan dua dan menyimpulkan daftar yang dihasilkan:sum.zipWith((*).(2^))[0..]
.sumber
JavaScript, 289 byte
Bytes adalah jumlah dari kode JavaScript tanpa linebreak setelah koma (yang dimasukkan hanya untuk pemformatan dan keterbacaan yang lebih baik) (256 byte) dan karakter tambahan untuk saklar baris perintah, yang diperlukan saat menggunakan Chrome (33 byte).
Dan versi yang lebih panjang, lebih baik dibaca:
Beberapa penjelasan singkat:
f
adalah algoritma faktorisasi ekor-rekursif murni fungsional.c
menghitung di mana tempatr
bilangan primap
terjadi dalam urutan bilangan prima dan mengembalikan baik[]
(jikap=2
danr=1
) atau membuat faktor dan proses lebih lanjutr
dengan cara rekursi.h
adalah fungsi pembantu kecil yang sayangnya diperlukan sebagaimap
memanggil fungsi yang disediakan dengannumberOfCurrentElement
sebagaiwholeArray
argumen kedua dan ketiga, sehingga mengesampingkan nilai default yang disediakanc
jika kita akan meneruskan fungsi ini secara langsung (butuh beberapa waktu untuk mendapatkan setelah jebakan ini; menggantih
dengan definisinya akan lebih lama beberapa byte).s
mentransformasikan array yang dihasilkan menjadi string. Kami menggunakanblank
alih-alih0
agar kami dapat menggunakannyatrim()
dio
.o
adalah fungsi yang dipanggil dengan nilai inputi
yang mengembalikan output. Ini menghasilkan representasi string biner yang diperlukan oleh spesifikasi dan mengubahnya menjadi angka (desimal).Sunting: Chrome harus dimulai dengan
chrome --js-flags="--harmony-tailcalls"
untuk mengaktifkan optimasi rekursi ekor (lihat https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html ). Ini juga mengharuskan menggunakan mode ketat.Tes berikut menunjukkan bahwa perhitungannya agak lambat untuk beberapa nilai (yang terpanjang lebih dari enam detik untuk
10007
komputer saya). Menariknya, tanpa optimasi rekursi ekor perhitungannya jauh lebih cepat (sekitar faktor 5) ketika tidak ada stack overflow.sumber
tinylisp , 209 byte
Baris terakhir adalah fungsi tanpa nama yang menghitung pengkodean yang ditentukan. Cobalah online!
Versi pra-golf
Ini adalah kode yang saya miliki sebelum mulai bermain golf:
sumber
05AB1E , 18 byte
Cobalah online!
Penjelasan:
sumber