Introduction (peut être ignoré)

Mettre tous les nombres positifs dans son ordre normal (1, 2, 3, ...) est un peu ennuyeux, n'est-ce pas? Voici donc une série de défis autour des permutations (remaniements) de tous les nombres positifs. Il s'agit du deuxième défi de cette série. Le premier défi se trouve ici .

Dans ce défi, nous utilisons des codes Gray pour réarranger les nombres naturels. Un code Gray ou "code binaire réfléchi" est un codage binaire de telle manière que deux valeurs successives diffèrent en un seul bit. Une application pratique de cet encodage est de l'utiliser dans des encodeurs rotatifs , d'où ma référence à "Turn My Way" .

Notez que ce codage laisse un certain degré de liberté. Par exemple, après le binaire 1100, il y a quatre codes suivants possibles: 1101, 1110, 1000 et 0100. C'est pourquoi je définirai comme la plus petite valeur non utilisée précédemment qui ne diffère qu'un seul caractère dans le codage binaire. Cette séquence correspond à A163252 .$a(n)$

Puisqu'il s'agit d'un défi de "séquence pure", la tâche consiste à sortir pour un donné en entrée, où a (n) est A163252 .$a(n)$$n$$a(n)$

Tâche

Étant donné une entrée entière $n$ , la sortie $a(n)$ au format entier ( pas au format binaire).

$a(n)$ est défini comme l'entier le moins positif ne se produisant pas plus tôt dans la séquence, de telle sorte que et diffèrent d'un seul bit lorsqu'ils sont écrits en binaire.$a(n-1)$$a(n)$

Remarque: l'indexation basée sur 1 est supposée ici; vous pouvez utiliser une indexation basée sur 0, donc , etc. Veuillez le mentionner dans votre réponse si vous choisissez de l'utiliser.$a(0) = 1; a(1) = 3$

Cas de test

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

Règles

• L'entrée et la sortie sont des entiers (votre programme doit au moins prendre en charge l'entrée et la sortie dans la plage de 1 à 32 767)
• Une entrée non valide (0, flottants, chaînes, valeurs négatives, etc.) peut entraîner une sortie imprévue, des erreurs ou un comportement (non) défini. Dans A163252 , est défini comme 0. Pour ce défi, nous l'ignorerons.$a(0)$
• Les règles d'E / S par défaut s'appliquent.
• Les failles par défaut sont interdites.
• Il s'agit de code-golf , donc les réponses les plus courtes en octets l'emportent

Note finale

Voir les questions PP&CG connexes (mais pas égales) suivantes:

• Trouver le prochain code Gray (entrée et sortie en binaire)
• Générer tous les codes gris de longueur n

Stax , 19 17 octets

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

Exécuter et déboguer

Il cesse de fonctionner à un moment donné après le domaine spécifié en raison de l'itération d'index binaire codée en dur. (32767)

Déballé, non golfé et commenté, il ressemble à ceci.

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

Exécutez celui-ci

JavaScript (ES6), 65 octets

1 indexé.

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

Essayez-le en ligne!

Commenté

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ée , 26 20 octets

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

Essayez-le en ligne!

Un programme complet qui prend n comme seul argument. Fonctionne pour tous les cas de test. Notez également que, bien que non obligatoire, il gère n = 0.

Explication

Lien d'aide: trouvez le prochain terme et ajoutez-le

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

Lien principal

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

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

• augmenté pour tenir compte de l'importation, enregistré un octet grâce à @ kevin-cruijssen
• collection commutée vers int array grâce à @ 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;}

Essayez-le en ligne!

Python 2 , 81 octets

Indexation basée sur 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

Essayez-le en ligne!

Python 2 , 79 octets

Cela prend beaucoup de temps (9999 n'était pas terminé après une exécution locale pendant 7 minutes)

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

Essayez-le en ligne!

Wolfram Language (Mathematica) , 74 octets

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

Essayez-le en ligne!

APL (Dyalog Extended) , 46 octets

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

Essayez-le en ligne!

Fusain , 65 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

≔⁰θ

Initialisez le résultat à 0.

ＦＮ«

nTemps de boucle .

⊞υθ

Enregistrez le résultat précédent afin de ne plus l'utiliser.

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

Trouvez le bit le plus élevé dans le résultat précédent.

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

Bien que ce bit soit supérieur à 1, si le bit est défini dans le résultat précédent, essayez de soustraire ce bit pour voir si le résultat est un résultat invisible. Cela garantit que les résultats potentiels sont essayés par ordre croissant de valeur.

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

Essayez maintenant de XORing ce bit avec le résultat précédent, en doublant le bit jusqu'à ce qu'un résultat invisible soit trouvé. Cela gère les cas où un bit doit être défini, à nouveau dans l'ordre croissant de valeur, mais aussi le cas où le bit le moins significatif doit être basculé, ce que la boucle précédente ne prend pas la peine de tester (car il est golfeur de tester pour c'est ici). Si la boucle précédente a trouvé un résultat invisible, cette boucle ne s'exécute jamais; si ce n'est pas le cas, cette boucle testera inutilement ces résultats.

≔⁻｜θη＆θηθ

Mettez à jour le résultat en réellement XOR le bit avec.

»Ｉθ

Afficher le résultat final à la fin de la boucle.

05AB1E , 21 20 18 octets

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

Assez inefficace, donc plus l'entrée est grande, plus il faut de temps pour obtenir le résultat. Cela fonctionne également pour les entrées 0.

$n$

Explication:

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

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

Essayez-le en ligne!

Il semble dommage de subir une importation juste pour xor, mais je n'ai pas encore trouvé de bonne solution. Je me demande également s'il y a une meilleure façon d'exprimer la boucle.

R , 90 octets

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

Essayez-le en ligne!