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
100001011000
ist a0
. Meinst du die geringste Bedeutung1
?Antworten:
Mathematica 25 Bytes
Andere Möglichkeiten, dies zu tun:
56 Bytes
58 Bytes
quelle
Python 3 ,
2221 Bytes1 Byte dank ETHproductions.
Probieren Sie es online!
Bitweise Arithmetik ftw.
quelle
0+(...)
?n&1
in Klammern gesetzt werden? Oder1+(n^~-n)<1
kann das in Klammern gesetzt werden? Oder ist es1+(n^~-n)
...&
hat die niedrigste Priorität, so ist es1+(n^~-n)
Netzhaut ,
383429 BytesProbieren 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.
quelle
Gelee , 5 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Alice , 8 Bytes
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):
Probieren Sie es online!
Wenn Alice eine Golfsprache wäre und keine explizite Eingabe /
2z1xn
Ausgabe und Programmbeendigung erfordern würde, würde dies mit nur 5 Bytes ( ) eintakten, die sowohl 05AB1E als auch Jelly schlagen.Erläuterung
quelle
05AB1E , 6 Bytes
Probieren Sie es online!
quelle
Wise ,
282016 BytesProbieren 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 wir0
iff das Bit war aus und eine Potenz von 2 iff das Bit war an, können wir dies in eine einzelne1
oder0
mit ändern:[?>]
. Sobald dies erledigt ist, müssen wir nur das Bit negieren~-^
und wir sind fertig.quelle
Python 2 , 19 Bytes
Probieren Sie es online!
quelle
Haskell ,
454339 Bytes6 Bytes gespart dank nimi
Probieren Sie es online!
quelle
div
anstelle von verwendenquot
.divMod
:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
|(d,m)<-divMod x 2
Ist ein Muster Wache zu bindend
andiv x 2
undm
anmod x 2
. Wir verwenden,m
um die Liste mit zwei Elementen zu indizieren[...,...]!!m
. Im Falle einerm==0
Rückkehrmod(1+d)2
und im Falle vonm==1
f d
.[f d,mod(1+d)2]
. Probieren Sie es online! .x86-Maschinencode,
171615 Byte:Es wird ein ABI angenommen, bei dem die Parameter auf den Stack übertragen werden und der Rückgabewert im
AL
Register enthalten ist.Dies wird wie folgt zerlegt:
quelle
JavaScript (ES6),
1714 BytesBearbeiten: 3 Bytes durch Portierung von @ Dennis Antwort gespeichert, als ich bemerkte, dass die boolesche Ausgabe akzeptabel war.
quelle
C (gcc) , 20 Bytes
Probieren Sie es online!
quelle
INTERCAL , 50 Bytes
INTERCALs unäre Operatoren sind dafür sehr gut geeignet, deshalb habe ich beschlossen, meinen ersten Beitrag zu schreiben.
quelle
Haskell , 33 Bytes
Probieren Sie es online!
Verwendet die 0-Indizierung.
quelle
~
in diesem Zusammenhang? Ich verstehe, dass es ein Lazy Match ist, aber warum brauchst du ein Lazy Match?Gelee ,
76 Bytes1 Byte danke an Erik den Outgolfer.
Probieren Sie es online!
Längere Programme
Họ¡2&2Ị
Bt0ṫ-ḄỊ
quelle
ṖṪṆ
(wie meine gelöschte Antwort) anstattṫ-ḄỊ
.BUḌDḊḢ¬
,,, ,
109 BytesErläuterung
Nehmen Sie zum Beispiel die Eingabe 3.
quelle
Haskell , 26 Bytes
Probieren Sie es online!
Boolesche Ausgabe.
quelle
Oktave , 34 Bytes
Probieren Sie es online!
Erläuterung:
quelle
Einreichung:
Python 2 ,
4139 BytesProbieren Sie es online!
-2 Bytes dank FryAmTheEggman
Anfangslösung:
Python 2 , 43 Bytes
Probieren Sie es online!
quelle
~-x&1
funktioniert stattdessen für die while-Bedingung, denke ich.MATL ,
1110 BytesProbieren Sie es online! Oder sehen Sie sich die ersten 100 Ausgänge an .
Erläuterung
quelle
Pari / GP , 20 Bytes
Verwendung der Kronecker-Symbol .
Probieren Sie es online!
quelle
Befunge-98 , 19 Bytes
Probieren Sie es online!
quelle
SCALA, 99 (78?) Zeichen, 99 (78?) Bytes
wo
i
ist 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):
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.
quelle
C (gcc) ,
35-31BytesZu einer rekursiven Implementierung gewechselt. Probieren Sie es online!
quelle
Java 8, 17 Bytes
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?
quelle
Japt ,
10 89 BytesProbieren Sie es online!
Erläuterung
quelle
false
für alles zurückgegeben, da das Zeichen (0 oder 1) immer eine Zeichenfolge ist.1
.JavaScript (ES6),
53-34Bytequelle
a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
PHP> = 7.1, 32 Bytes
PHP Sandbox Online
PHP , 40 Bytes
Probieren Sie es online!
PHP , 41 Bytes
Probieren Sie es online!
quelle
Common Lisp, 56 Bytes
Probieren Sie es online!
quelle
Chip , 93 Bytes
Nimmt die Eingabe als Little-Endian-Bytes. (Das TIO hat ein bisschen Python, das dies für Sie erledigt). Gibt entweder
0x0
oder 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:
Dies sind das
HZ
High-Bit des vorherigen Bytes (falls vorhanden) undA
-G
die sieben unteren Bits des aktuellen Bytes. Diese werden verwendet, um das niedrigste gesetzte Bit der Zahl zu lokalisieren.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,S
hören Sie auf, die Ausgabe zut
unterdrücken , und löschen Sie, nachdem wir die Antwort gedruckt haben.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
).quelle