Einführung
Ein Gray-Code ist eine Alternative zur binären Darstellung, bei der eine Zahl durch Umschalten nur eines Bits anstatt einer variablen Anzahl von Bits inkrementiert wird. Hier sind einige Graucodes zusammen mit ihren Dezimal- und Binäräquivalenten:
decimal | binary | gray
-------------------------
0 | 0 | 0
-------------------------
1 | 1 | 1
-------------------------
2 | 10 | 11
-------------------------
3 | 11 | 10
-------------------------
4 | 100 | 110
-------------------------
5 | 101 | 111
-------------------------
6 | 110 | 101
-------------------------
7 | 111 | 100
-------------------------
8 | 1000 | 1100
-------------------------
9 | 1001 | 1101
-------------------------
10 | 1010 | 1111
-------------------------
11 | 1011 | 1110
-------------------------
12 | 1100 | 1010
-------------------------
13 | 1101 | 1011
-------------------------
14 | 1110 | 1001
-------------------------
15 | 1111 | 1000
Zyklisches Bitmuster eines Gray Codes
Manchmal als "gespiegelte Binärdatei" bezeichnet, wird die Eigenschaft, immer nur ein Bit zu ändern, leicht mit zyklischen Bitmustern für jede Spalte erreicht, beginnend mit dem niedrigstwertigen Bit:
bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111
...und so weiter.
Zielsetzung
Inkrementieren Sie bei einer nicht aufgefüllten Eingabezeichenfolge eines Gray-Codes den Gray-Code, indem Sie ein einzelnes Zeichen in der Sequenz abwechseln oder a voranstellen 1
(beim Inkrementieren zur nächsten Zweierpotenz ), und geben Sie dann das Ergebnis als nicht aufgefüllten Gray-Code aus.
Vorbehalte
- Machen Sie sich keine Sorgen,
0
wenn Sie eine leere Zeichenfolge als Eingabe verwenden. - Die niedrigste Eingabe
1
ist und es gibt keine Obergrenze für die Zeichenfolgenlänge außer den durch die Umgebung auferlegten Speicherbeschränkungen. - Mit ungepolsterter Zeichenfolge meine ich, dass es kein führendes oder nachfolgendes Leerzeichen (außer einem optionalen nachfolgenden Zeilenumbruch) und keine führenden Zeichen
0
in der Eingabe oder Ausgabe gibt.
E / A-Formate
Die folgenden Formate werden als Eingabe- und Ausgabeformate akzeptiert, Zeichenfolgen werden jedoch gegenüber anderen Formaten empfohlen:
- höchstwertiges "Bit" zuerst
- unwattierter Zeichen - Array oder eine Kette von ASCII
'1'
s und'0'
s - ungepolstertes Integer-Array von
1
s und0
s - nicht gepolstertes boolesches Array
Was ist nicht erlaubt:
- niedrigstwertiges "Bit" zuerst
- Dezimalzahl, binäre oder unäre Ganzzahl
- Datenstruktur mit fester Länge
- Zeichenarray oder Zeichenfolge aus nicht druckbaren ASCII-Indizes
1
und0
Tests
input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000
Weitere Tests können auf Anfrage hinzugefügt werden.
Kriterien
Das ist Code-Golf , also gewinnt das kürzeste Programm in Bytes! Alle Bindungen werden durch die Bevorzugung früherer Einreichungen aufgehoben; Es gelten Standardlücken. Die am besten eingereichte Antwort wird am 9. Oktober 2016 akzeptiert und aktualisiert, sobald bessere Antworten gegeben werden.
quelle
0011
für 8Antworten:
Jelly ,
108 BytesVielen Dank an Dennis für das Speichern von 2 Bytes.
Ein- und Ausgabe sind Listen mit 0s und 1s.
Probieren Sie es online!
Erläuterung
Die Umkehrung des Gray-Codes ist durch A006068 gegeben . Auf diese Weise müssen wir keine große Anzahl von Gray-Codes generieren, um die Eingabe nachzuschlagen. Eine Klassifizierung dieser auf OEIS angegebenen Sequenz lautet wie folgt:
Wo
[]
sind die Bodenklammern. Betrachten Sie das Beispiel,44
dessen binäre Darstellung ist101100
. Teilen durch 2 und Flooring ist nur eine Rechtsverschiebung, die das niedrigstwertige Bit abhackt. Wir versuchen also, die folgenden Zahlen zu XORENBeachten Sie, dass die
n
dritte Spalte die erstenn
Bits enthält . Daher kann diese Formel für die Binäreingabe trivial als die kumulative Reduktion von XOR über die Liste berechnet werden (wobei grundsätzlich XOR auf jedes Präfix der Liste angewendet wird und eine Liste der Ergebnisse erstellt wird).Dies gibt uns eine einfache Möglichkeit, den Gray-Code umzukehren. Anschließend erhöhen wir das Ergebnis und konvertieren es zurück in den Gray-Code. Für den letzten Schritt verwenden wir die folgende Definition:
Zum Glück scheint Jelly die Eingaben automatisch zu blockieren, wenn er versucht, sie zu XORen. Wie auch immer, hier ist der Code:
quelle
Ḟ$
; bitweise Operatoren umgewandelt in int .JavaScript (ES6), 58 Byte
Schaltet das entsprechende Bit direkt um. Erläuterung: Wie in MartinEnders Antwort gezeigt, ist jedes Bit in einem decodierten Gray-Code das kumulative XOR oder die Parität von sich selbst und den Bits zu seiner Linken. Wir müssen dann die Zahl inkrementieren, die eine Übertrag-Welligkeit verursacht, die alle am weitesten rechts liegenden 1-Bits auf 0 und dann das nächste 0-Bit auf 1 umschaltet. Die Neucodierung führt zu einem Code, bei dem nur diese eine 0-Bit-Position umgeschaltet ist. Wenn die Parität aller 1-Bits gerade ist, ist das Bit ganz rechts 0 und wir schalten daher nur das letzte Bit um. Wenn die Parität aller 1 Bits ungerade ist, sind die am weitesten rechts stehenden Bits 1, und wir müssen das letzte 1 Bit finden. Dies ist nun das letzte der übertragenen Bits. Das Bit, das umgeschaltet werden muss, ist das nächste Bit von rechts.
quelle
?
in/.?(?=10*$)/
wirklich erforderlich? Vergiss es. Ja ist es. :-)Perl,
2725 BytesBeinhaltet +1 für
-p
Geben Sie einen Eingabestring für STDIN ein, z
gray.pl
:Perl hat keine billigen Ganzzahlen mit unendlicher Genauigkeit. Schalten Sie also direkt das rechte Bit um, das genau vor dem Bit mit der letzten ungeraden Nummer 1 liegt.
quelle
\G
das macht es dir wirklich leicht!\K
macht es die Sache für Sie noch einfacher.\G
Implementierung sehen.Haskell,
118 115108 BytesProbieren Sie es auf Ideone.
Naiver Ansatz:
g
Erzeugt die Menge aller Gray-Codes mit Längen
(mit 0-Auffüllung),f
ruftg
mit auflength(input)+1
, entfernt alle Elemente, bis sie0<inputstring>
gefunden werden, und gibt das nächste Element zurück (wobei ein möglicherweise führendes Element abgeschnitten wird0
).quelle
MATL , 18 Bytes
Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
Lassen a ( n ) zu Gray - Codes entsprechen , um die Folge von ganzen Zahlen bezeichnen ( OEIS A003188 ). Das Programm verwendet die Charakterisierung a ( n ) = n XOR-Floor ( n / 2), wobei XOR bitweise ist.
Im Wesentlichen konvertiert der Code die Eingabe in eine Ganzzahl a 0 , findet diese Ganzzahl in der Sequenz und wählt dann den nächsten Term aus. Dies erfordert die Erzeugung einer ausreichend großen Anzahl von Termen der Sequenz a ( n ). Es zeigt sich, dass 2 · a 0 ausreichend groß ist. Dies ergibt sich aus der Tatsache, dass der Gray-Code a ( n ) niemals mehr Binärziffern als n hat .
Nehmen wir
'101'
als Beispiel die Eingabe .quelle
CJam (19 Bytes)
Online-Demo . Dies ist ein anonymer Block (Funktion) von Bit-Array zu Bit-Array, den die Demo in einer Schleife ausführt.
Es funktioniert nach dem einfachen Prinzip, dass wir, wenn die Anzahl der gesetzten Bits gerade ist, das niedrigstwertige Bit umschalten sollten, und andernfalls das Bit links vom niedrigstwertigen gesetzten Bit umschalten sollten. Es stellt sich heraus, dass das Identifizieren dieses Bits mit Bit-Hacks für eine Ganzzahl viel einfacher ist als mit der Liste der Bits.
Präparation
Ich denke, es ist notwendig, nur mit dem Bit-Array zu arbeiten, da es
1
viel einfacher ist , mit dem ganz linken als mit dem ganz rechten zu arbeiten. Das Beste, was ich bisher gefunden habe, ist (24 Bytes):Alternativer Ansatz (19 Byte)
Dies konvertiert von Gray-Code in Index, inkrementiert und konvertiert zurück in Gray-Code.
quelle
JavaScript (ES6), 53 Byte (nicht konkurrierend)
Eine rekursive Funktion, die alle Gray-Codes aufbaut, bis die Eingabe gefunden wurde, und bei der nächsten Iteration stoppt.
Die höchstmögliche Eingabe hängt vom Rekursionslimit des Browsers ab (ungefähr 13 Bit in Firefox und 15 Bit in Chrome).
quelle
--harmony
für Strafbytes hinzugefügt werden, um Zugriff auf die Optimierung der Tail-Call-Rekursion zu haben, was hier möglich zu sein scheint.Retina, 25 Bytes
Ich bin mir sicher, dass es einen besseren Weg geben sollte, dies zu tun ...
quelle
^
?05AB1E , 12 Bytes
Verwendet die CP-1252- Codierung.
Probieren Sie es online!
Erläuterung
Beispiel für Eingabe 1011 .
quelle
Python 2.7, 68 Zeichen
Python 3, 68 Zeichen
Diese Funktion konvertiert die angegebene Binärzeichenfolge in eine Ganzzahl und x oder das letzte Bit, wenn die Anzahl der gesetzten Bits in der ursprünglichen Zeichenfolge gerade ist, oder vertauscht das Bit links vom ganz rechts gesetzten Bit, wenn die Anzahl der gesetzten Bits im Original ist Zeichenfolge ist ungerade. Dann konvertiert es das Ergebnis in eine Binärzeichenfolge und entfernt das
0b
boolesche Präfix.quelle
def f(s):
und (unter der Annahme von Python 2) ein anderes entfernen, indem Sieprint
anstelle von verwendenreturn
.int()
eine 32-Bit-Ganzzahl generiert, obwohl Sie unbedingt eine beliebige Zeichenfolge inkrementieren müssen. Ich bin mir nicht sicher, ob dies als gültige Einsendung qualifiziert istlong
anstattint
vielleicht das Problem zu lösen.C ++, 205 Bytes
Beschreibung: Gerade Zahlen haben gerade Anzahl von Einsen. Variable
z
zählt diejenigen; ifz
ist gerade (z mod 2 = z%2 = 0
- else branch), ändere das letzte Bit; Wennz
ungerade ist, rufen Sie diese Funktion erneut ohne das letzte Zeichen auf und berechnen Sie einen neuen Wert. Fügen Sie anschließend das letzte Zeichen hinzu.Klicken Sie hier, um die Testfälle zu testen.
quelle
Batch,
199197 BytesLiest die Eingabe von STDIN in die Variable
s
. Entfernt die Nullen und führt eine Paritätsprüfung für die Einsen durch. Wenn eine ungerade Zahl vorhanden ist, werden die Nullen ganz rechts in einer Schleife entfernt und angehalten, wenn eine 1 entfernt wird.s
Daher enthält das Präfix für die gerade Parität undr
den Rest der Zeichenfolge.s
wird auf Null gesetzt, wenn es leer war, damit die letzte Ziffer umgeschaltet werden kann, und dann wird alles verkettet.quelle
Eigentlich
201913 BytesBasierend auf Martin Enders Jelly-Antwort mit meiner eigenen Version von "kumulative Reduzierung von XOR über die Eingabe". Golfvorschläge sind willkommen. Probieren Sie es online!
Ungolfing
quelle
J, 38 Bytes
Probieren Sie es online!
Dies ist im Wesentlichen Martins Algorithmus in J.
Beachten Sie, dass dies
22 b.
XOR ist.quelle