Smocza sekwencja Krzywej

23

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
Kreator pszenicy
źródło
9
Najmniej znaczącym fragmentem 100001011000jest 0. Masz na myśli najmniej znaczący 1?
rozproszyć

Odpowiedzi:

16

Mathematica 25 bajtów

1/2+JacobiSymbol[-1,#]/2&

Inne sposoby na to:

56 bajtów

(v:=1-IntegerDigits[#,2,i][[1]];For[i=1,v>0,i++];i++;v)&

58 bajtów

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&
Kelly Lowder
źródło
3
Łał! Odpowiedź matematyczna i nie jest tylko wbudowana. Zyskaj głos!
KeyWeeUsr
2
Jedyną rzeczą, która mogłaby uczynić tę odpowiedź jeszcze lepszą, jest wyjaśnienie, dlaczego i jak to działa. : P
Martin Ender
2
@MartinEnder arxiv.org/pdf/1408.5770.pdf Patrz uwaga po Przykład 13
alephalpha
7

Python 3 , 22 21 bajtów

1 bajt dzięki produktom ETH.

lambda n:n&2*(n&-n)<1

Wypróbuj online!

Bitowe arytmetyki ftw.

Leaky Nun
źródło
2
„Możesz generować przez liczbę całkowitą lub wartość logiczną”, więc myślę, że nie potrzebujesz 0+(...)?
Martin Ender
Tutaj porządek operacji jest naprawdę mylący. Można n&1umieścić w nawiasach? Czy 1+(n^~-n)<1może to być umieszczone w nawiasach? Czy to jest 1+(n^~-n)...
ETHproductions
o Boże co. tego właśnie szukałem: o miło!
HyperNeutrino
&ma najniższy priorytet, więc jest1+(n^~-n)
Leaky Nun
Ach, znalazłem tabelę pierwszeństwa. Teraz wszystko ma sens: P
ETHproductions
6

Siatkówka oka ,38 34 29 bajtów

\d+
$*
+`^(1+)\1$|1111
$1
^1$

Wypró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.

FryAmTheEggman
źródło
31 bajtów (powinienem to opublikować?)
Leaky Nun
Znalazłem sposób na uniknięcie pełnej konwersji binarnej i zamiast tego po prostu podzielę czynniki 2 i sprawdzam równość z 1 (mod 4): tio.run/##K0otycxL/…
Martin Ender
@MartinEnder zasadniczo mój algorytm ... z 2 bajtami wyłączonymi
Leaky Nun
@LeakyNun O tak, oboje mają ten sam pomysł. Wielkie umysły i takie tam ...;)
Martin Ender
Zmienię to, ale jeśli któryś z was chce to opublikować, cofnę się, ponieważ prawdopodobnie sam bym o tym nie pomyślał;)
FryAmTheEggman
6

Galaretka , 5 bajtów

&N&HṆ

Wypróbuj online!

Jak to działa

&N&HṆ  Main link. Argument: n

 N     Negate; yield -n.
&      Bitwise AND; compute n&-n.
       This yields the highest power of 2 that divides n evenly.
   H   Halve; yield n/2.
  &    Bitwise AND; compute n&-n&n/2. This rounds n/2 down if n is odd.
    Ṇ  Take the logical NOT of the result.
Dennis
źródło
4

Alice , 8 bajtów

I2z1xnO@

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):

/o
\i@/2z1xn

Wypróbuj online!

Gdyby Alicja była językiem golfowym i nie wymagała wyraźnego wejścia / wyjścia i zakończenia programu, 2z1xnosiągnęłoby to zaledwie 5 bajtów ( ), pokonując zarówno 05AB1E, jak i Jelly.

Wyjaśnienie

I    Read input.
2z   Drop all factors of 2 from the input, i.e. divide it by 2 as long
     as its even. This shifts the binary representation to the right
     until there are no more trailing zeros.
1x   Extract the second-least significant bit.
n    Negate it.
O    Output it.
@    Terminate the program.
Martin Ender
źródło
3

Mądry , 28 20 16 bajtów

::-~^~-&:[?>]~-^

Wypró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ć 0iff, że ten bit był wyłączony i moc 2 iff, ten bit był włączony, możemy zmienić to na pojedyncze 1lub 0z :[?>]. Gdy to zrobimy, musimy tylko trochę zanegować ~-^i gotowe.

Kreator pszenicy
źródło
3

Haskell , 45 43 39 bajtów

6 bajtów zapisanych dzięki nim

f x|d<-div x 2=[f d,mod(1+d)2]!!mod x 2

Wypróbuj online!

Kreator pszenicy
źródło
Możesz użyć divzamiast quot.
nimi
Nawet lepiej: divMod:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
Nimi
@nimi Nawet nie rozumiem, jak to działa. Prawdopodobnie powinieneś po prostu opublikować to sam.
Wheat Wizard
Jest to wciąż ten sam algorytm, ale po prostu inny sposób wybrania gałęzi (rekurencyjnie wywołaj f ponownie w porównaniu z przypadkiem podstawowym), więc nie krępuj się edytować go. |(d,m)<-divMod x 2Jest to strażnik wzorców do wiązania dz div x 2i mdo mod x 2. Używamy mdo indeksowania listy dwóch elementów [...,...]!!m. W przypadku m==0powrotu mod(1+d)2i w przypadku m==1 f d.
nimi
1
Oh, przepraszam, trzeba odwrócić elementów listy: [f d,mod(1+d)2]. Wypróbuj online! .
nimi
3

Kod maszynowy x86, 17 16 15 bajtów:

Zakłada ABI, w którym parametry są wypychane na stos, a zwracana wartość znajduje się w ALrejestrze.

8B 44 24 04 0F BC C8 41 0F BB C8 0F 93 C0 C3

Rozkłada się to w następujący sposób:

_dragoncurve:
  00000000: 8B 44 24 04        mov         eax,dword ptr [esp+4]
  00000004: 0F BC C8           bsf         ecx,eax
  00000007: 41                 inc         ecx
  00000008: 0F BB C8           btc         eax,ecx
  0000000B: 0F 93 C0           setae       al
  0000000E: C3                 ret
Govind Parmar
źródło
1
@PeterTaylor Liczę rozmiar instrukcji procesora w bajtach dla mojej odpowiedzi; jest to dość powszechna praktyka w PPCG dla odpowiedzi asemblacyjnych.
Govind Parmar
1
Nie mogłem powiedzieć, jak często to się dzieje , ale zdecydowanie jest błędne
Peter Taylor
1
Jest nie tylko pedantyczny, ale także pozbawiony znaczenia. W przypadku komputera nie ma różnicy między „kodem maszynowym” a „kodem montażowym”. Różnica polega jedynie na interpretacji. Przypisujemy mnemoniki do bajtów kodu maszynowego, aby ułatwić ich odczytanie. Innymi słowy, odkrywamy bajty, aby ułatwić ich zrozumienie.
Cody Gray
3
To nie ma znaczenia, @Peter. Kod asemblera to po prostu tłumaczenie kodu maszynowego w postaci czytelnej dla człowieka. Są to dokładnie ten sam język, tylko w dwóch różnych formach / reprezentacjach. Nie różni się niczym od TI BASIC, gdzie powszechnie przyjmuje się, że liczymy tokeny zamiast bajtów znaków, ponieważ w ten sposób system przechowuje je wewnętrznie. To samo dotyczy języka asemblera: mnemoniki instrukcji nie są przechowywane jako pojedyncze znaki, lecz raczej reprezentowane jako bajty równoważnego kodu maszynowego.
Cody Gray
2
Poza tym, praktycznie mówiąc, dlaczego ktokolwiek miałby kiedykolwiek brać udział w rozszerzonej mnemonice języka asemblera podczas zawodów w golfie, skoro mógł przetłumaczyć je na w 100% ekwiwalentny kod maszynowy, w którym wpis jest gwarantowany za darmo krócej? To samo czyni rozróżnienie między tymi dwoma bezcelowymi, jeśli nie całkowicie absurdalnymi.
Cody Gray
3

JavaScript (ES6), 17 14 bajtów

f=
n=>!(n&-n&n/2)
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Edycja: Zapisałem 3 bajty, przenosząc odpowiedź @ Dennisa, gdy zauważyłem, że wyjście boolowskie jest dopuszczalne.

Neil
źródło
3

C (gcc) , 20 bajtów

f(n){n=!(n&-n&n/2);}

Wypróbuj online!

Dennis
źródło
To tak naprawdę nie działa; polegasz na dziwactwie generatora kodu dla jednej konkretnej wersji kompilatora ukierunkowanej na jedną konkretną architekturę, gdzie obliczenia pośrednie są wykonywane w tym samym rejestrze, który jest używany dla zwracanych wartości. Włączenie dowolnego typu optymalizacji, zmiana architektury docelowej lub użycie innej wersji GCC to zepsuje. Równie dobrze możesz powiedzieć: „śmieci na moim stosie zawierają odpowiednią wydajność, gdy jest pełnia księżyca 13 października”.
Cody Gray
Chociaż wszystko, co mówisz, jest prawdą, a takiego kodu nigdy nie można używać w kodzie produkcyjnym, definiujemy języki przez ich implementacje na potrzeby gry w golfa. Bez dodatkowych flag działa to we wszystkich najnowszych wersjach gcc i tcc i musi działać tylko w jednej wersji, aby zostać uznane za ważne.
Dennis
„definiujemy języki przez ich implementacje dla potrzeb golfa” Czekaj, co? Więc każda flaga kompilatora i każda wersja GCC definiuje inny język? Zdajesz sobie sprawę, że to szalone, prawda? Standard języka C określa język.
Cody Gray
Nie tutaj. Gdyby istniał standard C, ale nie ma implementacji, nie uznalibyśmy go nawet za język. Jak powiedziałem wcześniej, kompilator określa język . W rezultacie dozwolone jest poleganie na niezdefiniowanym zachowaniu . Inny zestaw flag nie jest uważany za inny język, ale jeśli nie dodasz ich do liczby bajtów, wszystkie odpowiedzi używają standardowych flag kompilacji.
Dennis
Łał. To szaleństwo. To znaczy, mogę zrozumieć, jeśli mówisz, że realizacja zdefiniowane zachowanie jest dozwolone, ale niezdefiniowane zachowanie jest nie zdefiniowana przez wdrożenie. Jest dosłownie niezdefiniowany. Implementacja może za każdym razem wykonywać losowe czynności. A to pojęcie „standardowych flag kompilacji” to coś, co właśnie wymyśliłeś. Moje standardowe flagi kompilacji zawierają kilka, które łamią Twój kod. I raczej nie sądzę, że optymalizator jest niestandardowy. Oczywiście ta strona nie jest dla mnie.
Cody Gray
3

INTERCAL , 50 bajtów

DOWRITEIN.1DO.1<-!?1~.1'~#1DOREADOUT.1PLEASEGIVEUP

Jednoargumentowi operatorzy INTERCAL są do tego całkiem odpowiedni, więc postanowiłem napisać swój pierwszy post.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP
Bernd Fischer
źródło
3

Haskell , 33 bajty

g~(a:b:c)=1:a:0:b:g c
d=g d
(d!!)

Wypróbuj online!

Wykorzystuje indeksowanie 0.

Anders Kaseorg
źródło
1
Co robi ~w tym kontekście? Rozumiem, że to leniwe dopasowanie, ale dlaczego potrzebujesz leniwego dopasowania?
Wheat Wizard
2

Galaretka , 7 6 bajtów

1 bajt dzięki Erik the Outgolfer.

Bt0ṖṪṆ

Wypróbuj online!

Dłuższe programy

Leaky Nun
źródło
Hmm ... cóż, możesz po prostu zrobić ṖṪṆ(jak moja usunięta odpowiedź) zamiast ṫ-ḄỊ.
Erik the Outgolfer
1
Kolejny dla twojej listy 7-bajtowej:BUḌDḊḢ¬
steenbergh
2

,,, , 10 9 bajtów

::0-&2*&¬

Wyjaśnienie

Weź na przykład dane wejściowe jako 3.

::0-&2*&1≥
               implicitly push command line argument       [3]
::             duplicate twice                             [3, 3, 3]
  0            push 0 on to the stack                      [3, 3, 3, 0]
   -           pop 0 and 3 and push 0 - 3                  [3, 3, -3]
    &          pop -3 and 3 and push -3 & 3 (bitwise AND)  [3, 1]
     2         push 2 on to the stack                      [3, 1, 2]
      *        pop 2 and 1 and push 2 * 1                  [3, 2]
       &       pop 2 and 3 and push 2 & 3                  [2]
        ¬      pop 2 and push ¬ 2 (logical NOT)            [0]
               implicit output                             []
całkowicie ludzki
źródło
2

Oktawa , 34 bajty

@(x)~(k=[de2bi(x),0])(find(k,1)+1)

Wypróbuj online!

Wyjaśnienie:

@(x)                               % Anonymous function taking a decimal number as input
    ~....                          % Negate whatever comes next
     (   de2bi(x)   )              % Convert x to a binary array that's conveniently 
                                   % ordered with the least significant bits first
        [de2bi(x),0]               % Append a zero to the end, to avoid out of bound index
     (k=[de2bi(x),0])              % Store the vector as a variable 'k'
                     (find(k,1)    % Find the first '1' in k (the least significant 1-bit)
                               +1  % Add 1 to the index to get the next bit
     (k=[de2bi(x),0])(find(k,1)+1) % Use as index to the vector k to get the correct bit
Stewie Griffin
źródło
Dlaczego nigdy nie słyszałem o de2bi ...: O
Sanchises
1

Uległość:

Python 2 , 41 39 bajtów

x=input()
while~-x&1:x/=2
print 1-x/2%2

Wypróbuj online!

-2 bajty dzięki FryAmTheEggman

Wstępne rozwiązanie:

Python 2 , 43 bajty

lambda x:1-int(bin(x)[bin(x).rfind('1')-1])

Wypróbuj online!

HyperNeutrino
źródło
Więc który z nich jest twoim poddaniem?
Leaky Nun
@LeakyNun Pierwszy, ponieważ jest krótszy; drugi był moim oryginalnym oświadczeniem. Czy powinienem opublikować je osobno?
HyperNeutrino
~-x&1myślę, że zamiast tego działa na chwilę.
FryAmTheEggman
(Zapomniałem nazwy użytkownika); Odrzuciłem twoją edycję, ponieważ zmiany w kodzie golfowym innych osób nie są zalecane w PPCG. Możesz publikować sugestie (btw, dzięki @FryAmTheEggman), ale proszę nie wprowadzać zmian w grze w golfa. Dzięki!
HyperNeutrino
@StewieGriffin Ah tak, dziękuję. Niestety nie mogę pingować użytkownika, ponieważ edycja została odrzucona.
HyperNeutrino
1

MATL , 11 10 bajtów

t4*YF1)Z.~

Wypróbuj online! Lub zobacz pierwsze 100 wyników .

Wyjaśnienie

t    % Implicit input. Duplicate
4*   % Multiply by 4. This ensures that the input is a multiple of 2, and
     % takes into account that bit positions are 1 based
YF   % Exponents of prime factorization
1)   % Get first exponent, which is that of factor 2
Z.   % Get bit of input at that (1-based) position
~    % Negate. Implicit display
Luis Mendo
źródło
1

Befunge-98 , 19 bajtów

&#;:2%\2/\#;_;@.!%2

Wypróbuj online!

&#                       Initial input: Read a number an skip the next command
  ;:2%\2/\#;_;           Main loop: (Direction: East)
   :2%                    Duplicate the current number and read the last bit
      \2/                 Swap the first two items on stack (last bit and number)
                          and divide the number by two => remove last bit
         \                swap last bit and number again
          #;_;            If the last bit is 0, keep going East and jump to the beginning of the loop
                          If the last bit is 1, turn West and jump to the beginning of the loop, but in a different direction.
&#;           @.!%2      End: (Direction: West)
&#                        Jump over the input, wrap around
                 %2       Take the number mod 2 => read the last bit
               .!         Negate the bit and print as a number
              @          Terminate
ovs
źródło
1

SCALA, 99 (78?) Znaków, 99 (78?) Bajtów

if(i==0)print(1)else
print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

gdzie ijest wejście.

Jak widać, oszczędzam 21 bajtów, jeśli nie dbam o zero (tak jak autor w swoim przypadku testowym):

print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

To mój pierwszy codegolf, więc mam nadzieję, że dobrze mi poszło :)

Wypróbuj online! Chociaż obliczenie lol jest dość długie.

V. Courtois
źródło
Witamy na stronie!
DJMcMayhem
1

Java 8, 17 bajtów

n->(n&2*(n&-n))<1

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?

JollyJoker
źródło
0

Japt , 10 8 9 bajtów

!+¢g¢a1 É

Wypróbuj online!

Wyjaśnienie

!+¢   g    a1 É
!+Us2 gUs2 a1 -1 # Implicit input (U) as number
!+               # Return the boolean NOT of
      g          #   the character at index
       Us2       #     the input converted to binary
           a1    #     the index of its last 1
              -1 #     minus 1
      g          #   in string
  Us2            #     the input converted to binary
Luke
źródło
Zwraca to falsewszystko, ponieważ znak (0 lub 1) jest zawsze ciągiem.
Shaggy
Ups, powinienem był zauważyć, że ... Naprawiono
Luke
Na razie wygląda na to, że zawodzi1 .
Shaggy
0

JavaScript (ES6), 53 34 bajty

a=>eval("for(;~a&1;a/=2);~a>>1&1")
Luke
źródło
42 bajty:a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
Shaggy
Znalazłem już krótsze (matematyczne) rozwiązanie ...
Luke
Fajnie :) Czy mógłbym zamieścić ten 42 bajtowy?
Shaggy
@ Shaggy, wcale nie
Luke
0

Chip , 93 bajty

HZABCDEFG,t
 ))))))))^~S
H\\\\\\\/v~a
G\\\\\\/v'
F\\\\\/v'
E\\\\/v'
D\\\/v'
C\\/v'
B\/v'
A/-'

Pobiera dane wejściowe jako małe bajty endian. (TIO ma trochę Pythona, który robi to za Ciebie). Daje wyjście jako albo 0x0albo 0x1. (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:

HZABCDEFG

Są to HZ: wysoki bit poprzedniego bajtu (jeśli był) i A- Gsiedem niższych bitów bieżącego bajtu. Służą one do zlokalizowania najniższego ustawionego bitu liczby.

        ,t
))))))))^~S

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ń Szwiększać wydajność i tkończymy po wydrukowaniu odpowiedzi.

H\\\\\\\/v~a
G\\\\\\/v'
...
A/-'

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).

Phlarx
źródło