Die Drachenkurvenfolge

23

Die Drachenkurvenfolge (oder die reguläre Papierfaltfolge) ist eine binäre Folge. a(n)wird durch Negation des Bits links von der niedrigstwertigen 1 von gegeben n. Um zum Beispiel zu berechnen a(2136), konvertieren wir zuerst nach binär:

100001011000

Wir finden unser am wenigsten signifikantes Bit

100001011000
        ^

Nehmen Sie das Stück nach links

100001011000
       ^

Und erwidere seine Verneinung

0

Aufgabe

Bei einer positiven Ganzzahl als Eingabe wird ausgegeben a(n). (Sie können eine Ganzzahl oder einen Booleschen Wert ausgeben.) Sie sollten darauf abzielen, Ihren Code so klein wie möglich zu machen, gemessen in Bytes.

Testfälle

Hier sind die ersten 100 Einträge in Reihenfolge

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
Weizen-Assistent
quelle
9
Das am wenigsten signifikante Bit von 100001011000ist a 0. Meinst du die geringste Bedeutung 1?
Scatter

Antworten:

16

Mathematica 25 Bytes

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

Andere Möglichkeiten, dies zu tun:

56 Bytes

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

58 Bytes

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&
Kelly Lowder
quelle
3
Wow! Eine mathematische Antwort, die nicht nur eingebaut ist. Habe ein positives Votum!
KeyWeeUsr
2
Das einzige, was diese Antwort noch verbessern könnte, ist eine Erklärung, warum und wie es funktioniert. : P
Martin Ender
2
@MartinEnder arxiv.org/pdf/1408.5770.pdf Siehe Anmerkung nach Beispiel 13.
alephalpha
7

Python 3 , 22 21 Bytes

1 Byte dank ETHproductions.

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

Probieren Sie es online!

Bitweise Arithmetik ftw.

Undichte Nonne
quelle
2
"Sie können als Ganzzahl oder als Boolescher Wert ausgeben", also brauchen Sie das wohl nicht 0+(...)?
Martin Ender
Die Reihenfolge der Operationen hier verwirrt mich wirklich. Könnte n&1in Klammern gesetzt werden? Oder 1+(n^~-n)<1kann das in Klammern gesetzt werden? Oder ist es 1+(n^~-n)...
ETHproductions
oh Gott was. das ist wonach ich gesucht habe: o schön!
HyperNeutrino
&hat die niedrigste Priorität, so ist es1+(n^~-n)
Leaky Nun
Ah, ich habe die Rangfolge-Tabelle gefunden. Jetzt macht alles Sinn: P
ETHproductions
6

Netzhaut ,38 34 29 Bytes

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

Probieren Sie es online!

Martin und Leaky hatten im Wesentlichen diese Idee, um 5 Bytes mehr zu sparen!

Wandelt die Eingabe in eine unäre um und dividiert die Zahl dann schrittweise durch 2. Wenn dies nicht mehr gleichmäßig möglich ist (dh die Zahl ist ungerade), werden Patches von 4 aus der Eingabe entfernt und das Ergebnis der letzten Operation Mod 4 berechnet Schließlich wird geprüft, ob das Ergebnis 1 war, was bedeutet, dass die Ziffer links vom niedrigstwertigen 1-Bit Null war. Wenn dies zutrifft, ist das Endergebnis 1, andernfalls ist es Null.

FryAmTheEggman
quelle
31 Bytes (sollte ich es selbst posten?)
Undichte Nonne
Ich habe einen Weg gefunden, die vollständige Binärkonvertierung
Martin Ender
@ MartinEnder im Wesentlichen mein Algorithmus ... mit 2 Bytes aus
Leaky Nun
@LeakyNun Oh ja, sie sind beide die gleiche Idee. Großartige Köpfe und so ...;)
Martin Ender
Ich bearbeite das in, aber wenn einer von euch es veröffentlichen möchte, werde ich es zurücksetzen, da ich selbst wahrscheinlich nicht daran gedacht hätte;)
FryAmTheEggman
6

Gelee , 5 Bytes

&N&HṆ

Probieren Sie es online!

Wie es funktioniert

&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
quelle
4

Alice , 8 Bytes

I2z1xnO@

Probieren Sie es online!

Übernimmt die Eingabe als Codepunkt eines Unicode-Zeichens und gibt das Ergebnis entsprechend als 0x00- oder 0x01-Byte aus.

Aus Gründen der Testbarkeit ist hier eine dezimale E / A-Version mit 12 Byte angegeben, die denselben Algorithmus verwendet (nur die E / A sind unterschiedlich):

/o
\i@/2z1xn

Probieren Sie es online!

Wenn Alice eine Golfsprache wäre und keine explizite Eingabe / 2z1xnAusgabe und Programmbeendigung erfordern würde, würde dies mit nur 5 Bytes ( ) eintakten, die sowohl 05AB1E als auch Jelly schlagen.

Erläuterung

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
quelle
3

Wise , 28 20 16 Bytes

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

Probieren Sie es online!

Erläuterung

Dies ist eine Portierung von Leaky Nuns Python-Antwort. TIO funktioniert leider nicht, da die Version des Interpreters von TIO etwas veraltet ist.

Wir beginnen damit, 3 Kopien unserer Eingabe mit zu ::erstellen, und dekrementieren dann die oberste Kopie um 1. Dadurch werden alle Bits bis zur ersten 1 hochgeklappt. Anschließend xor dies mit einer weiteren Kopie unserer Eingabe. Da alle Bits bis zur ersten 1 an unserem Eingang umgedreht wurden, haben alle diese Bits 1 im Ergebnis. Wenn wir dann eins ~-zum Ergebnis hinzufügen , erhalten wir eine einzelne 1 an der Stelle links von unserer niedrigstwertigen 1. Wir UND dies mit der Eingabe, um das Bit von der Eingabe zu erhalten. Jetzt haben wir 0iff das Bit war aus und eine Potenz von 2 iff das Bit war an, können wir dies in eine einzelne 1oder 0mit ändern :[?>]. Sobald dies erledigt ist, müssen wir nur das Bit negieren ~-^und wir sind fertig.

Weizen-Assistent
quelle
3

Haskell , 45 43 39 Bytes

6 Bytes gespart dank nimi

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

Probieren Sie es online!

Weizen-Assistent
quelle
Sie können divanstelle von verwenden quot.
Nimi
Noch besser: divMod:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
nimi
@nimi Ich verstehe nicht einmal, wie das funktioniert. Du solltest es wahrscheinlich einfach selbst posten.
Weizen-Assistent
Es ist immer noch der gleiche Algorithmus, sondern nur eine andere Art und Weise um die Verzweigung zu wählen (rekursiv f wieder aufrufen vs. Basisfall), so frei zu bearbeiten fühlen es in. |(d,m)<-divMod x 2Ist ein Muster Wache zu binden dan div x 2und man mod x 2. Wir verwenden, mum die Liste mit zwei Elementen zu indizieren [...,...]!!m. Im Falle einer m==0Rückkehr mod(1+d)2und im Falle von m==1 f d.
Nimi
1
Oh, sorry, Sie haben die Listenelemente kippen: [f d,mod(1+d)2]. Probieren Sie es online! .
Nimi
3

x86-Maschinencode, 17 16 15 Byte:

Es wird ein ABI angenommen, bei dem die Parameter auf den Stack übertragen werden und der Rückgabewert im ALRegister enthalten ist.

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

Dies wird wie folgt zerlegt:

_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
quelle
1
@ PeterTaylor Ich zähle die Größe des CPU-Befehls in Byte für meine Antwort. Dies ist bei PPCG für Assembly-Antworten eine weit verbreitete Praxis.
Govind Parmar
1
Ich konnte nicht sagen, wie häufig es ist, aber es ist definitiv falsch
Peter Taylor
1
Es ist nicht nur umständlich, sondern auch bedeutungslos. In Bezug auf einen Computer gibt es keinen Unterschied zwischen "Maschinencode" und "Baugruppencode". Der Unterschied besteht lediglich in der Interpretation. Wir weisen Maschinencode-Bytes Mnemoniken zu, um sie für den Menschen leichter lesbar zu machen. Mit anderen Worten, wir lösen die Bytes auf, um sie verständlicher zu machen.
Cody Grey
3
Das ist irrelevant, @Peter. Der Assembler-Code ist nur eine für Menschen lesbare Übersetzung des Maschinencodes. Sie sind genau die gleiche Sprache, nur in zwei verschiedenen Formen / Darstellungen. Es ist nicht anders als bei TI BASIC, wo allgemein anerkannt wird, dass wir Token anstelle von Zeichenbytes zählen, da diese vom System intern gespeichert werden. Gleiches gilt für die Assemblersprache: Die Anweisungsmnemoniken werden nicht als einzelne Zeichen gespeichert, sondern als Bytes des entsprechenden Maschinencodes dargestellt.
Cody Grey
2
Außerdem, praktisch gesehen, warum sollte jemand jemals an erweiterten Assembler-Mnemoniken in einem Code-Golf-Wettbewerb teilnehmen, wenn er sie in 100% äquivalenten Maschinencode übersetzen könnte, bei dem der Eintrag garantiert kostenlos kürzer ist? Das allein macht eine Unterscheidung zwischen den beiden sinnlosen, wenn nicht völlig absurden.
Cody Grey
3

JavaScript (ES6), 17 14 Bytes

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

Bearbeiten: 3 Bytes durch Portierung von @ Dennis Antwort gespeichert, als ich bemerkte, dass die boolesche Ausgabe akzeptabel war.

Neil
quelle
3

C (gcc) , 20 Bytes

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

Probieren Sie es online!

Dennis
quelle
Das "funktioniert" eigentlich nicht; Sie verlassen sich auf eine Besonderheit des Codegenerators für eine bestimmte Version des Compilers, die auf eine bestimmte Architektur abzielt, wobei Zwischenberechnungen in demselben Register ausgeführt werden, das für Rückgabewerte verwendet wird. Wenn Sie eine beliebige Art der Optimierung aktivieren, die Zielarchitektur ändern oder eine andere Version von GCC verwenden, wird dies nicht mehr funktionieren. Sie könnten genauso gut einfach sagen "Der Müll auf meinem Stapel enthält die richtige Ausgabe, wenn am 13. Oktober Vollmond ist".
Cody Grey
Während alles, was Sie sagen, wahr ist und Code wie dieser niemals im Produktionscode verwendet wird, definieren wir Sprachen durch ihre Implementierungen für die Zwecke des Codegolfs. Ohne zusätzliche Flags funktioniert dies in allen aktuellen Versionen von gcc und tcc und es muss nur in einer Version funktionieren , um als gültig zu gelten.
Dennis
"Wir definieren Sprachen durch ihre Implementierungen zum Zwecke des Codegolfs." Warten Sie, was? Also definiert jedes Compiler-Flag und jede Version von GCC eine andere Sprache? Sie erkennen, dass das verrückt ist, oder? Der C-Sprachstandard definiert die Sprache.
Cody Grey
Nicht hier. Wenn es einen C-Standard, aber keine Implementierung gäbe, würden wir ihn nicht einmal als Sprache betrachten. Wie ich bereits sagte, definiert der Compiler die Sprache . Infolgedessen ist es zulässig , sich auf undefiniertes Verhalten zu verlassen . Ein anderer Satz von Flags wird nicht als andere Sprache betrachtet. Wenn Sie sie jedoch nicht zu Ihrer Byteanzahl hinzufügen, verwenden alle Antworten Standard-Kompilierungsflags.
Dennis
Wow. Das ist verrückt. Ich könnte verstehen, wenn Sie sagen, dass implementierungsdefiniertes Verhalten zulässig ist, undefiniertes Verhalten jedoch nicht von der Implementierung definiert wird. Es ist buchstäblich undefiniert. Die Implementierung darf jedes Mal zufällige Dinge tun. Und diese Vorstellung von "Standard-Kompilierungsflags" haben Sie gerade erfunden. Meine Standard-Kompilierungsflags enthalten mehrere, die Ihren Code beschädigen. Und ich denke kaum, dass der Optimierer nicht dem Standard entspricht. Na klar, diese Seite ist nichts für mich.
Cody Grey
3

INTERCAL , 50 Bytes

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

INTERCALs unäre Operatoren sind dafür sehr gut geeignet, deshalb habe ich beschlossen, meinen ersten Beitrag zu schreiben.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP
Bernd Fischer
quelle
3

Haskell , 33 Bytes

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

Probieren Sie es online!

Verwendet die 0-Indizierung.

Anders Kaseorg
quelle
1
Was macht der ~in diesem Zusammenhang? Ich verstehe, dass es ein Lazy Match ist, aber warum brauchst du ein Lazy Match?
Weizen-Assistent
2

Gelee , 7 6 Bytes

1 Byte danke an Erik den Outgolfer.

Bt0ṖṪṆ

Probieren Sie es online!

Längere Programme

Undichte Nonne
quelle
Hmm ... na ja, das kannst du einfach machen ṖṪṆ(wie meine gelöschte Antwort) anstatt ṫ-ḄỊ.
Erik der Outgolfer
1
Ein weiteres für Ihre 7-Byte-Liste:BUḌDḊḢ¬
steenbergh
2

,,, , 10 9 Bytes

::0-&2*&¬

Erläuterung

Nehmen Sie zum Beispiel die Eingabe 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                             []
total menschlich
quelle
2

Oktave , 34 Bytes

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

Probieren Sie es online!

Erläuterung:

@(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
quelle
Wieso habe ich noch nie von de2bi gehört ...: O
Sanchises
1

Einreichung:

Python 2 , 41 39 Bytes

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

Probieren Sie es online!

-2 Bytes dank FryAmTheEggman

Anfangslösung:

Python 2 , 43 Bytes

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

Probieren Sie es online!

HyperNeutrino
quelle
Welches ist Ihr Beitrag?
Undichte Nonne
@LeakyNun Der erste, weil er kürzer ist; Die zweite war meine ursprüngliche Vorlage. Soll ich sie separat posten?
HyperNeutrino
~-x&1funktioniert stattdessen für die while-Bedingung, denke ich.
FryAmTheEggman
(Ich vergesse den Benutzernamen); Ich habe Ihre Bearbeitung abgelehnt, da Änderungen am Code anderer Personen in PPCG nicht empfohlen werden. Sie können Vorschläge posten (übrigens, danke @FryAmTheEggman), aber bitte nehmen Sie keine Golfbearbeitungen vor. Vielen Dank!
HyperNeutrino
@StewieGriffin Ah ja, danke. Leider kann ich den Benutzer nicht anpingen, da die Bearbeitung abgelehnt wurde.
HyperNeutrino
1

MATL , 11 10 Bytes

t4*YF1)Z.~

Probieren Sie es online! Oder sehen Sie sich die ersten 100 Ausgänge an .

Erläuterung

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
quelle
1

Befunge-98 , 19 Bytes

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

Probieren Sie es 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
quelle
1

SCALA, 99 (78?) Zeichen, 99 (78?) Bytes

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

wo iist der eingang.

Wie Sie sehen, spare ich 21 Bytes, wenn ich mich nicht um die Null kümmere (wie es der Autor in seinem Testfall getan hat):

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

Dies ist mein erster Codegolf, also hoffe ich, dass ich es gut gemacht habe :)

Probieren Sie es online! Obwohl es ziemlich lang ist, lol zu berechnen.

V. Courtois
quelle
Willkommen auf der Seite!
DJMcMayhem
1

Java 8, 17 Bytes

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

Einfache Portierung der Python 3-Antwort von LeakyNun . Ich bin mit bitweisen Operationen und der Rangfolge von Operatoren nicht vertraut genug, um eine kürzere Lösung zu finden. Vielleicht gibt es eine Möglichkeit, die zusätzliche Elternschaft zu vermeiden?

JollyJoker
quelle
0

Japt , 10 8 9 Bytes

!+¢g¢a1 É

Probieren Sie es online!

Erläuterung

!+¢   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
quelle
Dies wird falsefür alles zurückgegeben, da das Zeichen (0 oder 1) immer eine Zeichenfolge ist.
Shaggy
Hoppla, hätte beachten sollen, dass ... Jetzt behoben
Luke
Sieht so aus, als ob es vorerst fehlschlägt1 .
Shaggy
0

JavaScript (ES6), 53-34 Byte

a=>eval("for(;~a&1;a/=2);~a>>1&1")
Luke
quelle
42 Bytes:a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
Shaggy
Ich habe bereits eine kürzere (mathematische) Lösung gefunden ...
Luke
Schön :) Stört es mich, wenn ich das 42-Byte-eins poste?
Shaggy
@ Shaggy, nein überhaupt nicht
Luke
0

Chip , 93 Bytes

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

Nimmt die Eingabe als Little-Endian-Bytes. (Das TIO hat ein bisschen Python, das dies für Sie erledigt). Gibt entweder 0x0oder aus0x1 . (Der TIO prüft den Wert mit xxd).

Probieren Sie es online!

Wie geht das?

Der Chip betrachtet die Eingabe Byte für Byte. Bei der Verarbeitung von Multibyte-Eingaben wird ein gewisser Speicherplatz hinzugefügt, der jedoch nicht so groß ist, wie ich befürchtet hatte.

Lassen Sie uns darauf eingehen:

HZABCDEFG

Dies sind das HZHigh-Bit des vorherigen Bytes (falls vorhanden) und A- Gdie sieben unteren Bits des aktuellen Bytes. Diese werden verwendet, um das niedrigste gesetzte Bit der Zahl zu lokalisieren.

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

Wenn das niedrigste gesetzte Bit gefunden wird, haben wir ein paar Dinge zu tun. Dieser erste Block sagt: "Wenn wir ein gesetztes Bit (das )s) haben, Shören Sie auf, die Ausgabe zu tunterdrücken , und löschen Sie, nachdem wir die Antwort gedruckt haben.

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

Welchem ​​Bit des aktuellen Bytes ( A- H) nur ein Bündel von Nullen vorausgeht, dann eine Eins ( \und /: diese sehen die Bits direkt nördlich davon; wir können darauf vertrauen, dass alle vorherigen Bits Null waren), wird an die Drähte weitergeleitet das Recht ( v, ', ...), je nachdem , was dann Wert wird invertiert und als den Low - Bit des Ausgangs gegeben ( ~a).

Phlarx
quelle