Sekwencja krzywa smok (lub określonej sekwencji składania papier) jest sekwencją binarną. a(n)
jest podane przez zanegowanie bitu po lewej stronie najmniej znaczącego 1 z n
. Na przykład, aby obliczyć a(2136)
, najpierw konwertujemy na binarny:
100001011000
Znajdujemy nasz najmniej znaczący kawałek
100001011000
^
Weź kawałek w lewo
100001011000
^
I zwróć swoją negację
0
Zadanie
Biorąc pod uwagę dodatnią liczbę całkowitą jako dane wejściowe, wyjściowe a(n)
. (Możesz generować przez liczbę całkowitą lub wartość logiczną). Powinieneś dążyć do tego, aby twój kod był tak mały, jak to możliwe, mierzony bajtami.
Przypadki testowe
Oto pierwsze 100 wpisów w kolejności
1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1
100001011000
jest0
. Masz na myśli najmniej znaczący1
?Odpowiedzi:
Mathematica 25 bajtów
Inne sposoby na to:
56 bajtów
58 bajtów
źródło
Python 3 ,
2221 bajtów1 bajt dzięki produktom ETH.
Wypróbuj online!
Bitowe arytmetyki ftw.
źródło
0+(...)
?n&1
umieścić w nawiasach? Czy1+(n^~-n)<1
może to być umieszczone w nawiasach? Czy to jest1+(n^~-n)
...&
ma najniższy priorytet, więc jest1+(n^~-n)
Siatkówka oka ,
383429 bajtówWypróbuj online!
Martin i Leaky zasadniczo wymyślili ten pomysł, za 5 kolejnych bajtów!
Konwertuje dane wejściowe na jednoargumentowe, a następnie stopniowo dzieli liczbę przez 2. Gdy nie może już tego zrobić równomiernie (tzn. Liczba jest nieparzysta), usuwa łatki 4 z danych wejściowych, obliczając wynik ostatniej operacji mod 4 Na koniec sprawdza, czy wynik wynosił 1, co oznacza, że cyfra na lewo od najmniej znaczącego 1 bitu wynosiła zero. Jeśli to prawda, końcowy wynik to 1, w przeciwnym razie zero.
źródło
Galaretka , 5 bajtów
Wypróbuj online!
Jak to działa
źródło
Alice , 8 bajtów
Wypróbuj online!
Pobiera dane wejściowe jako punkt kodowy znaku Unicode i odpowiednio wyświetla wynik jako bajt 0x00 lub 0x01.
W celu przetestowania, oto wersja dziesiętna we / wy na 12 bajtów, która używa dokładnie tego samego algorytmu (tylko we / wy jest inne):
Wypróbuj online!
Gdyby Alicja była językiem golfowym i nie wymagała wyraźnego wejścia / wyjścia i zakończenia programu,
2z1xn
osiągnęłoby to zaledwie 5 bajtów ( ), pokonując zarówno 05AB1E, jak i Jelly.Wyjaśnienie
źródło
05AB1E , 6 bajtów
Wypróbuj online!
źródło
Mądry ,
282016 bajtówWypróbuj online!
Wyjaśnienie
To jest port odpowiedzi Pythona Dziurawej Zakonnicy. Niestety nie działa na TIO, ponieważ wersja interpretera TIO jest nieco nieaktualna.
Zaczynamy od wykonania 3 kopii naszych danych wejściowych
::
, a następnie zmniejszamy górną kopię o 1. Spowoduje to odwrócenie wszystkich bitów do pierwszej 1. Następnie xor to z inną kopią naszych danych wejściowych. Ponieważ wszystkie bity do pierwszej 1 na naszym wejściu zostały odwrócone, spowoduje to, że wszystkie te bity będą miały 1 na wyniku. Jeśli następnie dodamy jeden~-
do wyniku, otrzymamy jeden 1 w miejscu po lewej stronie naszego najmniej znaczącego 1. My ORAZ to z wejściem, aby uzyskać ten bit z wejścia. Teraz będziemy mieć0
iff, że ten bit był wyłączony i moc 2 iff, ten bit był włączony, możemy zmienić to na pojedyncze1
lub0
z:[?>]
. Gdy to zrobimy, musimy tylko trochę zanegować~-^
i gotowe.źródło
Python 2 , 19 bajtów
Wypróbuj online!
źródło
Haskell ,
454339 bajtów6 bajtów zapisanych dzięki nim
Wypróbuj online!
źródło
div
zamiastquot
.divMod
:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
|(d,m)<-divMod x 2
Jest to strażnik wzorców do wiązaniad
zdiv x 2
im
domod x 2
. Używamym
do indeksowania listy dwóch elementów[...,...]!!m
. W przypadkum==0
powrotumod(1+d)2
i w przypadkum==1
f d
.[f d,mod(1+d)2]
. Wypróbuj online! .Kod maszynowy x86,
171615 bajtów:Zakłada ABI, w którym parametry są wypychane na stos, a zwracana wartość znajduje się w
AL
rejestrze.Rozkłada się to w następujący sposób:
źródło
JavaScript (ES6),
1714 bajtówEdycja: Zapisałem 3 bajty, przenosząc odpowiedź @ Dennisa, gdy zauważyłem, że wyjście boolowskie jest dopuszczalne.
źródło
C (gcc) , 20 bajtów
Wypróbuj online!
źródło
INTERCAL , 50 bajtów
Jednoargumentowi operatorzy INTERCAL są do tego całkiem odpowiedni, więc postanowiłem napisać swój pierwszy post.
źródło
Haskell , 33 bajty
Wypróbuj online!
Wykorzystuje indeksowanie 0.
źródło
~
w tym kontekście? Rozumiem, że to leniwe dopasowanie, ale dlaczego potrzebujesz leniwego dopasowania?Galaretka ,
76 bajtów1 bajt dzięki Erik the Outgolfer.
Wypróbuj online!
Dłuższe programy
Họ¡2&2Ị
Bt0ṫ-ḄỊ
źródło
ṖṪṆ
(jak moja usunięta odpowiedź) zamiastṫ-ḄỊ
.BUḌDḊḢ¬
,,, ,
109 bajtówWyjaśnienie
Weź na przykład dane wejściowe jako 3.
źródło
Haskell , 26 bajtów
Wypróbuj online!
Wyjście logiczne.
źródło
Oktawa , 34 bajty
Wypróbuj online!
Wyjaśnienie:
źródło
Uległość:
Python 2 ,
4139 bajtówWypróbuj online!
-2 bajty dzięki FryAmTheEggman
Wstępne rozwiązanie:
Python 2 , 43 bajty
Wypróbuj online!
źródło
~-x&1
myślę, że zamiast tego działa na chwilę.MATL ,
1110 bajtówWypróbuj online! Lub zobacz pierwsze 100 wyników .
Wyjaśnienie
źródło
Pari / GP , 20 bajtów
Używanie symbolu Kronecker .
Wypróbuj online!
źródło
Befunge-98 , 19 bajtów
Wypróbuj online!
źródło
SCALA, 99 (78?) Znaków, 99 (78?) Bajtów
gdzie
i
jest wejście.Jak widać, oszczędzam 21 bajtów, jeśli nie dbam o zero (tak jak autor w swoim przypadku testowym):
To mój pierwszy codegolf, więc mam nadzieję, że dobrze mi poszło :)
Wypróbuj online! Chociaż obliczenie lol jest dość długie.
źródło
C (gcc) ,
3531 bajtówPrzełączono na implementację rekurencyjną. Wypróbuj online!
źródło
Java 8, 17 bajtów
Prosty port odpowiedzi LeakyNun na Python 3 . Nie znam wystarczająco operacji bitowych i pierwszeństwa operatorów, aby zobaczyć krótsze rozwiązanie; może istnieje sposób na uniknięcie dodatkowego nawiasu?
źródło
Japt ,
10 89 bajtówWypróbuj online!
Wyjaśnienie
źródło
false
wszystko, ponieważ znak (0 lub 1) jest zawsze ciągiem.1
.JavaScript (ES6),
5334 bajtyźródło
a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
PHP> = 7.1, 32 bajty
PHP Sandbox Online
PHP , 40 bajtów
Wypróbuj online!
PHP , 41 bajtów
Wypróbuj online!
źródło
Common Lisp, 56 bajtów
Wypróbuj online!
źródło
Chip , 93 bajty
Pobiera dane wejściowe jako małe bajty endian. (TIO ma trochę Pythona, który robi to za Ciebie). Daje wyjście jako albo
0x0
albo0x1
. (TIO używa xxd do sprawdzenia wartości).Wypróbuj online!
Jak to zrobić?
Chip patrzy na dane wejściowe jeden bajt na raz, więc obsługa danych wielobajtowych dodaje trochę objętości, ale nie tak bardzo, jak się obawiałem.
Przejdźmy do tego:
Są to
HZ
: wysoki bit poprzedniego bajtu (jeśli był) iA
-G
siedem niższych bitów bieżącego bajtu. Służą one do zlokalizowania najniższego ustawionego bitu liczby.Kiedy zostanie znaleziony najniższy ustawiony bit, mamy kilka rzeczy do zrobienia. Ta pierwsza porcja mówi „jeśli mamy ustawiony bit (
)
y), to przestańS
zwiększać wydajność it
kończymy po wydrukowaniu odpowiedzi.Niezależnie od tego, który bit bieżącego bajtu (
A
-H
) poprzedza tylko wiązka zer, wówczas jeden (\
i/
: patrzą one na bity bezpośrednio na północ od nich; możemy ufać, że wszystkie poprzednie bity były zerowe) są przekazywane do przewodów na prawo (v
,'
...), a następnie tych dwóch wartości jest odwracany i jest podawana jako niski bit wyjścia (~a
).źródło