La expansión binaria binaria

9

Normalmente, descomponemos un número en dígitos binarios asignándolo con potencias de 2, con un coeficiente de 0o 1para cada término:

25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1

La elección de 0y 1es ... no muy binaria. Realizaremos la verdadera expansión binaria expandiéndonos con potencias de 2, pero con un coeficiente de 1o en su -1lugar:

25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1

Ahora esto parece binario.

Dado cualquier número positivo, debería ser trivial ver que:

  • Cada número impar tiene infinitas expansiones binarias verdaderas
  • Cada número par no tiene expansiones binarias verdaderas

Por lo tanto, para que una verdadera expansión binaria esté bien definida, requerimos que la expansión sea la menor , es decir, con la longitud más corta.


Dado cualquier número entero positivo e impar n, devuelve su verdadera expansión binaria, del dígito más significativo al dígito menos significativo (o en orden inverso).

Reglas:

  • Como se trata de , debe intentar hacerlo en el menor recuento de bytes posible. Las construcciones están permitidas.
  • Cualquier salida que pueda representar y enumerar los coeficientes es aceptable: una matriz, una cadena de coeficientes con separadores, etc.
  • Se aplican lagunas de golf estándar.
  • Su programa debería funcionar para valores dentro del tamaño entero estándar de su idioma.

Casos de prueba

25 -> [1,1,1,-1,-1]
47 -> [1,1,-1,1,1,1]
1 -> [1]
3 -> [1,1]
1234567 -> [1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1]
Voile
fuente
Relacionado pero bastante diferente.
Giuseppe
44
Algoritmo simple: Convertir a base 2, reemplazar 0's con -1's, poner el LSD al frente.
Josiah Winslow
Voile: no estaba explicando los votos negativos, solo describía un algoritmo para las personas que tienen comandos de conversión de bases en su idioma.
Josiah Winslow
Dado que está tan interesado en ser verdaderamente binario, ¿podemos devolver el valor como bits empaquetados con el valor posicional habitual pero la nueva interpretación de los dos estados? es decir, eléctricamente es solo alto o bajo voltaje (o lo que sea), y no es mi culpa si los depuradores estándar imprimen en 0lugar del estado -1de bajo voltaje. La persona que llama que recibe los bits sabe lo que significan. (Todavía es un ejercicio de manipulación de bits no trivial, ya que una rotación hacia la derecha solo funciona si tiene 32 bits significativos. Por ejemplo, un número de 5 bits necesita un ancho de rotación de 5)
Peter Cordes
¿La salida necesita incluir separadores? ¿Es 111-1-1una salida válida para 25?
Oliver

Respuestas:

7

Japt , 6 bytes

¤é r0J

Pruébalo en línea!

Explicación:

¤é r0J  // Test input:                  25
¤       // Binary the input:            11001
 é      // Rotate 1 chars to the right: 11100
   r0J  // Replace 0s with -1:          111-1-1
Oliver
fuente
1
Ah, la rotación; que es la razón por que no funcionaba para mí.
Shaggy
2
¿¿¿Girar??? Dagnabbit.
Giuseppe
3

Pyth ,  12  11 bytes

|R_1.>jQ2 1

Pruébalo aquí!


¿Cómo?

| R_1.> JQ2 1 Programa completo.

      jQ2 Convierta la entrada a una lista binaria.
     .> 1 Gire cíclicamente la lista anterior 1 lugar a la derecha.
| R_1 Sustituye 0 con -1.
               Salida implícita.

En primer lugar, nos damos cuenta de que la tarea es simplemente "sustituir la 0s en la escritura binaria con -1sy desplazarse a la derecha por 1 lugar". - Eso es exactamente lo que debemos hacer! La conversión binaria nos da una lista de 0sy 1s. Todo lo que hay que hacer aquí es encontrar una manera de convertir golfy 0a -1. El operador bit a bit |(bitwise OR) es nuestro amigo. El mapa sobre la representación binaria cambió con |y -1. Si el número actual es 0, se convierte a -1.

Sr. Xcoder
fuente
No creo que haya una mejor manera. ;)
Josiah Winslow
@JosiahWinslow sí ... Tratando de encontrarlo
Sr. Xcoder
Hm? El algoritmo parece óptimo, tal vez sea porque no conozco a Pyth.
Josiah Winslow
@JosiahWinslow encontró la mejor manera. Mejor forma sintáctica, no mejor forma algorítmica.
Sr. Xcoder
@ Mr.Xcoder Y ahora realmente no hay ninguno al menos para mí.
Erik the Outgolfer
3

JavaScript (ES6), 35 34 bytes

f=n=>n?[...f(n>>=1),!n|n%2||-1]:[]

Fragmento de prueba

ETHproducciones
fuente
2

Perl 6 , 72 bytes

Seguramente hay una mejor manera, pero esto es lo que tengo ...

->$a {grep {$a==[+] @^a.reverse Z+< ^∞},[X] (1,-1)xx $a.base(2).chars}

Pruébalo en línea!

Explicación : Es una función que toma un argumento ( ->$a). Primero obtenemos el número de coeficientes necesarios ( $a.base(2).chars= número de caracteres en la representación de base 2), luego hacemos un producto cartesiano ( X) de tantos pares (1,-1). (Los [X]medios: reduzca la siguiente lista con X). Entonces obtenemos una lista de todas las combinaciones posibles de 1s y -1s. Luego filtramos ( grep) solo las listas que codifican el número dado$a . Solo hay uno, por lo que obtenemos una lista de una lista con los coeficientes.

El bloque grep hace esto: toma su argumento como una lista ( @^a), lo invierte y lo comprime con una lista infinita 0,1,2,...utilizando el operador "desplazamiento de bit izquierdo" +<. La compresión se detiene tan pronto como se agota la lista más corta (¡bueno para nosotros!) Luego sumamos todos los resultados y los comparamos con el número dado. Tuvimos que usar .reverseporque el OP exige que los coeficientes estén en el orden de más significativo a menos significativo.

Ramillies
fuente
1

05AB1E , 6 5 bytes

bÁ0®:

Pruébalo en línea!

Okx
fuente
D<puede ser ®( ®es el valor predeterminado -1).
Erik the Outgolfer
@EriktheOutgolfer ¡Gracias! No me di cuenta de eso.
Okx
1

J, 11 bytes

1-~2*_1|.#:

Pruébalo en línea!

Gracias a @JosiahWinslow por el algoritmo.

¿Alguna idea sobre hacer la conversión más corta? Mis pensamientos son usar !.-fit (nvm, solo cambia la tolerancia de la conversión).

Usar {-take es más largo por 1 personaje.

_1 1{~_1|.#:
col
fuente
1

Java 8, 101 bytes

n->{String s=n.toString(n,2);return(s.charAt(s.length()-1)+s.replaceAll(".$","")).replace("0","-1");}

Puerto de @Oliver Japt respuesta 's , con unos cuantos más bytes ..;)

Definitivamente se puede jugar al golf utilizando un enfoque matemático en lugar de este enfoque de cadena.

Explicación:

Pruébalo aquí.

n->{                             // Method with Integer parameter and String return-type
  String s=n.toString(n,2);      //  Convert the Integer to a binary String
  return(s.charAt(s.length()-1)  //  Get the last character of the binary String
    +s.replaceAll(".$","")       //   + everything except the last character
   ).replace("0","-1");          //  Then replace all zeroes with -1, and return the result
}                                // End of method
Kevin Cruijssen
fuente
1

R , 90 88 46 bytes

function(n)c((n%/%2^(0:log2(n))%%2)[-1],1)*2-1

Pruébalo en línea!

Implementa el algoritmo de Oliver , pero devuelve los dígitos en orden inverso. Como estamos garantizados de que nnunca es par, el bit menos significativo (el primero) es siempre 1, por lo que lo eliminamos y agregamos una 1al final para simular la rotación en R. Gracias a Shaggy por ayudarme a arreglar mis matemáticas .

Simplemente colocando rev( )las llamadas de función en el pie de página debería devolver los valores en el mismo orden.

respuesta original, 88 bytes:

function(n,b=2^(0:log2(n)))(m=t(t(expand.grid(rep(list(c(-1,1)),sum(b|1))))))[m%*%b==n,]

Función anónima; devuelve los valores en orden inverso con los nombres de columna adjuntos.

Pruébalo en línea!

Explicación:

function(n){
 b <- 2^(0:log2(n))         # powers of 2 less than n
 m <- expand.grid(rep(list(c(-1,1)),sum(b|1))) # all combinations of -1,1 at each position in b, as data frame
 m <- t(t(m))               # convert to matrix
 idx <- m%*%b==n            # rows where the matrix product is `n`
 m[idx,]                    # return those rows
}
Giuseppe
fuente
No consideraría que la salida sea válida; sugiera pedir confirmación al autor del desafío.
Shaggy
El orden inverso de @Shaggy está explícitamente permitido: from the most significant digit to the least significant digit (or in reversed order).por lo tanto, esto debería ser perfectamente aceptable.
Giuseppe
1
Orden invertido , no signos invertidos. Lo que significa salida válida para 25, por ejemplo, sería [1,1,1,-1,-1]o [-1,-1,1,1,1].
Shaggy
1
@ Shaggy ah, tienes razón, ¡acabo de hacer mal las matemáticas! debería ser en 2*bits - 1lugar de 1-2*bits. Gracias.
Giuseppe
0

CJam, 12 bytes

Un puerto de mi respuesta Golfscript.

qi2b{_+(}%)\
Josiah Winslow
fuente
0

Golfscript, 14 13 14 bytes

-1 byte porque olvidé que %existía. +1 byte porque también olvidé que input es una cadena.

~2base{.+(}%)\
Josiah Winslow
fuente
1
Si va a suponer que la entrada viene como un número entero, debe envolver el código {}para convertirlo en un bloque. Los programas completos solo pueden obtener entradas como cadenas.
Peter Taylor
¿Um que? Quise decir, el número se empuja como un entero, en lugar de una cadena que contiene un número.
Josiah Winslow
En ese caso, su respuesta no es un programa completo, por lo que debe ser una "función" o, en el caso de GolfScript, un bloque. Por lo tanto, es {2base{.+(}%\}por 15 bytes. Del mismo modo, su respuesta CJam.
Peter Taylor
Este es un programa completo. Las entradas en Golfscript se insertan implícitamente en la pila al comienzo del programa, y ​​las entradas en CJam se especifican antes de la ejecución y se accede a ellas con el comando q.
Josiah Winslow
Tengo cierta familiaridad con GolfScript . ( Y CJam ). Si desea afirmar que es un programa completo, debe agregarle el prefijo ~.
Peter Taylor