Introdução (pode ser ignorado)

Colocar todos os números positivos em sua ordem regular (1, 2, 3, ...) é um pouco chato, não é? Então, aqui está uma série de desafios em torno de permutações (reorganizações) de todos os números positivos. Este é o segundo desafio desta série. O primeiro desafio pode ser encontrado aqui .

Neste desafio, usamos os códigos Gray para reorganizar os números naturais. Um código Gray ou "código binário refletido" é uma codificação binária de tal maneira que dois valores sucessivos diferem em apenas um bit. Uma aplicação prática dessa codificação é usá-la em codificadores rotativos , daí a minha referência a "Turn My Way" .

Observe que essa codificação deixa algum grau de liberdade. Por exemplo, após o binário 1100, existem quatro códigos possíveis: 1101, 1110, 1000 e 0100. É por isso que definirei $a(n)$ como o menor valor não usado anteriormente que difere apenas um caractere na codificação binária. Esta sequência corresponde a A163252 .

Como esse é um desafio de "sequência pura", a tarefa é gerar $a(n)$ para um dado $n$ como entrada, onde $a(n)$ é A163252 .

Tarefa

Dada uma entrada inteira $n$ , produza $a(n)$ no formato inteiro ( não no formato binário).

$a(n)$ é definido como o número inteiro menos positivo que não ocorre anteriormente na sequência, de modo que$a(n-1)$ e$a(n)$ diferem em apenas um bit quando escritos em binário.

Nota: a indexação baseada em 1 é assumida aqui; você pode usar a indexação baseada em 0; portanto, $a(0) = 1; a(1) = 3$ , etc. Por favor mencione isso na sua resposta se você optar por usá-lo.

Casos de teste

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

Regras

• Entrada e saída são números inteiros (seu programa deve, pelo menos, suportar entrada e saída no intervalo de 1 a 32767)
• Entrada inválida (0, valores flutuantes, seqüências de caracteres, valores negativos etc.) pode levar a resultados imprevisíveis, erros ou comportamento (não) definido. No A163252 , $a(0)$ é definido como 0. Para esse desafio, ignoraremos isso.
• Padrão Aplicam- se as regras de E / S .
• As brechas padrão são proibidas.
• Isso é código-golfe , então as respostas mais curtas em bytes ganham

Nota final

Consulte as seguintes perguntas relacionadas (mas não iguais) a PP&CG:

• Localizando o próximo código Gray (entrada e saída em binário)
• Gere todos os códigos Gray de comprimento n

Stax , 19 17 bytes

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

Execute e depure

Ele pára de funcionar em algum momento após o domínio especificado devido à iteração do índice de bits codificado. (32767)

Descompactado, não jogado e comentado, é assim.

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

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

Experimente online!

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

Geléia , 26 20 bytes

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

Experimente online!

Um programa completo que aceita n como argumento único. Funciona para todos os casos de teste. Observe também que, embora não seja obrigatório, ele lida com n = 0.

Explicação

Link auxiliar: encontre o próximo termo e adicione-o

Ṁ              | 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

Link 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 contabilizar a importação, salvou um byte graças a @ kevin-cruijssen
• coleção comutada para array int graças 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;}

Experimente online!

Python 2 , 81 bytes

Indexação baseada em 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

Experimente online!

Python 2 , 79 bytes

Isso leva muito tempo (o 9999 não foi concluído após a execução local por 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

Experimente online!

Wolfram Language (Mathematica) , 74 bytes

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

Experimente online!

APL (Dyalog Extended) , 46 bytes

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

Experimente online!

Carvão vegetal , 65 bytes

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

Experimente online! Link é a versão detalhada do código. Explicação:

≔⁰θ

Inicialize o resultado para 0.

ＦＮ«

nTempos de loop .

⊞υθ

Salve o resultado anterior para não usá-lo novamente.

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

Encontre o bit mais alto no resultado anterior.

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

Enquanto esse bit for maior que 1, se o bit estiver definido no resultado anterior, tente subtrair esse bit para ver se o resultado é um resultado invisível. Isso garante que os resultados potenciais sejam tentados em ordem crescente de valor.

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

Agora tente XORing esse bit com o resultado anterior, dobrando o bit até encontrar um resultado invisível. Isso lida com os casos em que um bit precisa ser definido, novamente em ordem crescente de valor, mas também o caso em que o bit menos significativo precisa ser alternado, que o loop anterior não se preocupa em testar (porque é mais experiente em testar isso aqui). Se o loop anterior encontrou um resultado invisível, ele nunca será executado; caso contrário, esse loop testará inutilmente esses resultados.

≔⁻｜θη＆θηθ

Atualize o resultado, na verdade, XORing the bit with it.

»Ｉθ

Saída do resultado final no final do loop.

05AB1E , 21 20 18 bytes

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

Bastante ineficiente, portanto, quanto maior a entrada, mais tempo leva para obter o resultado. Funciona para entrada0Também , no entanto.

Experimente online ou verifique o primeiro$n$termos .

Explicação:

Î                # 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

Experimente online!

Parece uma pena incorrer em uma importação apenas por xor, mas ainda não encontrei uma boa solução alternativa. Também me pergunto se existe uma maneira melhor de expressar o loop.

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

Experimente online!