Für Nandgame-Fans: Bitte probieren Sie DPD auch in Logikgattern mit Dezimalstellen aus !
Hintergrund
Dicht gepackte Dezimalstellen (DPD) sind eine Möglichkeit, Dezimalstellen in Binärform effizient zu speichern. Es speichert drei Dezimalstellen (000 bis 999) in 10 Bit, was viel effizienter ist als naives BCD (das eine Stelle in 4 Bit speichert).
Notizen
- Die Kleinbuchstaben
a
bisi
sind die Bits, die in die Dezimaldarstellung kopiert werden. 0
und1
sind die genauen Bits in den Eingabe- oder Ausgabebitmustern.x
Bits werden bei der Konvertierung ignoriert.
Umrechnungstabelle
Das Folgende ist die Umwandlungstabelle von 10 Bit DPD in drei Dezimalstellen. Jede Dezimalstelle wird als 4-Bit-Binärzahl (BCD) dargestellt. Beide Seiten werden von links nach rechts von der höchstwertigen bis zur niedrigsten Stelle geschrieben.
Bits => Decimal (Digit range)
a b c d e f 0 g h i => 0abc 0def 0ghi (0-7) (0-7) (0-7)
a b c d e f 1 0 0 i => 0abc 0def 100i (0–7) (0–7) (8–9)
a b c g h f 1 0 1 i => 0abc 100f 0ghi (0–7) (8–9) (0–7)
g h c d e f 1 1 0 i => 100c 0def 0ghi (8–9) (0–7) (0–7)
g h c 0 0 f 1 1 1 i => 100c 100f 0ghi (8–9) (8–9) (0–7)
d e c 0 1 f 1 1 1 i => 100c 0def 100i (8–9) (0–7) (8–9)
a b c 1 0 f 1 1 1 i => 0abc 100f 100i (0–7) (8–9) (8–9)
x x c 1 1 f 1 1 1 i => 100c 100f 100i (8–9) (8–9) (8–9)
Aufgabe
Konvertieren Sie 10 Bit DPD in 3 Dezimalstellen.
Testfälle
DPD Decimal
0000000101 005
0001100011 063
0001111001 079
0000011010 090
0001011110 098
1010111010 592
0011001101 941
1100111111 879
1110001110 986
0011111111 999
1111111111 999 * Output is same regardless of the `x` bits
Eingang
Das Standardeingabeformat ist eine Liste mit 10 Bits. Die Bits sollten der genauen Reihenfolge oben oder der umgekehrten Reihenfolge folgen. Sie können stattdessen eine äquivalente Zeichenfolge oder eine Ganzzahldarstellung verwenden. Im Gegensatz zu meinen anderen Herausforderungen ist es nicht erlaubt, verschachtelte Strukturen neu anzuordnen oder zu verwenden .
Für die Eingabe [1, 1, 0, 0, 0, 1, 0, 1, 0, 0]
sind folgende Formate zulässig:
- Liste der Bits:
[1, 1, 0, 0, 0, 1, 0, 1, 0, 0]
- Zeichenfolge:
"1100010100"
- Binäre Ganzzahl:
788
oder0b1100010100
- Dezimalzahl:
1100010100
- Umgekehrt:
[0, 0, 1, 0, 1, 0, 0, 0, 1, 1]
und in allen anderen oben genannten Formaten umgekehrt
Die folgenden Formate sind NICHT erlaubt:
- Beliebige Neuordnung von Bits:
[0, 0, 0, 0, 0, 1, 1, 1, 0, 1]
- Verschachtelte Strukturen:
[[1, 1, 0], [0, 0, 1], [0, 1, 0, 0]]
oder[0b110, 0b001, 0b0100]
Ausgabe
Das Standardausgabeformat ist eine Liste mit 3 Dezimalstellen. Jede Ziffer sollte als 0 bis 9 dargestellt werden, entweder als Ganzzahl oder als Zeichen. Wie bei der Eingabe können Sie eine Zeichenfolge oder eine Ganzzahldarstellung auswählen. Wenn Sie die Ganzzahldarstellung wählen, können führende Nullen weggelassen werden.
Bewertungs & Gewinnkriterium
Es gelten die Standardregeln für Code-Golf . Das kürzeste Programm oder die kürzeste Funktion in Bytes für jede Sprache gewinnt.
quelle
Python 3 ,
229 ... 9796 BytesProbieren Sie es online!
-4 Bytes von @xnor
-6 Bytes von @nwellnhof
Formatiert:
Erläuterung
Da ich dies ursprünglich in Jelly implementieren wollte, verfolge ich einen anderen Ansatz als die meisten Antworten hier, der einfach ist und möglicherweise für eine Golfsprache geeignet ist. Obwohl die Golffunktion eine Ganzzahl annimmt, sei die Eingabe eine Bitliste
[a0,a1,...,a9]
. Dann können wir drei Werte aus der Eingabe ableiten[a2,a5,a9]
: Dies sind immer die niedrigen Bits von[d0,d1,d2]
.[2*a0a1,2*a3a4,2*a7a8,8]
: Die hohen Bits jeder Ziffer sind eine davon.[a3,a4,a5,a7,a8]
bestimmen, wie die hohen Bits jeder Ziffer abgerufen werden. Wir berechnen den Indikator (zwischen 1 und 8) wie folgt:Dann kann die n-te Ziffer elegant wie
high_bits[arr[indicator][n]] | low_bits[n]
in der folgenden Tabelle berechnet werden, die zu einer Zeichenfolge komprimiert wird.quelle
b"..."
, um die Konvertierung durch zu ersetzenord
.b"$>6;-/'?"[a&8and(~a&6or a>>4&6|1)]
spart weitere vier Bytes.JavaScript (Node.js) ,
126119117112111 ByteProbieren Sie es online!
-5 Bytes danke @tsh (und 2 von mir) Also
l
kann man sich mehr Mühe geben als ich erwartet hatte.-2 weitere Bytes mit @ tshs Technik!
-5 Bytes danke @Arnauld
-1 Byte danke @Neil
Eingabe als Liste mit 10 Bits (als 10 Argumente), Ausgabe als Liste mit 3 Ziffern.
quelle
(!i|!d|e)
->i+l!=5
;(d|e|!h)
->h+l!=1
(g?h-i|h&!e?h?b:e:8:h*4+i*2)
->(g?h<i?e:h>i*e?b:8:h*4+i*2)
speichert ein weiteres Byte. (Diesmal habe ich nachgesehen ...)C (GCC) ,
138129 BytesProbieren Sie es online!
Extrahiert zuerst einige Bits in Variablen
s
undt
, so dass die acht Zeilen der Konvertierungstabelle identifiziert werden können durch:Dann richtet
u
undv
mit Teilungen (rechts verschieben), so dassu
,v
und den Eingangw
enthält die unteren drei BCD - Bits in den Positionen 0-2. Der Rest ist je nachs
und ein bisschen schlurfent
. Zwei bemerkenswerte Tricks sind:Ein Port der Javascript-Lösung von Shieru Asakoto hat nur 124 Bytes :
Probieren Sie es online!
quelle
f(b){int a=b/2%8,e=b&110,c=b/16,d=c/8;b=10*(10*(d%2|(6>a|78==e?d:8))+c%2+(3<a&a%2?e-46?8:d&6:c&6))+b%2+(4>a?b&6:a-5?a-6&&e-14?8:d&6:c&6)};
Ruby ,
153 ... 119117 BytesProbieren Sie es online!
Wie es funktioniert:
Dies ist der Ausgangspunkt: Konvertieren Sie zu BCD, indem Sie 3 Bits nach links verschieben, was für die meisten Muster funktioniert.
Holen Sie sich die mittleren Bits jedes Halbbytes (und ein zusätzliches Bit des dritten Halbbytes, aber maskieren Sie das niedrigstwertige Bit).
Wenn die dritte Ziffer kleiner als 10 ist (kleiner als 9, weil wir uns sowieso nie um das LSB gekümmert haben), sind wir eingestellt: Dies ist einfaches BCD, wir können das Hex ausgeben, ohne etwas zu ändern
Ansonsten machen Sie etwas schwarze Magie, indem Sie Bits verschieben und magische Zahlen hinzufügen, bis Sie das gewünschte Ergebnis erzielen.
quelle
Retina 0.8.2 ,
191181 BytesProbieren Sie es online! Link enthält Testfälle. Bearbeiten: Speichert 10 Byte, indem die Ziffern nur bei Bedarf mit 4 Bit aufgefüllt werden. Erläuterung:
Fügen Sie Trennzeichen ein, damit jede Ziffer einzeln in Dezimalzahlen umgewandelt werden kann. Dies behandelt effektiv die ersten beiden Fälle in der Konvertierungstabelle.
Behandeln Sie den letzten (achten) Fall in der Umrechnungstabelle.
Behandeln Sie den sechsten und siebten Fall in der Umrechnungstabelle.
Behandeln Sie den fünften Fall in der Umrechnungstabelle.
Behandeln Sie den dritten und vierten Fall in der Umrechnungstabelle.
Führen Sie eine Umwandlung von Binär in Dezimal durch.
quelle
Jelly ,
51484039 BytesProbieren Sie es online!
Algorithmus
Mit Ausnahme der Listenindizes sind alle Ganzzahlen in diesem Abschnitt binär geschrieben.
Code
quelle
Python 2 , 157 Bytes
Probieren Sie es online!
quelle
Sauber ,
238... 189 Bytes-2 Bytes dank Neil
Probieren Sie es online!
Nimmt eine 'Liste' von 10 Bits in Form von 10 Argumenten auf, wobei eine direkte Formel zur Berechnung des Ergebnisses verwendet wird.
quelle
i*(9*e+19*d+i*...)
scheint diese Sekundei*
unnötig.Perl 5, 195 Bytes
Probieren Sie es online aus
Ich weiß, 195 Bytes sind viel zu viel für diesen Wettbewerb, aber ich hatte keine Ahnung, wie ich den Perl-Code weiter komprimieren soll. Vorschläge?
Erklärung des Codes
In einer besser lesbaren Version sollte die Codeabsicht offensichtlich werden:
In den Regeln für die DPD-Codierung wird jede Zeile in einen 18-Bit-Wert codiert und in (6,6, (2,2,2)) Bits segmentiert.
@p
für die 3-Bit-Sequenzen, die in die Bits 11-9, 7-5 und 3-1 des Ergebnisses gespleißt werden sollen.@p
besteht aus den Bits 9-8, 6-5, 3-2 der Eingabe und der Zahl8
als viertem ElementZum Beispiel die erste Zahl in der Liste,
16390
die100000000000110
als Bitfeld vorliegt, die folgenden Informationen:quelle
05AB1E , 84 Bytes
Hafen von KimOyhus 'Antwort auf 05AB1E.
Probieren Sie es online!
Grobe Erklärung:
quelle
05AB1E ,
104103101 BytesAuf jeden Fall nicht die richtige Sprache für diese Art von Herausforderung, aber na ja.
Eingabe als Zeichenfolge, Ausgabe als dreistellige Liste.
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
Wir müssen die folgenden acht Szenarien berücksichtigen:
Ich teile zuerst die (implizite) Eingabe in Abschnitte von Größe auf
[2,1,2,1,3,1]
und speichere diese Liste im Register:Sehen Sie sich meinen Tipp 05AB1E (Abschnitt Wie komprimiere ich große ganze Zahlen? ) An, um zu verstehen, warum dies so
•3γã•
ist212131
Jetzt werden zuerst die Nullen und Einsen für die erste Ziffer der Ausgabe erstellt. Szenarien 1,2,3,7 verwenden
'0'+1st+2nd
; und Szenarien 4,5,6,8 verwenden'100'+2nd
:Dann werden wir die Nullen und Einsen für die zweite Ziffer der Ausgabe bilden. Szenarien 1,2,4 verwenden
'0'+3rd+4th
; Szenarien 3,5,7,8 Verwendung'100'+4th
; und Szenario 6 verwendet'0'+1st+4th
:Dann werden wir die Nullen und Einsen für die dritte Ziffer der Ausgabe bilden. Szenarien 1,2 verwenden
5th+6th
; Szenario 3 verwendet'0'+3rd+6th
; Szenarien 4,5 verwenden'0'+1st+6th
; und Szenarien 6,7,8 verwenden'100'+6th
:Jetzt haben wir alle Nullen und Einsen auf dem Stapel, sodass wir sie in die drei ausgegebenen Ziffern konvertieren können:
quelle