Introdução

Um código cinza é uma alternativa à representação binária na qual um número é incrementado alternando apenas um bit, em vez de uma quantidade variável de bits. Aqui estão alguns códigos em cinza, juntamente com seus equivalentes decimais e binários:

 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

Padrão de bit cíclico de um código cinza

Às vezes chamada de "binário refletido", a propriedade de alterar apenas um bit de cada vez é facilmente alcançada com padrões de bits cíclicos para cada coluna a partir do bit menos significativo:

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

...e assim por diante.

Objetivo

Dada uma sequência de entrada não preenchida de um código cinza, aumente o código cinza alternando um único caractere na sequência ou acrescentando a 1(ao aumentar para a próxima potência de 2) e, em seguida, imprima o resultado como um código cinza não preenchido.

Ressalvas

• Não se preocupe em pegar 0uma string vazia ou como entrada.
• A entrada mais baixa será 1e não há limite superior para o comprimento da cadeia, exceto as limitações de memória impostas pelo ambiente.
• Por sequência não preenchida, quero dizer que não haverá espaços em branco à esquerda ou à direita (exceto uma nova linha à direita) e nem 0s na entrada ou saída.

Formatos de E / S

Os seguintes formatos são aceitos para entrada e saída, mas as cadeias são incentivadas em relação a outros formatos:

• "bit" mais significativo primeiro
• array de caracteres não-acolchoado ou seqüência de ASCII '1's e '0's
• matriz inteira não preenchida de 1s e 0s
• matriz booleana não acolchoada

O que não é permitido:

• "bit" menos significativo primeiro
• número inteiro decimal, binário ou unário
• estrutura de dados de comprimento fixo
• matriz de caracteres ou sequência de índices ASCII não imprimíveis 1e0

Testes

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

_{Mais testes podem ser adicionados por solicitação.}

Critério

Isso é código-golfe , e o programa mais curto em bytes vence! Todos os laços serão rompidos favorecendo envios anteriores; lacunas padrão se aplicam. A melhor resposta enviada será aceita em 9 de outubro de 2016 e atualizada sempre que melhores respostas forem fornecidas.

Geléia , 10 8 bytes

Agradecimentos a Dennis por salvar 2 bytes.

^\Ḅ‘^H$B

Entrada e saída são listas de 0s e 1s.

Experimente online!

Explicação

O inverso do código Gray é dado por A006068 . Usando isso, não precisamos gerar um grande número de códigos Gray para procurar a entrada. Uma classificação desta sequência dada no OEIS é a seguinte:

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

Onde []estão os suportes do piso. Considere o exemplo de 44cuja representação binária é 101100. Dividir por 2 e piso é apenas o deslocamento certo, cortando a parte menos significativa. Então, nós estamos tentando XOR os seguintes números

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

Observe que a ncoluna th contém os primeiros nbits. Portanto, essa fórmula pode ser calculada trivialmente na entrada binária como a redução cumulativa de XOR sobre a lista (que basicamente aplica XOR a cada prefixo da lista e fornece uma lista dos resultados).

Isso nos dá uma maneira simples de inverter o código Gray. Depois, apenas incrementamos o resultado e o convertemos novamente no código Gray. Para o último passo, usamos a seguinte definição:

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

Felizmente, Jelly parece colocar as entradas automaticamente ao tentar fazer o XOR delas. Enfim, aqui está o código:

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

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

Alterna diretamente o bit apropriado. Explicação: Conforme mostrado na resposta de MartinEnder ♦, cada bit em um código Grey decodificado é o XOR cumulativo, ou paridade, de si mesmo e os bits à esquerda. Em seguida, precisamos incrementar o número que causa uma ondulação de transporte que alterna todos os 1 bits mais à direita para 0 e, em seguida, o próximo 0 para 1. A recodificação resulta em um código com apenas uma posição de 0 bits alternada. Se a paridade de todos os 1 bits for par, o bit mais à direita será 0 e, portanto, apenas alternamos o último bit. Se a paridade de todos os 1 bits for ímpar, os bits mais à direita serão 1, e precisamos encontrar o último 1 bit. Agora é o último dos bits transportados, portanto, o que precisamos alternar é o próximo da direita.

Perl, 27 25 bytes

Inclui +1 para -p

Dê uma string de entrada no STDIN, por exemplo

gray.pl <<< 1010

gray.pl:

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

O Perl não possui inteiros baratos de precisão infinita. Então, alterne diretamente o bit certo, que é o mesmo antes de onde seria o último número ímpar 1.

Haskell, 118 115 108 bytes

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

Experimente em Ideone.
Abordagem ingênua: ggera o conjunto de todos os códigos cinzas com comprimento n(com preenchimento de 0), fchama gcom length(input)+1, remove todos os elementos até que 0<inputstring>seja encontrado e retorna o próximo elemento (truncando um possível início 0).

MATL , 18 bytes

ZBtE:t2/kZ~tb=fQ)B

Experimente online! Ou verifique todos os casos de teste .

Explicação

Deixei a ( n ) a sequência de números inteiros correspondente aos códigos de Gray ( OEIS A003188 ). O programa usa a caracterização a ( n ) = n piso XOR ( n / 2), onde XOR é bit a bit.

Essencialmente, o código converte a entrada em um número inteiro a ₀ , localiza esse número inteiro na sequência e seleciona o próximo termo. Isso requer a geração de um número suficientemente grande de termos da sequência a ( n ). Acontece que 2 · a ₀ é suficientemente grande. Isso decorre do fato de o código Gray a ( n ) nunca ter mais dígitos binários que n .

Vamos dar '101'um exemplo como exemplo.

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

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

Demonstração online . Este é um bloco anônimo (função) de matriz de bits para matriz de bits, que a demonstração executa em um loop.

Ele trabalha com o princípio simples de que, se o número de bits definidos for igual, devemos alternar o bit menos significativo e, caso contrário, devemos alternar o bit para a esquerda do bit menos definido. Na verdade, identificar esse bit é muito mais fácil usando hacks de bits em um número inteiro do que usando a lista de bits.

Dissecação

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

Trabalhando exclusivamente com a matriz de bits, acho que é necessário revertê-la: trabalhar com a extremidade esquerda 1é muito mais fácil do que a extremidade direita. O melhor que encontrei até agora é (24 bytes):

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

Abordagem alternativa (19 bytes)

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

Isso converte do código Gray em índice, incrementa e converte novamente no código Gray.

JavaScript (ES6), 53 bytes (não concorrente)

Uma função recursiva que constrói todos os códigos em cinza até que a entrada seja encontrada e pára na próxima iteração.

A entrada mais alta possível depende do limite de recursão do navegador (cerca de 13 bits no Firefox e 15 bits no 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

Retina, 25 bytes

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

Tenho certeza de que deve haver uma maneira melhor de fazer isso ...

05AB1E , 12 bytes

Usos a codificação CP-1252 .

CÐ<^¹SOÉ*>^b

Experimente online!

Explicação

Exemplo para a entrada 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 caracteres

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

Python 3, 68 caracteres

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

Essa função converte a sequência binária especificada em um número inteiro e, em seguida, x ou o último bit, se o número de bits configurados na string original for par ou alterna o bit para a esquerda do bit definido à direita, se o número de bits configurados no original string é ímpar. Em seguida, converte o resultado em uma sequência binária e remove o 0bprefixo booleano.

C ++, 205 bytes

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

Descrição: os números pares têm um número par de unidades. Variável zconta os; se zfor par ( z mod 2 = z%2 = 0- outro ramo), altere o último bit; se zfor ímpar, chame essa função novamente sem o último caractere e calcule o novo valor, depois acrescente o último caractere.

Clique aqui para experimentá-lo nos casos de teste.

Lote, 199 197 bytes

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

Lê a entrada de STDIN na variável s. Remove os 0s e faz uma verificação de paridade nos 1s e, se houver um número ímpar, retira os 0s mais à direita em um loop, parando quando retira um 1., sportanto, contém o prefixo de paridade par e ro restante da sequência. sé definido como zero se estiver em branco para que seu último dígito possa ser alternado e tudo seja concatenado.

Na verdade, 20 19 13 bytes

Baseado na resposta Jelly de Martin Ender com minha própria versão de "redução cumulativa de XOR sobre a entrada". Sugestões de golfe são bem-vindas. Experimente 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 bytes

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

Experimente online!

Este é essencialmente o algoritmo de Martin em J.

Observe que 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