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
0
o 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á
0
s 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
1
sy0
s - 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
1
y0
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 código de golf , ¡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.
fuente
0011
para 8Respuestas:
Jalea ,
108 bytesGracias a Dennis por guardar 2 bytes.
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:
Donde
[]
están los soportes de piso. Considere el ejemplo de44
cuya representación binaria es101100
. 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úmerosObserve que la
n
columna th contiene los primerosn
bits. 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:
Afortunadamente, Jelly parece poner las entradas automáticamente al tratar de XOR. De todos modos, aquí está el código:
fuente
Ḟ$
; operadores bit a bit emitidos a int .JavaScript (ES6), 58 bytes
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.
fuente
?
en/.?(?=10*$)/
realmente necesario? Oh no importa. Sí lo es. :-)Perl,
2725 bytesIncluye +1 para
-p
Dar cadena de entrada en STDIN, p. Ej.
gray.pl
: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.
fuente
\G
realmente te facilita las cosas!\K
hace las cosas aún más fáciles para usted.\G
implementación también.Haskell,
118115108bytesPruébalo en Ideone.
Enfoque ingenuo:
g
genera el conjunto de todos los códigos grises con longitudn
(con relleno de 0),f
llamadasg
conlength(input)+1
, elimina todos los elementos hasta que0<inputstring>
se encuentra y devuelve el siguiente elemento (truncando un posible líder0
).fuente
MATL , 18 bytes
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.fuente
CJam (19 bytes)
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
Al trabajar únicamente con el conjunto de bits, creo que es necesario revertirlo: trabajar con el extremo izquierdo
1
es mucho más fácil que el extremo derecho. Lo mejor que he encontrado hasta ahora es (24 bytes):Enfoque alternativo (19 bytes)
Esto convierte de código gris a índice, incrementa y vuelve a convertir a código gris.
fuente
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).
fuente
--harmony
agregarse para bytes de penalización para tener acceso a la optimización de recursión de llamadas de cola, que parece ser posible aquí.Retina, 25 bytes
Estoy seguro de que debería haber una mejor manera de hacer esto ...
fuente
^
?05AB1E , 12 bytes
Usos codificación CP-1252 .
Pruébalo en línea!
Explicación
Ejemplo para la entrada 1011 .
fuente
Python 2.7, 68 caracteres
Python 3, 68 caracteres
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
0b
prefijo booleano.fuente
def f(s):
y (suponiendo Python 2) otro utilizando enprint
lugar dereturn
.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álidalong
en lugar deint
podría resolver el problema.C ++, 205 bytes
Descripción: los números pares tienen un número par de unos. La variable
z
cuenta unos; siz
es par (z mod 2 = z%2 = 0
- otra rama), modifique el último bit; siz
es 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.
fuente
Lote,
199197 bytesLee 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.s
por lo tanto, contiene el prefijo de paridad par yr
el resto de la cadena.s
se establece en cero si estaba en blanco para que su último dígito se pueda alternar, y luego todo se concatena.fuente
En realidad,
201913 bytesBasado 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!
Ungolfing
fuente
J, 38 bytes
Pruébalo en línea!
Este es esencialmente el algoritmo de Martin en J.
Tenga en cuenta que
22 b.
es XOR.fuente