Введение (может быть проигнорировано)

Размещать все положительные числа в обычном порядке (1, 2, 3, ...) немного скучно, не правда ли? Итак, вот серия проблем, связанных с перестановками (перестановками) всех положительных чисел. Это второй вызов в этой серии. Первый вызов можно найти здесь .

В этом вызове мы используем коды Грея, чтобы переставить натуральные числа. Код Грея или «отраженный двоичный код» - это двоичное кодирование таким образом, что два последовательных значения отличаются только одним битом. Практическое применение этого кодирования - использовать его в поворотных кодировщиках , поэтому я ссылаюсь на «Turn My Way» .

Обратите внимание, что эта кодировка оставляет некоторую степень свободы. Например, после бинарного 1100, существует четыре возможных следующие коды: 1101, 1110, 1000 и 0100. Поэтому я определим $a(n)$ , как наименьший, а не ранее используемое значение , которое отличается только один символ в двоичной кодировке. Эта последовательность соответствует A163252 .

Поскольку это задача «чистой последовательности», задача состоит в том, чтобы вывести $a(n)$ для заданного $n$ качестве входных данных, где $a(n)$ - это A163252 .

задача

Учитывая целочисленный ввод $n$ , выведите $a(n)$ в целочисленном формате ( не в двоичном формате).

$a(n)$ определяется как наименее положительное целое число, не встречающееся ранее в последовательности, так что$a(n-1)$ и$a(n)$ отличаются только одним битом при записи в двоичном виде.

Примечание: здесь предполагается индексирование на основе 1; Вы можете использовать индексирование на основе 0, поэтому $a(0) = 1; a(1) = 3$ и т. д. Пожалуйста, укажите это в своем ответе, если вы решите использовать это.

Контрольные примеры

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

правила

• Вход и выход являются целыми числами (ваша программа должна по крайней мере поддерживать вход и выход в диапазоне от 1 до 32767)
• Неверный ввод (0, значения с плавающей запятой, строки, отрицательные значения и т. Д.) Может привести к непредсказуемым результатам, ошибкам или (не) определенному поведению. В A163252 , ( 0 )$a(0)$ определяется как 0. Для этой задачи мы будем игнорировать это.
• Стандартные правила ввода / выводаПрименяются .
• Лазейки по умолчанию запрещены.
• Это код-гольф , поэтому самые короткие ответы в байтах выигрывают

Конечная нота

Смотрите следующие связанные (но не равные) вопросы PP & CG:

• Поиск следующего кода Грея (ввод и вывод в двоичном виде)
• Генерация всех кодов Грея длины n

Stax , 19 17 байт

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

Запустите и отладьте его

Он перестает работать в какой-то момент после указанного домена из-за жестко закодированной битовой индексации. (32767)

Распакованный, размазанный и прокомментированный, это выглядит так.

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

Запустите этот

JavaScript (ES6), 65 байт

1-индексироваться.

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

Попробуйте онлайн!

комментарии

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

Желе , 26 20 байт

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

Попробуйте онлайн!

Полная программа, которая принимает n в качестве единственного аргумента. Работает для всех тестовых случаев. Также обратите внимание, что, хотя и не обязательно, он обрабатывает n = 0.

объяснение

Вспомогательная ссылка: найти следующий термин и предварять

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

Главная ссылка

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 байт

• увеличен для учета импорта, сохранен байт благодаря @ kevin-cruijssen
• переключил коллекцию на массив int благодаря @ 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;}

Попробуйте онлайн!

Python 2 , 81 байт

Индексирование на основе 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

Попробуйте онлайн!

Python 2 , 79 байт

Это занимает много времени (9999 не был закончен после локального запуска в течение 7 минут)

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 74 байта

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

Попробуйте онлайн!

APL (Dyalog Extended) , 46 байтов

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

Попробуйте онлайн!

Древесный уголь , 65 байт

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

Попробуйте онлайн!Ссылка на подробную версию кода. Объяснение:

≔⁰θ

Инициализируйте результат до 0.

ＦＮ«

петля n раз.

⊞υθ

Сохраните предыдущий результат, чтобы мы не использовали его снова.

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

Найти старший бит в предыдущем результате.

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

Хотя этот бит больше 1, если бит установлен в предыдущем результате, попробуйте вычесть этот бит, чтобы увидеть, является ли результат невидимым результатом. Это гарантирует, что потенциальные результаты проверяются в порядке возрастания стоимости.

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

Теперь попробуйте XORing этот бит с предыдущим результатом, удваивая бит, пока не будет найден невидимый результат. Это обрабатывает случаи, когда бит должен быть установлен, опять-таки в порядке возрастания значения, но также и случай, когда необходимо переключить младший бит, который предыдущий цикл не потрудит проверить (потому что он проверяет гольф что здесь). Если предыдущий цикл обнаружил невидимый результат, этот цикл никогда не запускается; если это не так, то этот цикл будет бесполезно повторно тестировать эти результаты.

≔⁻｜θη＆θηθ

Обновите результат, на самом деле XORing бит с ним.

»Ｉθ

Выведите окончательный результат в конце цикла.

05AB1E , 21 20 18 байт

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

Довольно неэффективно, поэтому чем больше ввод, тем больше времени требуется для получения результата. Работает ли для ввода 0, хотя.

Попробуйте онлайн или проверьте первый$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 байт

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

Попробуйте онлайн!

Кажется, стыдно брать на себя импорт xor, но я пока не нашел хорошего обходного пути. Мне также интересно, есть ли лучший способ выразить цикл.

R , 90 байт

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

Попробуйте онлайн!