Wprowadzenie

Grey kod jest alternatywą dla reprezentacji binarnej, w których liczba jest zwiększana przez przełączenie tylko jednego bitu, a nie do ilości zmienny bitów. Oto niektóre szare kody wraz z ich dziesiętnymi i binarnymi odpowiednikami:

 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

Cykliczny wzór bitowy szarego kodu

Czasami nazywany „odzwierciedleniem binarnym”, właściwość zmiany tylko jednego bitu na raz jest łatwo osiągana dzięki cyklicznym wzorom bitów dla każdej kolumny, zaczynając od najmniej znaczącego bitu:

bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111

...i tak dalej.

Cel

Biorąc pod uwagę niepochodzący ciąg wejściowy szarego kodu, zwiększaj szary kod, zmieniając pojedynczy znak w sekwencji lub przygotowując 1(przy zwiększaniu do następnej potęgi 2), a następnie wyślij wynik jako niepodszarpany szary kod.

Ostrzeżenia

• Nie martw się o pobranie 0lub pusty ciąg znaków jako dane wejściowe.
• Najniższe wejście będzie 1, i nie ma górnego ograniczenia długości łańcucha innego niż ograniczenia pamięci narzucone przez środowisko.
• Przez łańcuch bez dopełnienia mam na myśli, że nie będzie żadnych początkowych ani końcowych białych znaków (poza opcjonalnym końcowym znakiem nowej linii) i żadnych wiodących liter 0s na wejściu lub wyjściu.

Formaty we / wy

Następujące formaty są akceptowane jako dane wejściowe i wyjściowe, ale zachęca się ciągi znaków w stosunku do innych formatów:

• najważniejszy „bit” jako pierwszy
• non-wyściełane tablica znak lub ciąg ASCII '1's i '0's
• niepaścieniana tablica liczb całkowitych 1s i 0s
• niemodyfikowana tablica boolowska

Co nie jest dozwolone:

• najpierw najmniej znaczący „bit”
• dziesiętna, binarna lub jednoargumentowa liczba całkowita
• struktura danych o stałej długości
• tablica znaków lub ciąg niedrukowalnych indeksów ASCII 1i0

Testy

input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000

_{Więcej testów można dodać na żądanie.}

Kryteria

To jest golf golfowy , więc wygrywa najkrótszy program w bajtach! Wszystkie więzi zostaną zerwane przez faworyzowanie wcześniejszych zgłoszeń; obowiązują standardowe luki. Najlepsza przesłana odpowiedź zostanie zaakceptowana 9 października 2016 r. I będzie aktualizowana za każdym razem, gdy zostaną podane lepsze odpowiedzi.

Galaretka , 10 8 bajtów

Dzięki Dennis za oszczędność 2 bajtów.

^\Ḅ‘^H$B

Wejścia i wyjścia to listy zer i jedynek.

Wypróbuj online!

Wyjaśnienie

Odwrotność kodu Graya podana jest przez A006068 . Korzystając z tego, nie musimy generować dużej liczby kodów Graya, aby sprawdzić dane wejściowe. Jedna klasyfikacja tej sekwencji podana w OEIS jest następująca:

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

Gdzie []są wsporniki podłogowe. Rozważ przykład, 44którego reprezentacją binarną jest 101100. Dzielenie przez 2 i podłogę jest tylko przesunięciem w prawo, odcinając najmniej znaczący kawałek. Więc próbujemy XOR następujące liczby

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

Zauważ, że n kolumna th zawiera pierwsze nbity. Stąd ta formuła może być obliczona w sposób trywialny na wejściu binarnym jako skumulowana redukcja XOR na liście (która zasadniczo stosuje XOR do każdego prefiksu listy i daje nam listę wyników).

To daje nam prosty sposób na odwrócenie szarego kodu. Następnie zwiększamy wynik i przekształcamy go z powrotem w kod Graya. W ostatnim kroku używamy następującej definicji:

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

Na szczęście Jelly wydaje się automatycznie umieszczać dane wejściowe na podłodze przy próbie ich XOR. W każdym razie oto kod:

^\          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.

JavaScript (ES6), 58 bajtów

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

Bezpośrednio przełącza odpowiedni bit. Objaśnienie: Jak pokazano w odpowiedzi MartinEnder ♦, każdy bit w zdekodowanym kodzie Graya jest skumulowanym XOR lub parzystością samego siebie i bitów po jego lewej stronie. Następnie musimy zwiększyć liczbę, która powoduje tętnienie przenoszenia, które przełącza wszystkie skrajnie prawe 1 bity na 0, a następnie następne 0 bitów na 1. Ponowne kodowanie powoduje powstanie kodu z tylko jedną pozycją 0 bitów przełączoną. Jeśli parzystość wszystkich 1 bitów jest parzysta, to bit najbardziej po prawej stronie wynosi 0, a zatem przełączamy tylko ostatni bit. Jeśli parzystość wszystkich 1 bitów jest nieparzysta, to najbardziej prawostronne bity wynoszą 1 i musimy znaleźć ostatni 1 bit. To jest teraz ostatni z przenoszonych bitów, więc bit, który musimy przełączyć, to następny bit od prawej.

Perl, 27 25 bajtów

Obejmuje +1 dla -p

Podaj ciąg wejściowy na STDIN, np

gray.pl <<< 1010

gray.pl:

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

Perl nie ma tanich liczb całkowitych o nieskończonej precyzji. Więc bezpośrednio przełącz odpowiedni bit, który jest tuż przed tym, gdzie będzie ostatnia nieparzysta 1.

Haskell, 118 115 108 bajtów

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

Wypróbuj na Ideone.
Naiwne podejście: ggeneruje zestaw wszystkich szarych kodów o długości n(z dopełnieniem 0), fwywołuje za gpomocą length(input)+1, usuwa wszystkie elementy, dopóki nie 0<inputstring>zostanie znaleziony, i zwraca następny element (obcinając potencjalnie wiodący 0).

MATL , 18 bajtów

ZBtE:t2/kZ~tb=fQ)B

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Niech a ( n ) oznacza sekwencję liczb całkowitych odpowiadających kodom Graya ( OEIS A003188 ). Program wykorzystuje charakterystykę a ( n ) = n XOR floor ( n / 2), gdzie XOR jest bitowy.

Zasadniczo, kod przetwarza sygnał wejściowy na całkowitą w ₀ stwierdza, że całkowitą w kolejności, a następnie wybiera następny określenia. Wymaga to wygenerowania wystarczająco dużej liczby elementów sekwencji a ( n ). Okazuje się, że 2 · ₀ jest dostatecznie duża. Wynika to z faktu, że szary kod a ( n ) nigdy nie ma więcej cyfr binarnych niż n .

Weźmy '101'za przykład przykład.

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

CJam (19 bajtów)

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

Demo online . Jest to anonimowy blok (funkcja) z tablicy bitów do tablicy bitów, który demo wykonuje w pętli.

Działa na prostej zasadzie, że jeśli liczba ustawionych bitów jest równa, powinniśmy przełączyć najmniej znaczący bit, a w przeciwnym razie powinniśmy przełączyć bit na lewo od najmniej znaczącego zestawu bitów. Właściwie identyfikacja tego bitu okazuje się znacznie łatwiejsza przy użyciu hacków bitowych na liczbach całkowitych niż przy użyciu listy bitów.

Sekcja

{         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
}

Pracując wyłącznie z tablicą bitów, myślę, że trzeba ją odwrócić: praca z lewą stroną 1jest znacznie łatwiejsza niż z prawej. Najlepsze, jakie do tej pory znalazłem, to (24 bajty):

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

Alternatywne podejście (19 bajtów)

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

To konwertuje z kodu Graya na indeks, inkrementuje i konwertuje z powrotem na kod Graya.

JavaScript (ES6), 53 bajty (niekonkurujące)

Funkcja rekurencyjna, która buduje wszystkie szare kody aż do znalezienia danych wejściowych, a następnie zatrzymuje się przy następnej iteracji.

Najwyższe możliwe wejście zależy od limitu rekurencji przeglądarki (około 13 bitów w Firefoksie i 15 bitów w 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

Siatkówka, 25 bajtów

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

Jestem pewien, że powinien istnieć lepszy sposób na zrobienie tego ...

05AB1E , 12 bajtów

Wykorzystuje kodowanie CP-1252 .

CÐ<^¹SOÉ*>^b

Wypróbuj online!

Wyjaśnienie

Przykład dla wejścia 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

Python 2.7, 68 znaków

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

Python 3, 68 znaków

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

Ta funkcja konwertuje podany ciąg binarny na liczbę całkowitą, a następnie x lub ostatni bit, jeśli liczba ustawionych bitów w oryginalnym ciągu jest parzysta, lub zamienia bit na lewo od skrajnie prawego zestawu bitów, jeśli liczba ustawionych bitów w oryginale ciąg jest nieparzysty. Następnie konwertuje wynik na ciąg binarny i usuwa 0bprzedrostek boolowski.

C ++, 205 bajtów

#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;}

Opis: Parzyste liczby mają parzystą liczbę jedynek. Zmienne się zliczą; jeśli zjest parzysty ( z mod 2 = z%2 = 0- gałąź else), zmień ostatni bit; Jeśliz jest nieparzysty, wywołaj tę funkcję ponownie bez ostatniego znaku i oblicz nową wartość, a następnie dołącz ostatni znak.

Kliknij tutaj, aby wypróbować go dla przypadków testowych.

Partia, 199 197 bajtów

@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%

Odczytuje dane wejściowe ze STDIN do zmiennej s. Usuwa zera i wykonuje kontrolę parzystości na jedynkach, a jeśli liczba nieparzysta jest usuwana z pętli z prawej strony zer, zatrzymując się, gdy usuwa zera 1. sdlatego zawiera prefiks parzystości i rresztę ciągu.sjest ustawiony na zero, jeśli był pusty, aby można było przełączać jego ostatnią cyfrę, a następnie wszystko jest konkatenowane.

Właściwie 20 19 13 bajtów

Na podstawie odpowiedzi Jelly Martina Endera z moją własną wersją „skumulowanego zmniejszenia XOR ponad dane wejściowe”. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

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

Ungolfing

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

J, 38 bajtów

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

Wypróbuj online!

Jest to zasadniczo algorytm Martina w J.

Zauważ, że 22 b.to 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