Buku Randall Munroe "xkcd, volume 0" menggunakan sistem angka yang agak aneh untuk nomor halaman. Beberapa nomor halaman pertama adalah
1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...
Ini agak mirip ternary, tetapi perhatikan bahwa ia melompat dari 20
lurus ke 100
, dari 120
ke 200
dan dari 200
ke 1000
. Salah satu cara untuk mendefinisikan urutan ini adalah dengan mengatakan bahwa ia menyebutkan semua nomor terner yang berisi paling banyak satu 2
dan tidak ada 1
setelah itu 2
. Anda dapat menemukan ini di OEIS di entri A169683 . Sistem angka ini dikenal sebagai biner miring .
Tugas Anda adalah menemukan representasi bilangan bulat positif yang diberikan N
dalam sistem angka ini.
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Output dapat berupa string, angka dengan representasi desimal sama dengan representasi biner miring, atau daftar digit (sebagai bilangan bulat atau karakter / string). Anda tidak boleh mengembalikan angka nol di depan.
Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.
Fakta menyenangkan: Sebenarnya ada beberapa manfaat untuk sistem angka ini. Saat menambah angka, Anda akan selalu mengubah paling banyak dua digit yang berdekatan - Anda tidak akan perlu membawa perubahan melalui seluruh angka. Dengan representasi yang tepat yang memungkinkan penambahan di O (1).
Uji Kasus
1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001
1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102
Saya akan memberikan hadiah kepada jawaban terpendek yang dapat memecahkan kasus uji terakhir (dan input lain yang sama besarnya, jadi jangan berpikir tentang hardcoding) dalam waktu kurang dari satu detik.
Papan peringkat
Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.
Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:
# Language Name, N bytes
di mana N
ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Misalnya:
# Ruby, <s>104</s> <s>101</s> 96 bytes
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
sumber
59->60
dan109->110
, dengan tambahan 0.Jawaban:
Pyth, 17 byte
Ini agak lambat -
O(output^log_2(3))
. Itu eksponensial dalam panjang input, tetapi tidak eksponensial ganda, seperti beberapa jawaban di halaman. Beberapa ide diambil dari jawaban @ Dennis, di sini .Demonstrasi.
Itu memanfaatkan
.f
fungsi "loop sampai n kecocokan telah ditemukan" Pyth.sumber
CJam,
2423222119 byteIni adalah pendekatan O (log n) , di mana n adalah input, yang menyelesaikan kasus uji terakhir secara instan. Ini mengkonversi n langsung ke miring biner, menggunakan pembagian modular dengan nilai-nilai digit 1 .
Kode ini selesai dengan kesalahan yang masuk ke STDERR dengan Java interpreter, yang diizinkan sesuai dengan konsensus tentang Meta .
Jika Anda mencoba kode ini dalam juru bahasa CJam , abaikan saja semuanya kecuali baris keluaran terakhir.
Kesalahan dapat dihilangkan, dengan biaya 2 byte, dengan menambahkan
2>
keW%
.Terima kasih kepada @ MartinBüttner untuk bermain golf satu byte.
Latar Belakang
Representasi kemiringan miring a k ... a 0 sesuai dengan bilangan bulat n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .
Karena keduanya (2 k -1) + ... + (2 1 -1) = 2 k + 1 - (k + 2) dan (2 k -1) + ... + 2 (2 j -1) = 2 k + 1 - (2 j + 1 - 2 j + k + 1) kurang dari 2 k + 1 -1 , nilai-nilai suatu k untuk sebuah 0 dapat dipulihkan dengan pembagian modular berturut-turut oleh 2 k + 1 -1 , 2 k -1 , dll.
Untuk memulai, kita harus menemukan nilai 2 k + 1 -1 terlebih dahulu. Karena n paling banyak 2 (2 k + 1 -1) , integer n + 1 harus lebih kecil dari 2 k + 2 .
Dengan demikian, mengambil bagian integer dari logaritma biner dari n + 1 menghasilkan k + 1 .
Akhirnya, kami mengamati bahwa integer n + 1 memiliki ⌊log 2 (n + 1) ⌋ digit di basis 2.
Bagaimana itu bekerja
Dalam dua iterasi terakhir, kami melakukan pembagian modular dengan 1 dan 0 . Yang pertama mendorong 0 yang tidak diinginkan pada stack. Upaya terakhir untuk mengeksekusi
0 0 md
, yang mengeluarkan 0 s yang tidak diinginkan dari stack, keluar dengan segera alih-alih mendorong apa pun dan membuang stack ke STDOUT.sumber
Python 2, 67 byte
Tampaknya bekerja untuk test case yang diberikan. Jika saya sudah benar, ini seharusnya tentang
O(place values set in output)
, jadi itu kasus terakhir dengan mudah.Sebut seperti
f(100)
. Mengembalikan representasi desimal sama dengan biner miring.Python 3, 65 byte
Agak kurang efisien tetapi masih logaritmik, jadi kasing terakhir hampir instan.
Sebut seperti
g(100)
. Mengembalikan daftar digit.sumber
2and
kompilasi dalam 3? Saya berada di 2 dan2and2
melempar kesalahan sintaks2and2
tidak akan berfungsi karena akan diuraikan sebagai2 and2
- coba2and 2
, yang akan berfungsi jika versi Python Anda cukup baru (diuji dengan Python 2.7.10)CJam,
222120 byteIni adalah pendekatan O (e n n) , di mana n adalah input. Ini daftar pertama ⌊e n ⌋ bilangan bulat non-negatif dalam basis 3, menghilangkan orang-orang yang memiliki 2 s atau 1 s setelah pertama 2 (jika ada) dan memilih n + 1 th .
Cobalah online di juru bahasa CJam .
Bagaimana itu bekerja
sumber
Pyth, 20 byte
Berjalan di O (log (input ())), jauh di bawah satu detik untuk kasus uji akhir. Berbasis di sekitar run sampai loop kesalahan. Tidak ada baris baru.
Demonstrasi.
Penjelasan:
J diinisialisasi dengan nilai posisi digit miring biner terkecil yang lebih besar dari input. Kemudian, setiap kali melalui loop, kami melakukan hal berikut:
J
dariQ
dengan=%QJ
. Misalnya, jikaQ=10
danJ=7
,Q
menjadi3
, yang sesuai dengan biner miring yang berubah dari110
menjadi10
. Ini tidak berpengaruh pada iterasi pertama.J
nilai biner miring kemiringan berikutnya dengan=/J2
. Ini adalah pembagian lantai dengan 2, berubahJ=7
menjadiJ=3
, misalnya. Karena ini terjadi sebelum digit pertama adalah output,J
posisi satu digit lebih tinggi dari yang dibutuhkan./QJ
(efektif).p
, alih-alih pencetakan standar Pyth, untuk menghindari baris baru yang tertinggal.Loop ini akan mengulang sampai
J
menjadi nol, di mana titik kesalahan dibagi dengan nol akan dilemparkan, dan loop akan berakhir.sumber
ES6, 105 byte
Penggunaannya adalah:
f(1048576)
=> `" 10000000000000000001 "Uji argumen terakhir atas risiko Anda sendiri. Saya menyerah setelah 5 detik.
Dan cukup cetak dengan komentar!
sumber
f=
.f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s}
Math.pow(3,s.length+c)
dengan3**(s.length+c)
.Retina, 55 byte
Mengambil input di unary.
Setiap baris harus menuju ke file sendiri tetapi Anda dapat menjalankan kode sebagai satu file dengan
-s
bendera. Misalnya:Metode: Menjalankan penambahan pada jumlah input string kali mulai dari string
0
.Kami menggunakan aturan kenaikan berikut:
2
:^2 -> ^12
;02 -> 12
;12 -> 20
2
:0$ -> 1$
;1$ -> 2$
(Paling banyak ada satu
2
di string;^
dan$
menandai awal dan akhir string dalam aturan.)Informasi lebih lanjut tentang Retina.
sumber
Jawa,
154148Jawaban ini mengambil bentuk fungsi anonim tunggal yang mengambil argumen integer dan mengembalikan jawaban sebagai String. Di bawah ini adalah kelas lengkap untuk menguji solusi ini.
sumber
Bash + coreutils, 52
Ini kasar, jadi agak lambat untuk jumlah yang lebih besar.
Keluaran:
sumber
Java,
337335253246244 byteMetode yang mengambil dalam indeks sebagai
long
dan mengembalikan hasilnya sebagai stringMenggunakan a
long
untuk indeks sehingga secara teoritis dapat menangani test case terakhir, tetapi saya benar - benar tidak akan menyarankannya.sumber
if(j == 0)
pernyataan (empat byte). Anda tidak perlu mendeklarasikank
; Anda bisa menggunakanj
lagi (empat lagi). Anda dapat menggunakan inferensi tipe umum (di Jawa 7) dalam deklarasi Daftar Anda (new ArrayList<>();
) (4 lainnya)Haskell,
7372Terima kasih kepada @nimi untuk 1 byte!
Solusi ini tidak akan memenangkan hadiah apa pun, tes pasangan terakhir membutuhkan banyak waktu untuk berlari, tapi, saya pikir saya telah bermain golf dengan cukup baik.
Solusi ini adalah pendekatan yang agak naif yang menghitung angka biner miring
n
dengan menambah 0n
kali.sumber
CJam, 24 byte
Ini adalah pendekatan O (n log n) , di mana n adalah input. Ini dimulai dengan representasi biner miring 0 dan menambah bilangan bulat yang sesuai n kali.
Cobalah online di juru bahasa CJam .
Latar Belakang
Menambah angka dalam biner miring dapat dilakukan dengan mengikuti dua langkah mudah:
Ganti akhirnya 2 dengan 0 .
Jika 2 telah diganti, tambahkan digit ke kiri.
Jika tidak, tambahkan digit terakhir.
Bagaimana itu bekerja
sumber
VBA,
209147142 byteMatematika saya tidak efisien dan golf saya bisa menggunakan pekerjaan. Tapi ini upaya pertama saya di PoG dan saya pikir saya akan mencoba yang ini. Tapi semacam cara Brute Force.
Itu hanya menghitung dengan 1 kecuali digit terakhir adalah 2 lalu mundur 2 dan melompat ke depan 10. Ditambah 0 yang tertinggal.
Ini berhenti bekerja di 65534 karena VBA bersikeras memberi hasil dalam notasi ilmiah, tetapi logika harus bekerja dengan baik untuk angka yang lebih tinggi
Menantikan saran golf, VBA tidak terlalu ramah golf tetapi tidak sering diwakili, dan saya pikir itu bisa mengalahkan Jawa lama.
Sunting1: Terima kasih Manu karena membantu mencukur 62 byte
Sunting2: Ditukar
debug.print
untukmsgbox
sebagai output. Disimpan 5 bytesumber
Debug.Print (q)
. Anda juga dapat menghapus sebagian besar spasi putih (editor akan mengembalikannya, tetapi itu tidak perlu). Anda tidak perlu mendeklarasikank as Long
, cukup tulisk
. Ini akan menjadi variabel dari jenis Varian dan kode akan tetap berfungsi. Dengan tips ini Anda harus turun ke ~ 165 byte.InStr
, mereka adalah opsional.Trim()
tidak perlu, karena Anda tidak memiliki spasi putih. Diterapkan dengan benar, saya mendapatkan 147 byte .debug.print q
akan menjadi output Standar?msgbox q
lebih pendek tapi Sekali lagi sepertinya itu tidak cukup keluaran standar.Sheet1.cells(1,1)
sepertinya keluaran Khas tetapi mengasumsikan berjalan di excel. Saya hanya tidak begitu yakin tentang seberapa ketat kode-golf tentang hal-hal semacam ini.MsgBox
, jika seseorang mengeluh, Anda masih dapat mengubahnya kembali.Javascript ES6,
9986787672 karakterUji:
Terima kasih atas faktanya - ini adalah dasar dari solusi saya :)
sumber
Oktaf,
107, 101 byteSeharusnya O (log n) jika saya memperkirakan ini benar ...
Cukup cetak:
Saya agak terhalang mengatasi tantangan terakhir, karena Oktaf secara default memperlakukan semuanya sebagai angka floating point dan saya tidak memiliki presisi yang diperlukan untuk menghitung yang terakhir. Saya menyiasatinya dengan menghabiskan byte berharga untuk memaksa semuanya menjadi bilangan bulat yang tidak ditandatangani. Hasil yang terakhir terlalu besar untuk diperlakukan sebagai angka, jadi hasilnya adalah string.
Keluaran (Saya termasuk
1e18 - 1
untuk menunjukkan bahwa saya dapat melakukannya secara akurat, dan rangkaian keluaran terakhir menunjukkan berapa lama untuk menghitung nilai itu):sumber
T-SQL,
221189177 byteEDIT: Versi asli dari kode ini akan menghasilkan output yang tidak benar untuk beberapa angka, ini telah diperbaiki.
Dengan setiap kueri di sini, tambahkan saja angka untuk menghitung sebelum koma pertama.
Semua orang tahu bahwa T-SQL adalah bahasa golf terbaik. Ini adalah versi yang akan menghitung bahkan test case terakhir. Pada mesin saya mengujinya, itu berjalan di bawah satu detik, saya akan tertarik untuk melihat cara kerjanya untuk orang lain.
Dan ini dia lagi, tetapi bisa dibaca:
Jika saya hanya menggunakan int, ini bisa sedikit lebih pendek, keluar pada 157 byte:
Dan sekali lagi, lebih mudah dibaca:
sumber
@
adalah pengidentifikasi yang valid dalam sql dan Anda kemungkinan besar bisa lolos denganChar(8000)
yang masih lebih murah daripada nvarchar (maks). Anda juga dapat mengonversi kechar
alih-alihvarchar
, atau menggunakanstr
fungsi.@
, konyol saya. TheCHAR(8000)
saran cukup bagus, saya akan mencoba itu. Saya sepertinya selalu lupa tentang keberadaanSTR()
terima kasih untuk kepala.select @t=concat(@t,@/i)
yang seharusnya lebih kecil. Membutuhkan sql2012.CONCAT
, Saya pada 2008. Jadi saya tidak bisa mengujinya tanpa menggunakan biola SQL sekarang. Panggilan yang bagus.Kode Mesin Turing,
333293 byteSaya menggunakan penyandian seperti yang digunakan di sini .
Mesin ini menggunakan 9 status dan 11 warna.
Jika input biner diizinkan, ini dapat dikurangi menjadi hanya 4 warna, menghemat beberapa puluh byte dalam proses.
Jika tautan di atas tidak berfungsi (kadang-kadang itu berfungsi untuk saya, di lain waktu halaman tersebut menolak untuk memuat) Anda juga dapat menguji ini menggunakan implementasi java ini.
sumber
Perl, 66 byte
Nomor harus dimasukkan melalui STDIN.
sumber
(.?)
di$2
sejak(.*)
di$1
harus serakah dan mendapatkan karakter yang pertama. Tetapi jika itu dihapus kode tidak menghasilkan hasil yang benar lagi! Omong-omong, Anda tidak perlu final;
.$c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print
. Aku benar,(.?)
tidak pernah menangkap apa pun.$_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print
, yaitu 50 byte..*
di awal atau akhir dapat dioptimalkan jauh, jika Anda hanya menggantinya dengan teks asli. Juga tidak ada alasan untuk menambahkan 0 di akhir, karena selalu ada nol saja di aslinya$3
.Pyth, 19 byte
Kompleksitas logaritmik. Mudah selesai dalam jumlah waktu yang diperlukan. Output dalam bentuk daftar digit.
Demonstrasi .
sumber
Perl,
847067 byteTidak terlalu golf,Menjadi lebih baik tetapi bekerja dengan sangat cepat!Saran Dennis membuatnya turun menjadi 51 (50 byte + -p switch)
Itu harus disebut seperti di
perl -p skew_binary.pl num_list.txt
mananum_list.txt
berisi satu baris dengan nomor untuk dikodekan di atasnya.sumber
Mathematica, 65
Seharusnya cukup cepat, walaupun harus kuakui aku mengintip kiriman lain sebelum membuat ini.
Pemakaian:
Keluaran:
Mulai memberikan pesan kesalahan MaxExtraPrecision di suatu tempat di atas 10 ^ 228 (yang menghitung hasilnya dalam 0,03 detik pada mesin saya)
Setelah menghapus batas MaxExtraPrecision, itu akan menangani angka hingga sekitar 10 ^ 8000 dalam satu detik.
Memasukkan:
Keluaran:
sumber
C, 95 byte
Ini menerima integer dan buffer untuk mengembalikan digit. Hasilnya disimpan dalam
b
, diakhiri dengan nilai3
(yang tidak dapat terjadi dalam output). Kami tidak harus menangani input0
(seperti pertanyaan yang ditentukan hanya bilangan bulat positif), jadi tidak ada casing khusus untuk menghindari output kosong.Kode diperluas
Kami beroperasi dengan pengurangan berturut-turut, dimulai dengan digit paling signifikan. Satu-satunya komplikasi adalah kita menggunakan variabel
m
untuk menghindari pencetakan angka nol di depan. Perluasan alami untukunsigned long long
dibuat jika diinginkan, dengan biaya 10 byte.Program uji
Lewati angka yang akan dikonversi sebagai argumen perintah. Itu mengkonversi
int
buffer array ke string angka yang dapat dicetak. Runtime kurang dari satu milidetik untuk input1000000000000000000
.Hasil tes
sumber
auto a=~0ull
untuk sedikit keuntungan ...JavaScript (Node.js) , 40 byte
Cobalah online!
Solusi ini tidak berfungsi pada testcase terakhir. Itu hanya menyebabkan stack overflow di atasnya.
sumber
CoffeeScript,
9269 byteBerdasarkan jawaban dan pembaruan Qwertiy :
sumber
Japt , 31 byte
Cobalah online!
Hampir mengarahkan port solusi JS ini . Tidak tahu apakah ada cara yang lebih baik.
Dibongkar & Cara kerjanya
sumber
Stax , 16 byte
Jalankan dan debug itu
Saya tidak yakin apa sebenarnya kelas kompleksitas formal, tetapi cukup cepat untuk melakukan semua kasus uji dalam sepersepuluh detik pada mesin ini.
Dibongkar, tidak diserang, dan dikomentari, sepertinya ini. Dalam program ini, register x awalnya berisi input.
Jalankan yang ini
sumber