La secuencia de la curva del dragón

23

La secuencia de la curva del dragón (o la secuencia de plegado de papel normal) es una secuencia binaria. a(n)está dado por la negación del bit restante del 1 menos significativo de n. Por ejemplo, para calcular a(2136)primero convertimos a binario:

100001011000

Encontramos nuestro bit menos significativo

100001011000
        ^

Toma el bit a su izquierda

100001011000
       ^

Y devuelve su negación

0

Tarea

Dado un entero positivo como entrada, salida a(n). (Puede generar por entero o por booleano). Debe intentar que su código sea lo más pequeño posible medido por bytes.

Casos de prueba

Aquí están las primeras 100 entradas en orden

1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1
Asistente de trigo
fuente
99
El bit menos significativo 100001011000es a 0. ¿Te refieres a lo menos significativo 1?
dispersión

Respuestas:

16

Mathematica 25 Bytes

1/2+JacobiSymbol[-1,#]/2&

Otras formas de hacer esto:

56 bytes

(v:=1-IntegerDigits[#,2,i][[1]];For[i=1,v>0,i++];i++;v)&

58 bytes

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&
Kelly Lowder
fuente
3
¡Guauu! Una respuesta matemática y no solo está integrada. Tener un voto a favor!
KeyWeeUsr
2
Lo único que podría mejorar aún más esta respuesta es una explicación de por qué y cómo funciona. : P
Martin Ender
2
@MartinEnder arxiv.org/pdf/1408.5770.pdf Vea el comentario después del Ejemplo 13.
alephalpha
7

Python 3 , 22 21 bytes

1 byte gracias a ETHproductions.

lambda n:n&2*(n&-n)<1

Pruébalo en línea!

Bitwise aritmética ftw.

Monja permeable
fuente
2
"Puede salir por entero o por booleano", así que supongo que no necesita el 0+(...)?
Martin Ender
El orden de las operaciones aquí realmente me confunde. ¿Podría n&1ponerse entre paréntesis? ¿O es 1+(n^~-n)<1que se puede poner entre paréntesis? O es 1+(n^~-n)...
ETHproductions
oh dios que esto es lo que estaba buscando: ¡qué lindo!
HyperNeutrino
&tiene la menor prioridad, por lo que es1+(n^~-n)
Leaky Nun
Ah, encontré la tabla de precedencia. Ahora todo tiene sentido: P
ETHproductions
6

retina ,38 34 29 bytes

\d+
$*
+`^(1+)\1$|1111
$1
^1$

Pruébalo en línea!

A Martin y Leaky se les ocurrió esta idea, ¡con 5 bytes más de descuento!

Convierte la entrada en unaria, y luego divide progresivamente el número por 2. Una vez que ya no puede hacerlo de manera uniforme (es decir, el número es impar), elimina los parches de 4 de la entrada, calculando el resultado de la última operación mod 4 Finalmente, esto verifica si el resultado fue 1, lo que significa que el dígito a la izquierda del 1 bit menos significativo fue cero. Si eso es cierto, el resultado final es 1, de lo contrario es cero.

FryAmTheEggman
fuente
31 bytes (¿debería publicarlo yo mismo?)
Leaky Nun
Encontré una manera de evitar la conversión binaria completa y en su lugar simplemente dividir los factores de 2 y verificar la igualdad con 1 (mod 4): tio.run/##K0otycxL/…
Martin Ender
@MartinEnder esencialmente mi algoritmo ... con 2 bytes de descuento
Leaky Nun
@LeakyNun Oh, sí, ambos son la misma idea. Grandes mentes y esas cosas ...;)
Martin Ender
Lo editaré, pero si alguno de ustedes quiere publicarlo, lo revertiré, ya que probablemente no lo hubiera pensado yo mismo;)
FryAmTheEggman
6

Jalea , 5 bytes

&N&HṆ

Pruébalo en línea!

Cómo funciona

&N&HṆ  Main link. Argument: n

 N     Negate; yield -n.
&      Bitwise AND; compute n&-n.
       This yields the highest power of 2 that divides n evenly.
   H   Halve; yield n/2.
  &    Bitwise AND; compute n&-n&n/2. This rounds n/2 down if n is odd.
    Ṇ  Take the logical NOT of the result.
Dennis
fuente
4

Alice , 8 bytes

I2z1xnO@

Pruébalo en línea!

Toma la entrada como el punto de código de un carácter Unicode y genera el resultado como un byte 0x00 o 0x01 en consecuencia.

Para verificar, aquí hay una versión decimal de E / S de 12 bytes que usa exactamente el mismo algoritmo (solo E / S es diferente):

/o
\i@/2z1xn

Pruébalo en línea!

Si Alice era un lenguaje de golf y no requería E / S explícita y terminación del programa, esto se 2z1xnregistraría en solo 5 bytes ( ) superando tanto a 05AB1E como a Jelly.

Explicación

I    Read input.
2z   Drop all factors of 2 from the input, i.e. divide it by 2 as long
     as its even. This shifts the binary representation to the right
     until there are no more trailing zeros.
1x   Extract the second-least significant bit.
n    Negate it.
O    Output it.
@    Terminate the program.
Martin Ender
fuente
3

Sabio , 28 20 16 bytes

::-~^~-&:[?>]~-^

Pruébalo en línea!

Explicación

Este es un puerto de la respuesta Python de Leaky Nun. Desafortunadamente, no funciona en TIO porque la versión de TIO del intérprete está un poco desactualizada.

Comenzamos haciendo 3 copias de nuestra entrada con ::, luego disminuimos la copia superior en 1. Esto cambiará todos los bits hacia arriba hasta el primer 1. Luego lo enviaremos a otra copia de nuestra entrada. Dado que todos los bits hasta el primer 1 en nuestra entrada se han invertido, esto dará como resultado que todos esos bits sean 1 en el resultado. Si luego agregamos uno ~-al resultado, obtendremos un solo 1 en el lugar a la izquierda de nuestro menos significativo 1. Nosotros Y esto con la entrada para obtener ese bit de la entrada. Ahora tendremos 0si ese bit estaba apagado y una potencia de 2 si ese bit estaba encendido, podemos cambiar esto en un solo 1o 0con :[?>]. Una vez hecho esto, solo necesitamos negar el bit ~-^y listo.

Asistente de trigo
fuente
3

Haskell , 45 43 39 bytes

6 bytes guardados gracias a nimi

f x|d<-div x 2=[f d,mod(1+d)2]!!mod x 2

Pruébalo en línea!

Asistente de trigo
fuente
Puedes usar en divlugar de quot.
nimi
Aún mejor: divMod:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
Nombre del modelo
@nimi Ni siquiera entiendo cómo funciona eso. Probablemente deberías publicarlo tú mismo.
Wheat Wizard
Sigue siendo el mismo algoritmo, pero sólo una manera diferente para recoger la rama (de forma recursiva f llamar de nuevo vs caso base), así que no dude de edición en. |(d,m)<-divMod x 2Es un guardia de patrón para unen da div x 2y ma mod x 2. Usamos mpara indexar la lista de dos elementos [...,...]!!m. En caso de m==0que volvamos mod(1+d)2y en caso de m==1 f d.
nimi
1
Oh, lo siento, usted tiene que dar la vuelta a los elementos de la lista: [f d,mod(1+d)2]. Pruébalo en línea! .
nimi
3

Código de máquina x86, 17 16 15 bytes:

Asume un ABI donde los parámetros se insertan en la pila y el valor de retorno está en el ALregistro.

8B 44 24 04 0F BC C8 41 0F BB C8 0F 93 C0 C3

Esto se desmonta de la siguiente manera:

_dragoncurve:
  00000000: 8B 44 24 04        mov         eax,dword ptr [esp+4]
  00000004: 0F BC C8           bsf         ecx,eax
  00000007: 41                 inc         ecx
  00000008: 0F BB C8           btc         eax,ecx
  0000000B: 0F 93 C0           setae       al
  0000000E: C3                 ret
Govind Parmar
fuente
1
@ PeterTaylor Estoy contando el tamaño de la instrucción de la CPU en bytes para mi respuesta; Esa es una práctica bastante común en PPCG para respuestas de ensamblaje.
Govind Parmar
1
No podría decir qué tan común es, pero definitivamente está mal
Peter Taylor
1
No es solo pedante, tampoco tiene sentido. No hay distinción entre "código de máquina" y "código de ensamblaje" en lo que respecta a una computadora. La diferencia es meramente de interpretación. Asignamos mnemónicos a bytes de código de máquina para que sean más fáciles de leer para los humanos. En otras palabras, eliminamos los bytes para que sean más fáciles de entender.
Cody Gray
3
Eso es irrelevante, @Peter. El código de ensamblaje es solo una traducción legible por humanos del código de máquina. Son exactamente el mismo idioma, solo en dos formas / representaciones diferentes. No es diferente a TI BASIC, donde comúnmente se acepta que contamos tokens , en lugar de bytes de caracteres, porque así es como el sistema los almacena internamente. Lo mismo sería cierto con el lenguaje ensamblador: las instrucciones mnemotécnicas no se almacenan como caracteres individuales, sino que se representan como bytes de código de máquina equivalente.
Cody Gray
2
Además, en términos prácticos, ¿por qué alguien alguna vez enter ampliado mnemotécnicos lenguaje ensamblador en una competición código de golf, cuando se podría traducir en código máquina equivalente al 100%, donde la entrada se garantiza que sea más corto de forma gratuita? Solo eso hace una distinción entre los dos sin sentido, si no completamente absurdo.
Cody Gray
3

JavaScript (ES6), 17 14 bytes

f=
n=>!(n&-n&n/2)
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Editar: ahorré 3 bytes al portar la respuesta de @ Dennis una vez que noté que la salida booleana era aceptable.

Neil
fuente
3

C (gcc) , 20 bytes

f(n){n=!(n&-n&n/2);}

Pruébalo en línea!

Dennis
fuente
Esto en realidad no "funciona"; confía en una peculiaridad del generador de código para una versión particular del compilador que apunta a una arquitectura particular, donde los cálculos intermedios se realizan en el mismo registro que se utiliza para los valores de retorno. Habilitar cualquier tipo de optimización, cambiar la arquitectura de destino o usar una versión diferente de GCC lo romperá. También podría decir "la basura en mi pila contiene la salida correcta cuando hay luna llena el 13 de octubre".
Cody Gray
Si bien todo lo que dice es verdadero y un código como este nunca se usará en el código de producción, definimos los idiomas por sus implementaciones para los propósitos del código golf. Sin indicadores adicionales, esto funciona en todas las versiones recientes de gcc y tcc, y solo tiene que funcionar en una versión para que se considere válido.
Dennis
"definimos los idiomas por sus implementaciones a los efectos del código golf" Espera, ¿qué? Entonces, ¿cada indicador del compilador y cada versión de GCC define un idioma diferente? Te das cuenta de que es una locura, ¿verdad? El estándar del lenguaje C es lo que define el lenguaje.
Cody Gray
Aqui no. Si hubiera un estándar C pero ninguna implementación, ni siquiera lo consideraríamos un lenguaje. Como dije antes, el compilador define el lenguaje . Como resultado, se permite confiar en un comportamiento indefinido . Un conjunto diferente de indicadores no se considera un idioma diferente, pero a menos que los agregue a su conteo de bytes, todas las respuestas usan indicadores de compilación estándar.
Dennis
Guau. Eso es una locura. Es decir, podría entender si usted decía que definido por la implementación se permite comportamiento, pero un comportamiento indefinido es no definido por la aplicación. Está literalmente indefinido. La implementación puede hacer cosas al azar cada vez. Y esta noción de "banderas de compilación estándar" es algo que acabas de inventar. Mis banderas de compilación estándar incluyen varias que rompen su código. Y apenas creo que el optimizador no sea estándar. Bueno, claramente este sitio no es para mí.
Cody Gray
3

INTERCAL , 50 bytes

DOWRITEIN.1DO.1<-!?1~.1'~#1DOREADOUT.1PLEASEGIVEUP

Los operadores unarios de INTERCAL son bastante adecuados para esto, así que decidí escribir mi primera publicación.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP
Bernd Fischer
fuente
3

Haskell , 33 bytes

g~(a:b:c)=1:a:0:b:g c
d=g d
(d!!)

Pruébalo en línea!

Utiliza indexación 0.

Anders Kaseorg
fuente
1
¿Qué hace el ~en este contexto? Entiendo que es una perezosa, pero ¿por qué necesitas una perezosa?
Wheat Wizard
2

Jalea , 7 6 bytes

1 byte gracias a Erik the Outgolfer.

Bt0ṖṪṆ

Pruébalo en línea!

Programas más largos

Monja permeable
fuente
Hmm ... bueno, puedes hacer ṖṪṆ(como mi respuesta eliminada) en lugar de ṫ-ḄỊ.
Erik the Outgolfer
1
Otro para su lista de 7 bytes:BUḌDḊḢ¬
steenbergh
2

,,, , 10 9 bytes

::0-&2*&¬

Explicación

Tome la entrada como 3 por ejemplo.

::0-&2*&1≥
               implicitly push command line argument       [3]
::             duplicate twice                             [3, 3, 3]
  0            push 0 on to the stack                      [3, 3, 3, 0]
   -           pop 0 and 3 and push 0 - 3                  [3, 3, -3]
    &          pop -3 and 3 and push -3 & 3 (bitwise AND)  [3, 1]
     2         push 2 on to the stack                      [3, 1, 2]
      *        pop 2 and 1 and push 2 * 1                  [3, 2]
       &       pop 2 and 3 and push 2 & 3                  [2]
        ¬      pop 2 and push ¬ 2 (logical NOT)            [0]
               implicit output                             []
totalmente humano
fuente
2

Octava , 34 bytes

@(x)~(k=[de2bi(x),0])(find(k,1)+1)

Pruébalo en línea!

Explicación:

@(x)                               % Anonymous function taking a decimal number as input
    ~....                          % Negate whatever comes next
     (   de2bi(x)   )              % Convert x to a binary array that's conveniently 
                                   % ordered with the least significant bits first
        [de2bi(x),0]               % Append a zero to the end, to avoid out of bound index
     (k=[de2bi(x),0])              % Store the vector as a variable 'k'
                     (find(k,1)    % Find the first '1' in k (the least significant 1-bit)
                               +1  % Add 1 to the index to get the next bit
     (k=[de2bi(x),0])(find(k,1)+1) % Use as index to the vector k to get the correct bit
Stewie Griffin
fuente
¿Cómo es que nunca oí hablar de de2bi ...: O
Sanchises
1

Sumisión:

Python 2 , 41 39 bytes

x=input()
while~-x&1:x/=2
print 1-x/2%2

Pruébalo en línea!

-2 bytes gracias a FryAmTheEggman

Solución inicial

Python 2 , 43 bytes

lambda x:1-int(bin(x)[bin(x).rfind('1')-1])

Pruébalo en línea!

Hiperneutrino
fuente
Entonces, ¿cuál es tu presentación?
Leaky Nun
@LeakyNun El primero porque es más corto; El segundo fue mi presentación original. ¿Debo publicarlos por separado?
HyperNeutrino
~-x&1funciona para la condición while, creo.
FryAmTheEggman
(Olvidé el nombre de usuario); Rechacé su edición porque no se recomienda editar el código de otras personas en PPCG. Puede publicar sugerencias (por cierto, gracias @FryAmTheEggman), pero no realice ediciones de golf. ¡Gracias!
HyperNeutrino
@StewieGriffin Ah sí, gracias. Lamentablemente, no puedo hacer ping al usuario porque la edición fue rechazada.
HyperNeutrino
1

MATL , 11 10 bytes

t4*YF1)Z.~

Pruébalo en línea! O vea las primeras 100 salidas .

Explicación

t    % Implicit input. Duplicate
4*   % Multiply by 4. This ensures that the input is a multiple of 2, and
     % takes into account that bit positions are 1 based
YF   % Exponents of prime factorization
1)   % Get first exponent, which is that of factor 2
Z.   % Get bit of input at that (1-based) position
~    % Negate. Implicit display
Luis Mendo
fuente
1

Befunge-98 , 19 bytes

&#;:2%\2/\#;_;@.!%2

Pruébalo en línea!

&#                       Initial input: Read a number an skip the next command
  ;:2%\2/\#;_;           Main loop: (Direction: East)
   :2%                    Duplicate the current number and read the last bit
      \2/                 Swap the first two items on stack (last bit and number)
                          and divide the number by two => remove last bit
         \                swap last bit and number again
          #;_;            If the last bit is 0, keep going East and jump to the beginning of the loop
                          If the last bit is 1, turn West and jump to the beginning of the loop, but in a different direction.
&#;           @.!%2      End: (Direction: West)
&#                        Jump over the input, wrap around
                 %2       Take the number mod 2 => read the last bit
               .!         Negate the bit and print as a number
              @          Terminate
ovs
fuente
1

SCALA, 99 (78?) Caracteres, 99 (78?) Bytes

if(i==0)print(1)else
print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

donde iesta la entrada

Como puede ver, guardo 21 bytes si no me ocupo del cero (como lo hizo el autor en su caso de prueba):

print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

Este es mi primer codegolf, así que espero haberlo hecho bien :)

Pruébalo en línea! Aunque es bastante largo para calcular jajaja.

V. Courtois
fuente
Bienvenido al sitio!
DJMcMayhem
1

Java 8, 17 bytes

n->(n&2*(n&-n))<1

Puerto sencillo de la respuesta Python 3 de LeakyNun . No estoy lo suficientemente familiarizado con las operaciones bit a bit y la precedencia del operador para ver una solución más corta; tal vez hay una manera de evitar la parentetesis extra?

Bromista alegre
fuente
0

Japt , 10 8 9 bytes

!+¢g¢a1 É

Pruébalo en línea!

Explicación

!+¢   g    a1 É
!+Us2 gUs2 a1 -1 # Implicit input (U) as number
!+               # Return the boolean NOT of
      g          #   the character at index
       Us2       #     the input converted to binary
           a1    #     the index of its last 1
              -1 #     minus 1
      g          #   in string
  Us2            #     the input converted to binary
Luke
fuente
Esto devuelve falsetodo porque el carácter (0 o 1) siempre es una cadena.
Shaggy
Vaya, debería haber notado que ... Solucionado ahora
Luke
Parece que falla por1 ahora.
Shaggy
0

JavaScript (ES6), 53 34 bytes

a=>eval("for(;~a&1;a/=2);~a>>1&1")
Luke
fuente
42 bytes:a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
Shaggy
Ya encontré una solución (matemática) más corta ...
Luke
Agradable :) ¿Te importa si publico ese byte 42?
Shaggy
@ Shaggy, no, para nada
Luke
0

Chip , 93 bytes

HZABCDEFG,t
 ))))))))^~S
H\\\\\\\/v~a
G\\\\\\/v'
F\\\\\/v'
E\\\\/v'
D\\\/v'
C\\/v'
B\/v'
A/-'

Toma la entrada como pequeños bytes endian. (El TIO tiene un poco de python que hace esto por usted). Da salida como 0x0o0x1 . (El TIO usa xxd para inspeccionar el valor).

Pruébalo en línea!

¿Cómo se hace esto?

El chip mira la entrada de un byte a la vez, por lo que el manejo de la entrada multibyte agrega algo de volumen, pero no tanto como temía.

Vamos a entrar en eso:

HZABCDEFG

Estos son HZ, bit alto del byte anterior (si había uno), y A- G, los siete bits más bajos del byte actual. Estos se utilizan para localizar el bit de ajuste más bajo del número.

        ,t
))))))))^~S

Cuando se encuentra el bit de ajuste más bajo, tenemos algunas cosas que hacer. Este primer fragmento dice "si tenemos un bit establecido (el )'s), entonces deje de Spresionar la salida y termine después de imprimir la respuesta.

H\\\\\\\/v~a
G\\\\\\/v'
...
A/-'

Cualquier parte del byte actual (A - H) solo está precedido por un grupo de ceros y luego uno ( \y /: estos miran los bits directamente al norte de ellos; podemos confiar en que todos los bits anteriores eran cero) se pasan a los cables en la derecha ( v, ', ...), a continuación, el que sea valor se se invierte y se da como el bit bajo de salida ( ~a).

Phlarx
fuente