Introducción (puede ser ignorado)

Poner todos los números positivos en su orden regular (1, 2, 3, ...) es un poco aburrido, ¿no? Así que aquí hay una serie de desafíos en torno a las permutaciones (reorganizaciones) de todos los números positivos. Este es el segundo desafío de esta serie. El primer desafío se puede encontrar aquí .

En este desafío, usamos códigos grises para reorganizar los números naturales. Un código gris, o "código binario reflejado" es una codificación binaria de tal manera que dos valores sucesivos difieren en un solo bit. Una aplicación práctica de esta codificación es usarla en codificadores rotativos , de ahí mi referencia a "Turn My Way" .

Tenga en cuenta que esta codificación deja cierto grado de libertad. Por ejemplo, después del 1100 binario, hay cuatro posibles códigos siguientes: 1101, 1110, 1000 y 0100. Es por eso que definiré $a(n)$ como el valor más pequeño, no utilizado previamente, que difiere solo un carácter en la codificación binaria. Esta secuencia corresponde con A163252 .

Como se trata de un desafío de "secuencia pura", la tarea es generar $a(n)$ para un $n$ dado como entrada, donde $a(n)$ es A163252 .

Tarea

Dada una entrada entera $n$ , salida $a(n)$ en formato entero ( no en formato binario).

$a(n)$ se define como el número entero menos positivo que no aparece antes en la secuencia, de modo que$a(n-1)$ y$a(n)$ difieren en un solo bit cuando se escriben en binario.

Nota: aquí se supone una indexación basada en 1; puede usar indexación basada en 0, entonces $a(0) = 1; a(1) = 3$ , etc. Mencione esto en su respuesta si elige usar esto.

Casos de prueba

Input | Output
--------------
1     | 1
5     | 4
20    | 18
50    | 48
123   | 121
1234  | 1333
3000  | 3030
9999  | 9997

Reglas

• La entrada y la salida son enteros (su programa al menos debe admitir entradas y salidas en el rango de 1 hasta 32767)
• La entrada no válida (0, flotantes, cadenas, valores negativos, etc.) puede generar salidas imprevistas, errores o un comportamiento (no) definido. En A163252 , $a(0)$ se define como 0. Para este desafío, lo ignoraremos.
• Se aplican las reglas de E / S predeterminadas .
• Las lagunas predeterminadas están prohibidas.
• Este es el código de golf , por lo que gana la respuesta más corta en bytes

Nota final

Consulte las siguientes preguntas relacionadas (pero no iguales) de PP&CG:

• Encontrar el siguiente código Gray (entrada y salida en binario)
• Genere todos los códigos grises de longitud n

Stax , 19 17 bytes

êÑ{╚α8è╙mc┼σ▀»É▲ü

Ejecutar y depurarlo

Deja de funcionar en algún momento después del dominio especificado debido a la iteración del índice de bits codificado. (32767)

Desempaquetado, sin golf y comentado, se ve así.

z0,         push an empty array, literal zero, and the input, in that order
             - the zero represents the last calculated value in the sequence
             - the array contains all the previous ones
D           repeat the rest of the program n times (from input)
  +         append the last calculated value to the array
  17r       [0 .. 16] (these are the bit indices necessary to cover the input range)
  {|2nH|^m  calculate candidate values; previous value with each of these bits toggled 
  n-        remove all values previously calculated
  |m        keep the minimum candidate remaining

Ejecute este

JavaScript (ES6), 65 bytes

1 indexado.

n=>{for(o=p=[k=1];o[k]|~-(i=p^k)&i?k++:k=o[p=k]=!!n--;);return p}

Pruébalo en línea!

Comentado

n => {                  // n = index of requested term
  for(                  // for loop:
    o =                 //   o = storage object for the terms of the sequence
    p =                 //   p = last term found in the sequence
      [k = 1];          //   k = current term
    o[k] |              //   if k was already encountered
    ~-(i = p ^ k) & i ? //   or (p XOR k) has more than 1 bit set:
      k++               //     increment k
    :                   //   else:
      k = o[p = k]      //     set o[k], set p to k
        = !!n--;        //     stop if n is equal to 0 or set k to 1; decrement n
  );                    // end of for()
  return p              // return p
}                       // end

Gelatina , 26 20 bytes

ṀBLŻ2*^1ị$ḟ⁸Ṃ;
0Ç⁸¡Ḣ

Pruébalo en línea!

Un programa completo que toma n como argumento único. Funciona para todos los casos de prueba. También tenga en cuenta que, aunque no es obligatorio, maneja n = 0.

Explicación

Enlace auxiliar: encuentre el próximo término y anteponga

Ṁ              | maximum of list so far
 B             | convert to binary
  L            | number of binary digits
   Ż           | 0..above number
    2*         | 2 to the power of each of the above
      ^        | exclusive or with...
       1ị$     | ... the most recent term in the list so far
          ḟ⁸   | filter out anything used already
            Ṃ  | find the minimum
             ; | prepend to existing list

Enlace principal

0              | start with zero
 Ç             | call the above link
  ⁸¡           | and repeat n times
    Ḣ          | take the last term added

Java (JDK) , 142 138 124 123 132 130 98 bytes

• aumentado para tener en cuenta la importación, guardado un byte gracias a @ kevin-cruijssen
• cambió la colección a la matriz int gracias a @ olivier-grégoire

n->{int s[]=new int[9*n],j,k=0;for(;n-->0;s[k=j]++)for(j=0;s[++j]>0|n.bitCount(j^k)>1;);return k;}

Pruébalo en línea!

Python 2 , 81 bytes

Indexación basada en 1

l=[0];p=0
exec"n=0\nwhile(p^n)&(p^n)-1or n in l:n+=1\np=n;l+=p,;"*input()
print p

Pruébalo en línea!

Python 2 , 79 bytes

Esto lleva mucho tiempo (9999 no se terminó después de ejecutarse localmente durante 7 minutos)

l={0};p=0;n=input()
exec'p=min({p^2**k for k in range(n)}-l);l|={p};'*n
print p

Pruébalo en línea!

Wolfram Language (Mathematica) , 74 bytes

Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&

Pruébalo en línea!

APL (Dyalog Extended) , 46 bytes

{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}

Pruébalo en línea!

Carbón , 65 bytes

≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

≔⁰θ

Inicializa el resultado a 0.

ＦＮ«

nTiempos de bucle .

⊞υθ

Guarde el resultado anterior para que no lo usemos nuevamente.

≔¹ηＷ¬‹θ⊗η≦⊗η

Encuentra el bit más alto en el resultado anterior.

Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η

Si bien ese bit es mayor que 1, si el bit se establece en el resultado anterior, intente restar ese bit para ver si el resultado es un resultado invisible. Esto asegura que los resultados potenciales se prueben en orden ascendente de valor.

Ｗ№υ⁻｜θη＆θη≦⊗η

Ahora intente XORing ese bit con el resultado anterior, duplicando el bit hasta que se encuentre un resultado invisible. Esto maneja los casos en que se necesita establecer un bit, nuevamente en orden ascendente de valor, pero también el caso en que se necesita alternar el bit menos significativo, que el bucle anterior no se molesta en probar (porque es más golfista probar eso aquí). Si el ciclo anterior encontró un resultado invisible, este ciclo nunca se ejecuta; si no fuera así, este bucle volverá a probar esos resultados inútilmente.

≔⁻｜θη＆θηθ

Actualice el resultado realmente haciendo XOR al bit con él.

»Ｉθ

Salida del resultado final al final del ciclo.

05AB1E , 21 20 18 bytes

ÎFˆ∞.Δ¯θy^bSO¯yå_*

Bastante ineficiente, por lo que cuanto mayor es la entrada, más tiempo se tarda en obtener el resultado. Sin 0embargo, también funciona para la entrada .

$n$

Explicación:

Î                # Push 0 and the input
 F               # Loop the input amount of times:
  ˆ              #  Pop the current number and add it to the global_array
  ∞.Δ            #  Inner loop starting at 1 to find the first number which is truthy for:
     ¯θy^        #   XOR the last number of the global_array with the loop-number `y`
         b       #   Convert it to binary
          SO     #   Sum it's binary digits
     ¯yå_        #   Check if the loop-number `y` is NOT in the global_array yet
            *    #   Multiply both (only if this is 1 (truthy), the inner loop will stop)
                 # (after the loops, output the top of the stack implicitly)

Haskell , 101 bytes

import Data.Bits
(u!n)0=n
(u!n)m|q<-minimum[x|r<-[0..62],x<-[xor(2^r)n],notElem x u]=(n:u)!q$m-1
[]!0

Pruébalo en línea!

Parece una pena incurrir en una importación solo por xor, pero aún no he encontrado una buena solución. También me pregunto si hay una mejor manera de expresar el ciclo.

R , 90 bytes

function(n){A=1
while(sum(A|1)<n)A=c(min((x=bitwXor(A[1],2^(0:30)))[x>0&!x%in%A]),A)
A[1]}

Pruébalo en línea!