Incremento de códigos grises

36

Introducción

Un código gris es una alternativa a la representación binaria en la que un número se incrementa al alternar solo un bit, en lugar de una cantidad variable de bits. Aquí hay algunos códigos grises junto con sus equivalentes decimales y binarios:

 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

Patrón de bits cíclicos de un código gris

A veces llamado "binario reflejado", la propiedad de cambiar solo un bit a la vez se logra fácilmente con patrones de bits cíclicos para cada columna a partir del bit menos significativo:

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

...y así.

Objetivo

Dada una cadena de entrada no rellenada de un código gris, incremente el código gris alternando un solo carácter en la secuencia o anteponiendo a 1(cuando se incremente a la siguiente potencia de 2), luego envíe el resultado como un código gris no rellenado.

Advertencias

  • No se preocupe por tomar 0o una cadena vacía como entrada.
  • La entrada más baja será 1, y no hay límite superior a la longitud de la cadena que no sean las limitaciones de memoria impuestas por el entorno.
  • Por cadena sin relleno, quiero decir que no habrá espacios en blanco iniciales o finales (que no sea una nueva línea final opcional), y no habrá 0s iniciales en la entrada o salida.

Formatos de E / S

Se aceptan los siguientes formatos para entrada y salida, pero se recomiendan cadenas sobre otros formatos:

  • "bit" más significativo primero
  • matriz de caracteres no acolchada o cadena de ASCII '1'sy '0's
  • matriz entera no acolchada de 1sy 0s
  • matriz booleana sin relleno

Lo que no está permitido:

  • "bit" menos significativo primero
  • entero decimal, binario o unario
  • estructura de datos de longitud fija
  • matriz de caracteres o cadena de índices ASCII no imprimibles 1y0

Pruebas

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

Se pueden agregar más pruebas a pedido.

Criterios

Este es el , ¡así que el programa más corto en bytes gana! Todos los lazos se romperán favoreciendo las presentaciones anteriores; se aplican las lagunas estándar. La mejor respuesta enviada se aceptará el 9 de octubre de 2016 y se actualizará cada vez que se den mejores respuestas.

Patrick Roberts
fuente
¿Podemos tomar la entrada como un número?
xnor
1
Menos obvio, también relacionado .
Martin Ender
1
¿Puedo invertir la entrada y la salida, por ejemplo, 0011para 8
Ton Hospel el
1
@TonHospel lo siento, no vi su pregunta sobre E / S invertida. Como le dije al 1000000000 mi respuesta es no.
Patrick Roberts el

Respuestas:

13

Jalea , 10 8 bytes

Gracias a Dennis por guardar 2 bytes.

^\Ḅ‘^H$B

Entrada y salida son listas de 0s y 1s.

Pruébalo en línea!

Explicación

El inverso del código Gray viene dado por A006068 . Usando esto, no necesitamos generar una gran cantidad de códigos Gray para buscar la entrada. Una clasificación de esta secuencia dada en OEIS es esta:

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

Donde []están los soportes de piso. Considere el ejemplo de 44cuya representación binaria es 101100. Dividir por 2 y el piso es solo un desplazamiento a la derecha, cortando el bit menos significativo. Así que estamos tratando de XOR los siguientes 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 la ncolumna th contiene los primeros nbits. Por lo tanto, esta fórmula se puede calcular trivialmente en la entrada binaria como la reducción acumulativa de XOR sobre la lista (que básicamente aplica XOR a cada prefijo de la lista y nos da una lista de los resultados).

Esto nos da una manera simple de invertir el código Gray. Luego, simplemente incrementamos el resultado y lo convertimos nuevamente al código Gray. Para el último paso usamos la siguiente definición:

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

Afortunadamente, Jelly parece poner las entradas automáticamente al tratar de XOR. De todos modos, aquí está el 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.
Martin Ender
fuente
No necesitas el Ḟ$; operadores bit a bit emitidos a int .
Dennis
@ Dennis Gracias, descubrí eso mientras escribía. :)
Martin Ender
@MartinEnder ¿El entero que convierte internamente es un entero grande?
Patrick Roberts el
@PatrickRoberts sí, si es necesario, es Python bajo el capó.
Jonathan Allan
Buen análisis y explicación.
Wayne Conrad el
8

JavaScript (ES6), 58 bytes

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

Alterna directamente el bit apropiado. Explicación: Como se muestra en la respuesta de MartinEnder ♦, cada bit en un código Gray decodificado es el XOR acumulativo, o paridad, de sí mismo y los bits a su izquierda. Luego necesitamos incrementar el número que causa una onda de acarreo que alterna todos los 1 bits de la derecha a 0 y luego el siguiente 0 bit a 1. La nueva codificación da como resultado un código con solo esa posición de 0 bits activada. Si la paridad de todos los 1 bits es par, entonces el bit más a la derecha es 0 y, por lo tanto, solo cambiamos el último bit. Si la paridad de todos los 1 bits es impar, entonces los bits más a la derecha son 1, y necesitamos encontrar el último 1 bit. Este es ahora el último de los bits transportados, por lo que el bit que necesitamos alternar es el siguiente bit desde la derecha.

Neil
fuente
Muy buen método. Se el primero ?en /.?(?=10*$)/realmente necesario? Oh no importa. Sí lo es. :-)
Arnauld
8

Perl, 27 25 bytes

Incluye +1 para -p

Dar cadena de entrada en STDIN, p. Ej.

gray.pl <<< 1010

gray.pl:

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

Perl no tiene enteros baratos de precisión infinita. Entonces, cambie directamente el bit derecho, que es el justo antes de donde estaría el último 1 impar.

Ton Hospel
fuente
1
¡Guau, \Grealmente te facilita las cosas!
Neil
1
Por otro lado, \Khace las cosas aún más fáciles para usted.
Neil
Jaaaaa ... Ahora quiero ver la \Gimplementación también.
Magic Octopus Urn
2
@carusocomputing Puede ver versiones anteriores de una presentación haciendo clic en el enlace editado
Ton Hospel
6

Haskell, 118115108 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

Pruébalo en Ideone.
Enfoque ingenuo: ggenera el conjunto de todos los códigos grises con longitud n(con relleno de 0), fllamadas gconlength(input)+1 , elimina todos los elementos hasta que 0<inputstring>se encuentra y devuelve el siguiente elemento (truncando un posible líder 0).

Laikoni
fuente
1
Buena primera respuesta! Espero que podamos obtener algunos más eficientes pronto.
Patrick Roberts el
5

MATL , 18 bytes

ZBtE:t2/kZ~tb=fQ)B

Pruébalo en línea!O verificar todos los casos de prueba .

Explicación

Supongamos que a ( n ) denota la secuencia de enteros correspondientes a los códigos Gray ( OEIS A003188 ). El programa utiliza la caracterización a ( n ) = n XOR floor ( n / 2), donde XOR es de bits.

Esencialmente, el código convierte la entrada en un entero a 0 , encuentra ese entero en la secuencia y luego selecciona el siguiente término. Esto requiere generar un número suficientemente grande de términos de la secuencia a ( n ). Resulta que 2 · a 0 es suficientemente grande. Esto se debe al hecho de que el código Gray a ( n ) nunca tiene más dígitos binarios que n .

Tomemos la entrada '101'como un ejemplo.

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
fuente
Noté que la salida son caracteres delimitados por espacios ... ¿está imprimiendo algún tipo de matriz?
Patrick Roberts el
@PatrickRoberts Sí, exactamente. Asumí que es aceptable, ¿verdad?
Luis Mendo
Lo aceptaré tal como está. Ya he aflojado mis requisitos sobre el formato de E / S, por lo que no tiene sentido volverlo más estricto. Buen trabajo.
Patrick Roberts el
5

CJam (19 bytes)

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

Demostración en línea . Este es un bloque anónimo (función) de matriz de bits a matriz de bits, que la demostración se ejecuta en un bucle.

Funciona según el principio simple de que si el número de bits establecidos es par, deberíamos alternar el bit menos significativo y, de lo contrario, deberíamos alternar el bit a la izquierda del bit menos significativo. En realidad, identificar ese bit resulta mucho más fácil usando hacks de bits en un entero que usando la lista de bits.

Disección

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

Al trabajar únicamente con el conjunto de bits, creo que es necesario revertirlo: trabajar con el extremo izquierdo 1es mucho más fácil que el extremo derecho. Lo mejor que he encontrado hasta ahora es (24 bytes):

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

Enfoque alternativo (19 bytes)

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

Esto convierte de código gris a índice, incrementa y vuelve a convertir a código gris.

Peter Taylor
fuente
5

JavaScript (ES6), 53 bytes (no competitivos)

Una función recursiva que construye todos los códigos grises hasta que se encuentra la entrada, luego se detiene en la siguiente iteración.

La entrada más alta posible depende del límite de recurrencia del navegador (aproximadamente 13 bits en Firefox y 15 bits en 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
fuente
Me temo que este envío no califica, ya que el método no funciona para longitudes de cadena ilimitadas. Cambie a no competitivo si desea mantener esta respuesta aquí.
Patrick Roberts el
@PatrickRoberts - Claro. Eso tiene sentido.
Arnauld el
@PatrickRoberts ¿En serio? ¿Cómo no cae un límite de recursión bajo "limitaciones de memoria impuestas por el entorno"?
Sanchises
@sanchises Me refería a la memoria de almacenamiento dinámico, pero más concretamente, este programa recurre por cada código gris posible hasta el que se está probando, lo cual es extremadamente ineficiente. Técnicamente, esto podría enviarse como "Node.js 6.5" y --harmonyagregarse para bytes de penalización para tener acceso a la optimización de recursión de llamadas de cola, que parece ser posible aquí.
Patrick Roberts
@sanchises Mirando mi respuesta, ese fue un argumento pobre. El problema principal es que la limitación no la impone el entorno, sino el algoritmo. Hay otras respuestas que se repiten para cada bit en lugar de para cada valor incremental, y creo que son más aceptables ya que funciona para un rango mucho más amplio de valores.
Patrick Roberts
2

Retina, 25 bytes

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

Estoy seguro de que debería haber una mejor manera de hacer esto ...

Neil
fuente
¿Realmente necesitas el ^?
Ton Hospel
@TonHospel La expresión regular intentó coincidir en todas partes sin ella. (El modo de reemplazo predeterminado es un reemplazo global.)
Neil
2

05AB1E , 12 bytes

Usos codificación CP-1252 .

CÐ<^¹SOÉ*>^b

Pruébalo en línea!

Explicación

Ejemplo para la 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
Emigna
fuente
2

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:])

Esta función convierte la cadena binaria dada en un número entero y luego xo el último bit si el número de bits establecidos en la cadena original es par, o intercambia el bit a la izquierda del bit establecido más a la derecha si el número de bits establecidos en el original La cadena es extraña. Luego convierte el resultado en una cadena binaria y elimina el 0bprefijo booleano.

Morwenn
fuente
1
Puede guardar 1 byte eliminando el espacio después def f(s):y (suponiendo Python 2) otro utilizando en printlugar de return.
ElPedro
@ElPedro Gracias, también apliqué un truco de condición y factoricé el tamaño de la izquierda de un xor para guardar algunos caracteres adicionales :)
Morwenn
Acabo de ver eso. Buena respuesta :-)
ElPedro
Um ... comprobando la documentación de Python, parece que int()genera un número entero de 32 bits, aunque mi requisito es que incremente cualquier cadena de longitud. No estoy seguro de que esto califique como una presentación válida
Patrick Roberts
1
@PatrickRoberts Lo comprobaré más tarde. longen lugar de intpodría resolver el problema.
Morwenn
2

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

Descripción: los números pares tienen un número par de unos. La variable zcuenta unos; si zes par ( z mod 2 = z%2 = 0- otra rama), modifique el último bit; si zes extraño, llame a esta función nuevamente sin el último carácter y calcule el nuevo valor, luego agregue el último carácter después.

Haga clic aquí para probarlo en los casos de prueba.

AlexRacer
fuente
Gracias por tu presentación. Si pudiera proporcionar una breve descripción de su enfoque y un enlace a una compilación en línea de esto como una demostración, realmente lo agradecería.
Patrick Roberts
1
@PatrickRoberts Agregó el enlace y la descripción que solicitó.
AlexRacer
2

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%

Lee la entrada de STDIN en variable s. Elimina los 0 y realiza una comprobación de paridad en los 1 y, si hay un número impar, elimina los 0 más a la derecha en un bucle, deteniéndose cuando elimina un 1. spor lo tanto, contiene el prefijo de paridad par y rel resto de la cadena. sse establece en cero si estaba en blanco para que su último dígito se pueda alternar, y luego todo se concatena.

Neil
fuente
1

En realidad, 20 19 13 bytes

Basado en la respuesta Jelly de Martin Ender con mi propia versión de "reducción acumulativa de XOR sobre la entrada". Sugerencias de golf bienvenidas. Pruébalo en línea!

σ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".
Sherlock9
fuente
1

J, 38 bytes

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

Pruébalo en línea!

Este es esencialmente el algoritmo de Martin en J.

Tenga en cuenta que 22 b.es 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
Jonás
fuente
Buen trabajo, amigo!
Patrick Roberts el