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 .
Ponieważ jest to wyzwanie „czystej sekwencji”, zadaniem jest wyprowadzenie dla danego jako danych wejściowych, gdzie to A163252 .
Zadanie
Biorąc pod uwagę liczbę całkowitą , wypisz w formacie liczb całkowitych ( nie w formacie binarnym).
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.
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.
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.
- 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:
JavaScript (ES6), 65 bajtów
1-indeksowany.
Wypróbuj online!
Skomentował
źródło
Galaretka ,
2620 bajtówWypró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
Główny link
źródło
Java (JDK) ,
14213812412313213098 bajtówWypróbuj online!
źródło
import java.util.*;
+Set s=new HashSet();
dovar s=new java.util.HashSet();
. Ponadto, reszta może być golfed do:Integer i=0,j,k=0;for(;i++<n;s.add(k=j))for(j=0;s.contains(++j)|i.bitCount(j^k)>1;);return k;
. Niezła odpowiedź, więc +1 ode mnie. :)Stack
zamiastHashSet
. Dużo wolniej, ale działa!Python 2 , 81 bajtów
Indeksowanie 1
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)
Wypróbuj online!
źródło
Wolfram Language (Mathematica) , 74 bajty
Wypróbuj online!
źródło
APL (Dyalog Extended) , 46 bajtów
Wypróbuj online!
źródło
Węgiel drzewny , 65 bajtów
Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:
Zainicjuj wynik na 0.
n
Czasy pętliZapisz 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.
źródło
05AB1E ,
212018 bajtówDość 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ź pierwszyn warunki .
Wyjaśnienie:
źródło
Haskell , 101 bajtów
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ódło
R , 90 bajtów
Wypróbuj online!
źródło