pengantar
Kode Abu - abu adalah alternatif untuk representasi biner di mana angka bertambah dengan mengubah hanya satu bit, daripada jumlah variabel bit. Berikut adalah beberapa kode abu-abu beserta desimal dan binernya:
decimal | binary | gray
-------------------------
0 | 0 | 0
-------------------------
1 | 1 | 1
-------------------------
2 | 10 | 11
-------------------------
3 | 11 | 10
-------------------------
4 | 100 | 110
-------------------------
5 | 101 | 111
-------------------------
6 | 110 | 101
-------------------------
7 | 111 | 100
-------------------------
8 | 1000 | 1100
-------------------------
9 | 1001 | 1101
-------------------------
10 | 1010 | 1111
-------------------------
11 | 1011 | 1110
-------------------------
12 | 1100 | 1010
-------------------------
13 | 1101 | 1011
-------------------------
14 | 1110 | 1001
-------------------------
15 | 1111 | 1000
Pola Bit Siklik dari Kode Abu-abu
Kadang-kadang disebut "binary tercermin", sifat mengubah hanya satu bit pada satu waktu mudah dicapai dengan pola bit siklik untuk setiap kolom mulai dari bit paling signifikan:
bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111
...dan seterusnya.
Objektif
Diberikan string input non-empuk dari kode abu-abu, menambah kode abu-abu dengan bergantian karakter tunggal dalam urutan atau mengawali a 1
(saat menambah ke kekuatan berikutnya 2), kemudian output hasilnya sebagai kode abu-abu non-empuk.
Peringatan
- Jangan khawatir tentang mengambil
0
atau string kosong sebagai input. - Input terendah adalah
1
, dan tidak ada batas atas untuk panjang string selain dari batasan memori yang dikenakan oleh lingkungan. - Dengan string non-padded, maksud saya tidak akan ada spasi spasi awal atau tambahan (selain baris tambahan opsional), dan tidak ada pemimpin
0
dalam input atau output.
Format I / O
Format berikut adalah formulir yang diterima untuk input dan output, tetapi string dianjurkan daripada format lain:
- "bit" paling penting terlebih dahulu
- array karakter atau string ASCII
'1'
s dan'0'
s - array integer non-empuk dari
1
s dan0
s - array boolean non-empuk
Apa yang tidak diizinkan:
- "bit" paling penting terlebih dahulu
- bilangan desimal, biner atau bilangan bulat unary
- struktur data tetap-panjang
- array karakter atau string indeks ASCII yang tidak dapat dicetak
1
dan0
Tes
input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000
Lebih banyak tes dapat ditambahkan berdasarkan permintaan.
Kriteria
Ini adalah kode-golf , sehingga program terpendek dalam byte menang! Semua ikatan akan diputuskan dengan menyetujui pengiriman sebelumnya; celah standar berlaku. Jawaban yang diajukan terbaik akan diterima pada 9 Oktober 2016, dan diperbarui setiap kali jawaban yang lebih baik diberikan.
sumber
0011
untuk 8Jawaban:
Jelly ,
108 byteTerima kasih kepada Dennis karena telah menghemat 2 byte.
Input dan output adalah daftar 0s dan 1s.
Cobalah online!
Penjelasan
Kebalikan dari kode Gray diberikan oleh A006068 . Menggunakan ini, kita tidak perlu menghasilkan sejumlah besar kode Gray untuk mencari input. Salah satu klasifikasi urutan ini diberikan pada OEIS adalah ini:
Di mana
[]
ada kurung lantai. Pertimbangkan contoh44
representasi binernya101100
. Membagi dengan 2 dan lantai hanya pergeseran kanan, memotong sedikit paling tidak signifikan. Jadi kami mencoba untuk XOR angka-angka berikutPerhatikan bahwa
n
kolom th berisin
bit pertama . Oleh karena itu, rumus ini dapat dihitung secara sepele pada input biner sebagai pengurangan kumulatif XOR atas daftar (yang pada dasarnya berlaku XOR untuk setiap awalan daftar dan memberi kami daftar hasil).Ini memberi kita cara sederhana untuk membalikkan kode Gray. Setelah itu, kami hanya menambah hasilnya dan mengubahnya kembali menjadi kode Gray. Untuk langkah terakhir kami menggunakan definisi berikut:
Untungnya, Jelly tampaknya memberi masukan secara otomatis ketika mencoba melakukan XOR. Bagaimanapun, ini kodenya:
sumber
Ḟ$
; operator bitwise melakukan cast ke int .JavaScript (ES6), 58 byte
Langsung matikan bit yang sesuai. Penjelasan: Seperti yang ditunjukkan dalam jawaban MartinEnder ♦, setiap bit dalam kode Gray yang didekodekan adalah kumulatif XOR, atau paritas, dari dirinya sendiri dan bit di sebelah kirinya. Kita kemudian perlu menambah angka yang menyebabkan riak carry yang mengubah semua bit paling kanan menjadi 0 dan 0 bit berikutnya ke 1. Pengodean ulang menghasilkan kode dengan hanya satu posisi 0 bit yang di-toggle. Jika paritas semua bit 1 genap, maka bit paling kanan adalah 0 dan oleh karena itu kami hanya beralih bit terakhir. Jika paritas semua 1 bit aneh, maka bit paling kanan adalah 1, dan kita perlu menemukan 1 bit terakhir. Ini sekarang bit terakhir yang dibawa, jadi bit yang perlu kita ganti adalah bit berikutnya dari kanan.
sumber
?
masuk/.?(?=10*$)/
benar-benar diperlukan? Oh ya sudah. Ya itu. :-)Perl,
2725 byteTermasuk +1 untuk
-p
Berikan string input pada STDIN, mis
gray.pl
:Perl tidak memiliki bilangan bulat presisi tak terbatas murah. Jadi langsung beralih bit yang tepat yang merupakan tepat sebelum di mana angka ganjil 1 terakhir akan berada.
sumber
\G
sangat memudahkan Anda!\K
membuat segalanya lebih mudah bagi Anda.\G
implementasinya juga.Haskell,
118 115108 byteCobalah di Ideone.
Pendekatan naif:
g
menghasilkan set semua kode abu-abu dengan panjangn
(dengan 0-padding),f
memanggilg
denganlength(input)+1
, menghapus semua elemen hingga0<inputstring>
ditemukan dan mengembalikan elemen berikutnya (memotong kemungkinan yang memimpin0
).sumber
MATL , 18 byte
Cobalah online! Atau verifikasi semua kasus uji .
Penjelasan
Biarkan a ( n ) menunjukkan urutan bilangan bulat yang sesuai dengan kode Gray ( OEIS A003188 ). Program ini menggunakan karakterisasi a ( n ) = n lantai XOR ( n / 2), di mana XOR adalah bit-wise.
Pada dasarnya, kode mengkonversi input ke integer sebuah 0 , temuan bahwa bilangan bulat dalam urutan, dan kemudian memilih istilah berikutnya. Ini membutuhkan menghasilkan sejumlah besar syarat dari urutan a ( n ). Ternyata 2 · a 0 cukup besar. Ini berasal dari fakta bahwa kode Gray a ( n ) tidak pernah memiliki lebih banyak digit biner daripada n .
Mari kita ambil input
'101'
sebagai contoh.sumber
CJam (19 byte)
Demo online . Ini adalah blok anonim (fungsi) dari bit array ke bit array, yang dieksekusi demo dalam satu lingkaran.
Ini bekerja pada prinsip sederhana bahwa jika jumlah bit set bahkan kita harus beralih bit paling signifikan, dan kalau tidak kita harus beralih bit ke kiri bit set paling tidak signifikan. Sebenarnya mengidentifikasi bit itu ternyata jauh lebih mudah menggunakan bit hacks pada integer daripada menggunakan daftar bit.
Pembedahan
Bekerja hanya dengan bit array, saya pikir perlu untuk membalikkannya: bekerja dengan yang paling kiri
1
jauh lebih mudah daripada yang paling kanan. Yang terbaik yang saya temukan sejauh ini adalah (24 byte):Pendekatan alternatif (19 byte)
Ini mengkonversi dari kode Gray ke indeks, kenaikan, dan mengkonversi kembali ke kode Gray.
sumber
JavaScript (ES6), 53 byte (tidak bersaing)
Fungsi rekursif yang membangun semua kode abu-abu hingga input ditemukan, lalu berhenti pada iterasi berikutnya.
Input tertinggi yang mungkin tergantung pada batas rekursi browser (sekitar 13 bit di Firefox dan 15 bit di Chrome).
sumber
--harmony
ditambahkan untuk byte penalti untuk memiliki akses ke optimasi rekursi tail-call, yang tampaknya mungkin di sini.Retina, 25 byte
Saya merasa yakin harus ada cara yang lebih baik untuk melakukan ini ...
sumber
^
?05AB1E , 12 byte
Menggunakan pengodean CP-1252 .
Cobalah online!
Penjelasan
Contoh untuk input 1011 .
sumber
Python 2.7, 68 karakter
Python 3, 68 karakter
Fungsi ini mengubah string biner yang diberikan ke integer kemudian xor bit terakhir jika jumlah bit set dalam string asli genap, atau menukar bit ke kiri bit set paling kanan jika jumlah bit set dalam aslinya string itu aneh. Kemudian ia mengubah hasilnya menjadi string biner dan menghapus
0b
awalan boolean.sumber
def f(s):
dan (dengan asumsi Python 2) yang lain dengan menggunakanprint
alih-alihreturn
.int()
menghasilkan integer 32 bit, meskipun persyaratan saya adalah Anda harus menambahkan string panjang apa pun. Saya tidak yakin bahwa ini memenuhi syarat sebagai pengiriman yang validlong
bukannyaint
mungkin menyelesaikan masalah.C ++, 205 byte
Deskripsi: Angka genap memiliki angka genap. Variabel
z
menghitung satu; jikaz
genap (z mod 2 = z%2 = 0
- cabang lain), ubah bit terakhir; jikaz
aneh, panggil fungsi ini lagi tanpa karakter terakhir dan hitung nilai baru, kemudian tambahkan karakter terakhir sesudahnya.Klik di sini untuk mencobanya untuk test case.
sumber
Batch,
199197 byteMembaca input dari STDIN ke dalam variabel
s
. Menghapus 0s dan melakukan parity check pada 1s dan jika ada angka ganjil, strip paling kanan 0s dalam satu lingkaran, berhenti ketika strip 1.s
karena itu berisi awalan paritas genap danr
sisa string.s
diatur ke nol jika kosong sehingga digit terakhirnya dapat diaktifkan, dan kemudian semuanya digabungkan.sumber
Sebenarnya,
201913 byteDidasarkan pada jawaban Martin Ender's Jelly dengan versi saya sendiri "pengurangan kumulatif XOR atas input". Saran golf diterima. Cobalah online!
Tidak melakukanolf
sumber
J, 38 byte
Cobalah online!
Ini pada dasarnya adalah algoritma Martin dalam J.
Perhatikan bahwa
22 b.
XOR.sumber