Menambah Kode Gray

36

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 0atau 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 0dalam 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 1s dan 0s
  • 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 1dan0

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 , 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.

Patrick Roberts
sumber
1
Terkait Terkait
Martin Ender
Bisakah kita mengambil input sebagai angka?
xnor
1
Kurang jelas, juga terkait .
Martin Ender
1
Dapatkah saya mengambil input dan output secara terbalik, misal 0011untuk 8
Ton Hospel
1
@TonHospel maaf saya tidak melihat pertanyaan Anda tentang I / O terbalik. Seperti yang saya katakan kepada 1000000000 jawaban saya adalah tidak.
Patrick Roberts

Jawaban:

13

Jelly , 10 8 byte

Terima kasih kepada Dennis karena telah menghemat 2 byte.

^\Ḅ‘^H$B

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:

a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ...

Di mana []ada kurung lantai. Pertimbangkan contoh 44representasi binernya 101100. Membagi dengan 2 dan lantai hanya pergeseran kanan, memotong sedikit paling tidak signifikan. Jadi kami mencoba untuk XOR angka-angka berikut

1 0 1 1 0 0
  1 0 1 1 0
    1 0 1 1
      1 0 1
        1 0
          1

Perhatikan bahwa nkolom th berisi nbit 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:

a(n) = n XOR floor(n/2)

Untungnya, Jelly tampaknya memberi masukan secara otomatis ketika mencoba melakukan XOR. Bagaimanapun, ini kodenya:

^\          Cumulative reduce of XOR over the input.
  Ḅ         Convert binary list to integer.
   ‘        Increment.
    ^H$     XOR with half of itself.
       B    Convert integer to binary list.
Martin Ender
sumber
Anda tidak membutuhkan Ḟ$; operator bitwise melakukan cast ke int .
Dennis
@ Dennis Terima kasih, saya menemukan itu saat menulis. :)
Martin Ender
@ MartinEnder Apakah integer yang dikonversi menjadi internal integer besar?
Patrick Roberts
@ PatrickRoberts ya, jika perlu - itu Python di bawah tenda.
Jonathan Allan
Analisis dan penjelasan yang bagus.
Wayne Conrad
8

JavaScript (ES6), 58 byte

s=>s.replace(s.split`1`.length%2?/.$/:/.?(?=10*$)/,c=>1-c)

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.

Neil
sumber
Metode yang sangat bagus. Apakah yang pertama ?masuk /.?(?=10*$)/benar-benar diperlukan? Oh ya sudah. Ya itu. :-)
Arnauld
8

Perl, 27 25 byte

Termasuk +1 untuk -p

Berikan string input pada STDIN, mis

gray.pl <<< 1010

gray.pl:

#!/usr/bin/perl -p
s%(10*\K1(\K0)*)*%1-$&%e

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.

Ton Hospel
sumber
1
Wow, \Gsangat memudahkan Anda!
Neil
1
Di sisi lain, \Kmembuat segalanya lebih mudah bagi Anda.
Neil
Haaaaa ... Sekarang saya ingin melihat \Gimplementasinya juga.
Magic Octopus Guci
2
@carusocomputing Anda dapat melihat versi kiriman yang lebih lama dengan mengklik tautan yang diedit
Ton Hospel
6

Haskell, 118 115 108 byte

g 0=[""]
g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile
f s=d(=='0')$(d(/='0':s)$g$1+length s)!!1

Cobalah di Ideone.
Pendekatan naif: gmenghasilkan set semua kode abu-abu dengan panjang n(dengan 0-padding), fmemanggil gdengan length(input)+1, menghapus semua elemen hingga 0<inputstring>ditemukan dan mengembalikan elemen berikutnya (memotong kemungkinan yang memimpin 0).

Laikoni
sumber
1
Jawaban pertama yang bagus! Saya harap kita bisa mendapatkan yang lebih efisien segera.
Patrick Roberts
5

MATL , 18 byte

ZBtE:t2/kZ~tb=fQ)B

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.

ZB      % Input string implicitly. Convert from binary string to integer
        %   STACK: 5
t       % Duplicate
        %   STACK: 5, 5
E       % Multiply by 2. This is the number of terms we'll generate from the sequence
        %   STACK: 5, 10
:       % Range
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10]
t       % Duplicate
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [1 2 3 4 5 6 7 8 9 10]
2/k     % Divide by 2 and round down, element-wise
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [0 1 1 2 2 3 3 4 4 5]
Z~      % Bit-wise XOR, element-wise
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15]
t       % Duplicate
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15]
b       % Bubble up
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15], 5
=       % Equality test, element-wise
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [0 0 0 0 0 1 0 0 0 0]
f       % Find: yield (1-based) index of nonzero values (here there's only one)
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 6
Q       % Increase by 1
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 7
)       % Apply as index
        %   STACK: 4
B       % Convert to binary array
        %   STACK: [1 0 0]
        % Implicitly display
Luis Mendo
sumber
Saya perhatikan hasilnya adalah karakter yang dibatasi ruang ... apakah ia mencetak semacam array?
Patrick Roberts
@ PatrickRoberts Ya, tepatnya. Saya berasumsi itu dapat diterima, bukan?
Luis Mendo
Saya akan menerimanya apa adanya. Saya sudah melonggarkan persyaratan saya dalam format I / O, jadi tidak ada gunanya membuatnya lebih ketat lagi. Pekerjaan yang baik.
Patrick Roberts
5

CJam (19 byte)

{_2b__(^@1b1&*)^2b}

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

{         e# Declare a block:
  _2b     e#   Convert the bit array to a binary number
  __(^    e#   x ^ (x-1) gives 1s from the least significant set bit down
  @1b1&   e#   Get the parity of the number of set bits from the original array
  *       e#   Multiply: if we have an even number of set bits, we get 0;
          e#   otherwise we have 2**(lssb + 1) - 1
  )^      e#   Increment and xor by 1 or 2**(lssb + 1)
  2b      e#   Base convert back to a bit array
}

Bekerja hanya dengan bit array, saya pikir perlu untuk membalikkannya: bekerja dengan yang paling kiri 1jauh lebih mudah daripada yang paling kanan. Yang terbaik yang saya temukan sejauh ini adalah (24 byte):

{W%_1b)1&1$+1#0a*1+.^W%}

Pendekatan alternatif (19 byte)

{[{1$^}*]2b)_2/^2b}

Ini mengkonversi dari kode Gray ke indeks, kenaikan, dan mengkonversi kembali ke kode Gray.

Peter Taylor
sumber
5

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).

f=(s,n=1)=>(b=(n^n/2).toString(2),s)?f(b!=s&&s,n+1):b

console.log(f("1"));      // -> 11
console.log(f("11"));     // -> 10
console.log(f("111"));    // -> 101
console.log(f("1011"));   // -> 1001
console.log(f("1111"));   // -> 1110
console.log(f("10111"));  // -> 10110
console.log(f("101100")); // -> 100100
console.log(f("100000")); // -> 1100000

Arnauld
sumber
Saya khawatir pengiriman ini tidak memenuhi syarat, karena metode ini tidak berfungsi untuk panjang string yang tidak terikat. Harap ubah ke non-kompetitif jika Anda ingin menyimpan jawaban ini di sini.
Patrick Roberts
@ Patrickrickoberts - Tentu. Itu masuk akal.
Arnauld
@ PatrickRoberts Benarkah? Bagaimana batas rekursi tidak jatuh di bawah "keterbatasan memori yang dipaksakan oleh lingkungan."
Sanchises
@sanchises Saya merujuk ke memori tumpukan, tetapi lebih tepatnya, program ini berulang untuk setiap kode abu-abu yang mungkin hingga yang sedang diuji, yang sangat tidak efisien. Secara teknis ini dapat diajukan sebagai "Node.js 6.5" dan telah --harmonyditambahkan untuk byte penalti untuk memiliki akses ke optimasi rekursi tail-call, yang tampaknya mungkin di sini.
Patrick Roberts
@sanchises Melihat balasan saya, itu argumen yang buruk. Masalah utama adalah bahwa batasan itu tidak dipaksakan oleh lingkungan, itu dikenakan oleh algoritma. Ada jawaban lain yang berulang untuk setiap bit daripada untuk setiap nilai tambahan, dan saya menemukan mereka lebih dapat diterima karena bekerja untuk rentang nilai yang jauh lebih luas.
Patrick Roberts
2

Retina, 25 byte

^(10*10*)*
$1:
1:
0
.?:
1

Saya merasa yakin harus ada cara yang lebih baik untuk melakukan ini ...

Neil
sumber
Apakah Anda benar-benar membutuhkannya ^?
Ton Hospel
@TonHospel Regex mencoba mencocokkan di mana saja tanpanya. (Ganti mode default ke penggantian global.)
Neil
2

05AB1E , 12 byte

Menggunakan pengodean CP-1252 .

CÐ<^¹SOÉ*>^b

Cobalah online!

Penjelasan

Contoh untuk input 1011 .

C              # convert to int (bigint if necessary)
               # STACK: 11
 Ð             # triplicate
               # STACK: 11, 11, 11
  <            # decrease by 1
               # STACK: 11, 11, 10
   ^           # XOR
               # STACK: 11, 1
    ¹          # push first input
               # STACK: 11, 1, 1011
     S         # split to list
               # STACK: 11, 1, [1,0,1,1]
      O        # sum
               # STACK: 11, 1, 3
       É       # mod 2
               # STACK: 11, 1, 1
        *      # multiply
               # STACK: 11, 1
         >     # increase by 1
               # STACK: 11, 2
          ^    # XOR
               # STACK: 9
           b   # convert to binary
               # STACK: 1001
               # implicitly print top of stack
Emigna
sumber
2

Python 2.7, 68 karakter

def f(s):i=long(s,2);print bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:]

Python 3, 68 karakter

def f(s):i=int(s,2);print(bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:])

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 0bawalan boolean.

Morwenn
sumber
1
Anda dapat menyimpan 1 byte dengan menghapus spasi setelah def f(s):dan (dengan asumsi Python 2) yang lain dengan menggunakan printalih-alih return.
ElPedro
@ ElPedro Terima kasih, saya juga menerapkan trik kondisi dan memperhitungkan ukuran tangan kiri sebuah xor untuk menyimpan beberapa karakter tambahan :)
Morwenn
Baru saja melihatnya. Jawaban yang bagus :-)
ElPedro
Um .. memeriksa dokumentasi python, sepertinya 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 valid
Patrick Roberts
1
@ PatrickRoberts saya akan periksa nanti. longbukannya intmungkin menyelesaikan masalah.
Morwenn
2

C ++, 205 byte

#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}

Deskripsi: Angka genap memiliki angka genap. Variabel zmenghitung satu; jikaz genap ( z mod 2 = z%2 = 0- cabang lain), ubah bit terakhir; jika zaneh, panggil fungsi ini lagi tanpa karakter terakhir dan hitung nilai baru, kemudian tambahkan karakter terakhir sesudahnya.

Klik di sini untuk mencobanya untuk test case.

AlexRacer
sumber
Terima kasih atas kiriman Anda. Jika Anda bisa memberikan deskripsi singkat tentang pendekatan Anda dan tautan ke kompilasi online ini sebagai demo, saya sangat menghargai itu.
Patrick Roberts
1
@ PatrickRoberts Menambahkan tautan dan deskripsi seperti yang Anda minta.
AlexRacer
2

Batch, 199 197 byte

@echo off
set/ps=
set r=
set t=%s:0=%
if 1%t:11=%==1 goto g
:l
set b=%s:~-1%
set s=%s:~,-1%
set r=%b%%r%
if %b%==0 goto l
if 0%s%==0 set s=0
:g
set/ab=1-%s:~-1%
echo %s:~,-1%%b%%r%

Membaca 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. skarena itu berisi awalan paritas genap dan rsisa string. sdiatur ke nol jika kosong sehingga digit terakhirnya dapat diaktifkan, dan kemudian semuanya digabungkan.

Neil
sumber
1

Sebenarnya, 20 19 13 byte

Didasarkan pada jawaban Martin Ender's Jelly dengan versi saya sendiri "pengurangan kumulatif XOR atas input". Saran golf diterima. Cobalah online!

σ1♀&2@¿u;½≈^├

Tidak melakukanolf

      Implicit input a as a list, such as [1,0,1,1,0,0].
σ     Get the cumulative sums of a.
1♀&   Map x&1 (equivalent to x%2) over every member of the cumulative sum.
2@¿   Convert from binary to decimal.
u     Increment x.
;½≈   Duplicate and integer divide by 2.
^     XOR x and x//2.
├     Convert to binary to obtain our incremented Gray code.
      Implicit return as a string, such as "100100".
Sherlock9
sumber
1

J, 38 byte

[:#:@(22 b.<.@-:)@>:@#.[:22 b./[:#:#.\

Cobalah online!

Ini pada dasarnya adalah algoritma Martin dalam J.

Perhatikan bahwa 22 b.XOR.

                                    [: #: #.\   Creates the prefixes of the input
                                                converts to a number, then converts
                                                back to binary.  Needed to get the
                                                padding on the left.

                          [: 22 b./             Reduce the rows of the resulting 
                                                matrix with XOR, giving us the 
                                                normal binary
                      @#.                       Convert to int and...
                   @>:                          Increment and...
      (22 b. <.@-:)                             XOR that with its own floored half
[: #:@                                          And turn the result back to binary
Jonah
sumber
Kerja bagus, bung!
Patrick Roberts