Wprowadzenie (może zostać zignorowane)

Umieszczenie wszystkich liczb dodatnich w regularnej kolejności (1, 2, 3, ...) jest trochę nudne, prawda? Oto szereg wyzwań związanych z permutacjami (przetasowaniami) wszystkich liczb dodatnich. To drugie wyzwanie w tej serii. Pierwsze wyzwanie znajdziesz tutaj .

W tym wyzwaniu wykorzystujemy szare kody, aby zmienić liczby naturalne. Szary kod lub „odbity kod binarny” to kodowanie binarne w taki sposób, że dwie kolejne wartości różnią się tylko jednym bitem. Praktycznym zastosowaniem tego kodowania jest użycie go w koderach obrotowych , stąd moje odniesienie do „Turn My Way” .

Pamiętaj, że to kodowanie pozostawia pewien stopień swobody. Na przykład po binarnym 1100 istnieją cztery możliwe następujące kody: 1101, 1110, 1000 i 0100. Dlatego zdefiniuję jako najmniejszą, nieużywaną wcześniej wartość, która różni się tylko jednym znakiem w kodowaniu binarnym. Ta sekwencja odpowiada A163252 .$a(n)$

Ponieważ jest to wyzwanie „czystej sekwencji”, zadaniem jest wyprowadzenie dla danego jako danych wejściowych, gdzie to A163252 .$a(n)$$n$$a(n)$

Zadanie

Biorąc pod uwagę liczbę całkowitą , wypisz w formacie liczb całkowitych ( nie w formacie binarnym).$n$$a(n)$

$a(n)$ jest zdefiniowane jako najmniej dodatnia liczba całkowita nie występująca wcześniej w sekwencji, tak że i różnią się tylko jednym bitem, gdy są zapisywane w systemie binarnym.$a(n-1)$$a(n)$

Uwaga: tutaj zakłada się indeksowanie 1; możesz użyć indeksowania opartego na 0, więc itd. Podaj to w swojej odpowiedzi, jeśli zdecydujesz się na to.$a(0) = 1; a(1) = 3$

Przypadki testowe

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

Zasady

• Dane wejściowe i wyjściowe są liczbami całkowitymi (twój program powinien co najmniej obsługiwać dane wejściowe i wyjściowe w zakresie od 1 do 32767)
• Nieprawidłowe dane wejściowe (0, liczby zmiennoprzecinkowe, ciągi, wartości ujemne itp.) Mogą prowadzić do nieprzewidzianych wyników, błędów lub (nie) zdefiniowanego zachowania. W A163252 , definiuje się jako 0. Dla tego wyzwania, będziemy ignorować to.$a(0)$
• Obowiązują domyślne reguły we / wy .
• Domyślne luki są zabronione.
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach

Ostatnia uwaga

Zobacz następujące powiązane (ale nie równe) pytania PP&CG:

• Znajdowanie następnego kodu Graya (dane wejściowe i wyjściowe w formacie binarnym)
• Wygeneruj wszystkie kody Graya o długości n

Stax , 19 17 bajtów

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

Uruchom i debuguj

Przestaje działać w pewnym momencie po określonej domenie z powodu iteracji indeksu bitów na stałe. (32767)

Rozpakowane, niepolowane i skomentowane, wygląda to tak.

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

Uruchom ten

JavaScript (ES6), 65 bajtów

1-indeksowany.

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

Wypróbuj online!

Skomentował

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

Galaretka , 26 20 bajtów

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

Wypróbuj online!

Pełny program, który przyjmuje n jako pojedynczy argument. Działa dla wszystkich przypadków testowych. Zauważ też, że chociaż nie jest to wymagane, obsługuje n = 0.

Wyjaśnienie

Link pomocnika: znajdź następny termin i dodaj

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

Główny link

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 bajtów

• powiększony o konto do importu, zapisany bajt dzięki @ kevin-cruijssen
• przełączono kolekcję na tablicę int dzięki @ 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;}

Wypróbuj online!

Python 2 , 81 bajtów

Indeksowanie 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

Wypróbuj online!

Python 2 , 79 bajtów

To zajmuje dużo czasu (9999 nie zostało ukończone po uruchomieniu lokalnym przez 7 minut)

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

Wypróbuj online!

Wolfram Language (Mathematica) , 74 bajty

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

Wypróbuj online!

APL (Dyalog Extended) , 46 bajtów

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

Wypróbuj online!

Węgiel drzewny , 65 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

≔⁰θ

Zainicjuj wynik na 0.

ＦＮ«

nCzasy pętli

⊞υθ

Zapisz poprzedni wynik, aby nie używać go ponownie.

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

Znajdź najwyższy bit w poprzednim wyniku.

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

Chociaż ten bit jest większy niż 1, jeśli bit jest ustawiony w poprzednim wyniku, spróbuj odjąć ten bit, aby zobaczyć, czy wynik jest niewidoczny. Zapewnia to, że potencjalne wyniki są wypróbowywane w rosnącej kolejności wartości.

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

Teraz wypróbuj XORing tego bitu z poprzednim wynikiem, podwajając bit, aż do znalezienia niewidocznego wyniku. Dotyczy to przypadków, w których bit musi być ustawiony, ponownie w rosnącej kolejności wartości, ale także przypadku, gdy najmniej znaczący bit musi zostać przełączony, którego poprzednia pętla nie przeszkadza w testowaniu (ponieważ golfista testuje to tutaj). Jeśli poprzednia pętla znalazła niewidziany wynik, wówczas ta pętla nigdy nie działa; jeśli nie, to ta pętla bezużytecznie ponownie przetestuje te wyniki.

≔⁻｜θη＆θηθ

Zaktualizuj wynik, faktycznie XORując z nim bit.

»Ｉθ

Podaj wynik końcowy na końcu pętli.

05AB1E , 21 20 18 bajtów

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

Dość nieefektywny, więc im większy wkład, tym dłużej trwa uzyskanie wyniku. Działa również w przypadku danych wejściowych 0.

Wypróbuj online lub sprawdź pierwszy$n$warunki .

Wyjaśnienie:

Î                # 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 bajtów

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

Wypróbuj online!

Szkoda tylko ponieść import xor, ale nie znalazłem jeszcze dobrego rozwiązania. Zastanawiam się także, czy istnieje lepszy sposób na wyrażenie pętli.

R , 90 bajtów

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

Wypróbuj online!