Dies wurde inspiriert von Problem 13 - Non-Repeating Binary der letzten Konkurrenz von HP CodeWars.
Nehmen wir zum Beispiel eine zufällige Dezimalzahl
727429805944311
und schauen Sie sich seine binäre Darstellung an:
10100101011001011111110011001011101010110111110111
Teilen Sie nun diese Binärdarstellung in Teilfolgen auf, in denen sich die Ziffern 0
und 1
abwechseln.
1010 010101 10 0101 1 1 1 1 1 10 01 10 0101 1 1010101 101 1 1 1 101 1 1
Und konvertiere jede Teilsequenz zurück in eine Dezimalzahl.
10 21 2 5 1 1 1 1 1 2 1 2 5 1 85 5 1 1 1 5 1 1
Die Aufgabe
Nehmen Sie eine einzelne positive Ganzzahl als Eingabe und geben Sie die Folge positiver Ganzzahlen aus, die durch den obigen Prozess erhalten wurden.
Einzelheiten
- Eingabe und Ausgabe müssen dezimal oder unär sein.
- Zahlen in der Ausgabe müssen sinnvoll und für den Menschen lesbar getrennt und dezimal oder unär sein. Keine Einschränkung des Leerraums. Gültige Ausgabestile:
[1,2,3]
,1 2 3
,1\n2\n3
wo\n
sind wörtliche Zeilenumbrüche usw.
Testfälle
Input | Output
0 | 0
1 | 1
2 | 2
3 | 1 1
4 | 2 0
5 | 5
6 | 1 2
7 | 1 1 1
8 | 2 0 0
9 | 2 1
10 | 10
50 | 1 2 2
100 | 1 2 2 0
1000 | 1 1 1 1 10 0 0
10000 | 2 1 1 2 0 2 0 0 0
12914 | 1 2 2 1 1 2 2
371017 | 5 42 10 2 1
Zusätzlicher Hinweis: Alle Zahlen in der Ausgabe sollten die Form (2^k-1)/3
oder haben 2*(2^k-1)/3
. Das heißt, 0 1 2 5 10 21, 42, 85, 170, ...
das ist A000975 im OEIS.
code-golf
sequence
base-conversion
binary
subsequence
El'endia Starman
quelle
quelle
|tac
werde dann in meiner antwort bleiben :)Antworten:
Pyth,
1716 Bytes1 Byte danke an Jakube
Demonstration
Eine schöne, clevere Lösung. Verwendet einige weniger bekannte Funktionen von Pyth, wie
x<int><list>
undc<str><list>
.quelle
tJ
durch+dJ
können Sie entfernenhM
.Mathematica, 47 Bytes
Ungolfed:
Split[list,f]
Teilt eine Liste in mehrere Listen auf und bricht an der Position zwischena
undb
ifff[a,b]
kehrt nicht zurückTrue
.FromDigits[n,2] => Fold[#+##&,n]
ist ein guter Tipp von Alephalpha.quelle
Python, 86 Bytes
Da ich mich in Pyth fürchterlich geärgert habe, lass es uns einfach wieder in Python machen.
Probieren Sie es hier aus!
Erläuterung
Wir beginnen mit der Umwandlung der eingegebenen Zahl
n
in eine Binärzeichenfolge.bin(n)[2:]
kümmert sich darum. Wir müssen die ersten 2 Zeichen dieser Zeichenfolge verwerfen, dabin()
die Zeichenfolge im Format zurückgegeben wird0b10101
.Als nächstes müssen wir die Grenzen der Teilsequenzen identifizieren. Dies kann mit dem regulären Ausdruck erfolgen, der mit den
(?<=(.))(?=\1)
Positionen der Länge Null in der Zeichenfolge übereinstimmt, die links und rechts die gleiche Nummer haben.Die naheliegende Möglichkeit, eine Liste aller Teilsequenzen zu erhalten, besteht darin,
re.split()
eine Zeichenfolge in einem bestimmten regulären Ausdruck aufzuteilen. Leider funktioniert diese Funktion nicht für Übereinstimmungen mit der Länge Null. Glücklicherweisere.sub()
ersetzen wir diese Übereinstimmungen mit der Länge Null durch Leerzeichen und teilen die Zeichenfolge danach auf.Dann müssen wir nur noch jede dieser Teilsequenzen in eine Dezimalzahl umwandeln
int(s,2)
und fertig.quelle
Gelee, 12 Bytes
Probieren Sie es online! oder überprüfen Sie alle Testfälle .
Wie es funktioniert
quelle
Bash + GNU-Dienstprogramme, 51
Eingabe von STDIN.
dc -e2o?p
Liest eine Ganzzahl aus STDIN und gibt einen String zur Basis 2 aussed -r ':;s/(.)\1/\1 \1/;t'
Teilt die Zeichenfolge der Basis 2 mit einem Leerzeichen, wenn dieselben aufeinander folgenden Ziffern vorhanden sinddc -e2i?f
Liest die geteilte Binärdatei auf einmal, legt jeden Teil auf den Stapel und gibt dannf
den gesamtendc
Stapel aus (Ausgabenummern in umgekehrter Reihenfolge) ...tac
.quelle
JavaScript (ES6) 58
62 63Bearbeite 1 Byte gespeichert dank @ETHproductions
Bearbeite 4 Bytes gespeichert als @Neil
quelle
/(01)*0?|(10)*1?/g
, oder würde das etwas durcheinander bringen?x=>'0b'+x-0+' '
, um ein Byte zu speichern./((.)(?!\2))*./g
spart dir coole 4 Bytes.Pyth, 26 Bytes
Probieren Sie es hier aus!
Erläuterung
Da die split () - Funktion von Python bei Übereinstimmungen mit Länge Null nicht aufgeteilt wird, muss ich diese Übereinstimmungen durch ein Leerzeichen ersetzen und das Ergebnis darauf aufteilen.
quelle
Pyth,
2221 BytesProbieren Sie es online aus: Demonstration
Wirklich eine mühsame Aufgabe in Pyth.
Erläuterung:
quelle
05AB1E , 18 Bytes
Code:
Erläuterung:
Probieren Sie es online!
Verwendet CP-1252- Codierung.
quelle
MATL ,
1817 BytesProbieren Sie es online!
quelle
zsh,
676355 BytesIch weiß nicht warum, aber das funktioniert in Bash nicht.
Danke an Dennis für 8 Bytes!
quelle
for
Syntax. ... Warte, neinfor
s?for i in `grep -oP '1?(01)*0?'<<<$[[##2]$1]`;<<<$[2#$i]
.PHP,
Explosionszeichnung171168162160158121120131124118116113112 BytesVerwenden
d(int)
Sie und Sie sind ausgeschaltet, die Ausgabe ist eine durch ein Leerzeichen getrennteecho
Zeichenfolgeint
.Bearbeitungen:
-3:
$b
Definition instrlen()
Aufruf verschoben .-6: Entfernte
$c
Instanziierung.-2: Schließlich die Verkettung Problem behoben.
-2: Keine Klammern für einzeilige
for()
.-37: Generalüberholung.
Array
Ich gehe mit Chunklets anstatt wiederholterArray
->String
->Array
Anrufe.-1: Sneaky
$c
Reset.+11: Bugfix. Fehlte der letzte Teil. Nicht mehr.
-7: Müssen Sie überhaupt nicht instanziieren
$d
? Nett.-6:
return
->echo
.-2: Knirschen
$c
.-3:Ternary, meine erste Liebe.
-1: Hinterhältig hinterhältig
$u
.quelle
function d($i){for(;$d<$l=strlen($b=decbin($i));print$u==$b[++$d]||$d==$l?bindec($c).$c=" ":"")$c.=$u=$b[$d];}
.Konvex 0,2+, 25 Bytes
Convex ist eine neue Sprache, die ich entwickle und die stark auf CJam und Golfscript basiert. Den Interpreter und die IDE finden Sie hier . Die Eingabe ist eine Ganzzahl in die Befehlszeilenargumente. Dies verwendet die CP-1252- Codierung.
Erläuterung:
quelle
Java 8,
127119 BytesEs gibt wahrscheinlich einen besseren regulären Ausdruck, um die Zeichenfolge aufzuteilen. Ich beherrsche Regex nicht, aber ich werde weiter experimentieren.
-8 Bytes dank @FryAmTheEggman
quelle
APL (APL) ,
21-25BytesBehandelt jetzt auch 0.
Probieren Sie es online!
2⊥⍣¯1⊢
konvertiere nach Base-2, benutze so viele Bits wie nötig (lit. inverse from-Base-2-Konvertierung){
…}
Wenden folgende anonyme Funktion an0::
Wenn ein Fehler auftritt:0
0 zurückgeben⋄
jetzt versuchen:2=/⍵
paarweise Gleichheit des Arguments (wird eine 0 Länge-0 Binärdarstellung fehlschlagen)1,
voranstellen 1⍵⊂⍨
Verwenden Sie das, um das Argument zu partitionieren (beginnt neuen Abschnitt auf jeder 1)2⊥¨
konvertieren Sie jeweils von Basis-2quelle
⊂
ist hier wirklich nützlich. Ich sollte das zu Jelly hinzufügen.R←X⊂Y
: Mit⎕ML<3
(dh Dyalog-Stil) wird eine neue Partition im Ergebnis gestartet, die jeweils 1 in X bis zur Position vor der nächsten 1 in X (oder dem letzten Element von X) entspricht die aufeinanderfolgenden Elemente von R. Mit⎕ML=3
(dh IBM-Stil) wird eine neue Partition im Ergebnis gestartet, wenn das entsprechende Element in X größer als das vorherige ist. Elemente in Y, die 0en in X entsprechen, werden nicht in das Ergebnis einbezogen. Das⎕ML←1 ⋄ 1 0 0 1 0 1 1 ⊂ ⍳7
entspricht also⎕ML←3
⋄ 4 3 2 4 4 5 7 ⊂ ⊂7`Japt , 7 Bytes
Probier es aus
Erläuterung
quelle
Python 3, 115 Bytes
Erläuterung
Ergebnisse
vorherige Lösung (118 Bytes)
quelle
Haskell,
147, 145 Bytesmap(sum.zipWith((*).(2^))[0..]).([]%).b
ist eine unbenannte Funktion, die die Liste berechnet.Weniger golfen:
quelle
Perl, 53 Bytes
Beinhaltet +1 für
-p
Führen Sie mit der Nummer auf STDIN
alterbits.pl
:quelle
PowerShell, 103 Byte
Da ich bei Regex schrecklich bin, verwende ich den gleichen Ausdruck wie die Antwort von edc65 .
Absolut zerstört durch die langwierigen .NET-Aufrufe zum Konvertieren in / aus Binärdateien und den .NET-Aufruf zum Abrufen der Regex-Übereinstimmungen. Ansonsten ziemlich unkompliziert. Übernimmt die Eingabe
$args[0]
, stelltconvert
sie auf binär um, speist sie einMatches
, nimmt die resultierenden.Value
s auf, leitet sie durch eine Schleife|%{...}
und gibtconvert
diese Werte zurück anint
. Die Ausgabe bleibt in der Pipeline und wird implizit mit Zeilenumbrüchen gedruckt.Für zusätzliches Guthaben - eine (meist) nicht reguläre Version mit 126 Bytes
Wir nehmen wieder Eingang
$args[0]
undconvert
es binär. Wir wandeln es in ein Zeichen-Array um, in dem das erste Zeichen$l
und die restlichen Zeichen gespeichert werden$r
. Wir$r
durchlaufen dann eine Schleife,|%{...}
in der wir bei jeder Iteration entweder das Zeichen mit vorangestelltem Leerzeichen oder nur das Zeichen auswählen, je nach Ergebnis eines binären X oder mit$l
und dann$l
gleich dem Zeichen setzen. Dies stellt effektiv sicher, dass, wenn wir zweimal hintereinander dasselbe Zeichen haben, ein Leerzeichen dazwischen eingefügt wird.Die Ausgabe der Schleife wird
-join
zusammengefügt und an das erste Zeichen angehängt$l
, dann-split
an Leerzeichen (was technisch ein regulärer Ausdruck ist, aber ich werde es nicht zählen). Wir machen dann die gleiche Schleife wie die Regex-Antwortconvert
und geben ganze Zahlen aus.quelle
Java 345 Bytes
Prüfung
Ausgabe
quelle
package
und zu definierenclass
und unnötige Leerzeichen zu entfernen. Lassen Sie mich wissen, wenn Sie Fragen haben!Julia,
7057 BytesDies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und ein Ganzzahl-Array zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.
Der Ansatz hier ähnelt DenkerAffes netter Python- Antwort . Wir erhalten die binäre Darstellung von
n
usingbin(n)
und teilen den resultierenden String bei allen Übereinstimmungen des regulären Ausdrucks(?<=(.))(?=\1)
. Es ist eigentlich eine Übereinstimmung mit der Länge Null.(?<=(.))
ist ein positiver Lookbehind, der ein einzelnes Zeichen findet, und(?=\1)
ein positiver Lookahead, der das übereinstimmende Zeichen im Lookbehind findet. Dies lokalisiert die Stellen, an denen eine Zahl in der binären Darstellung von selbst gefolgt wird. Nurparse
jeweils als Ganzzahl in Basis 2 mitmap
und voila!quelle
C
137129 BytesEin- und Ausgabe erfolgen über die Standard-Streams.
quelle
puts
, obwohl es unangenehm wäre, es zu benutzen, erfordert die Spezifikation kein nachgestelltes Newline.J , 16 Bytes
Probieren Sie es online!
Erläuterung
quelle
q / kdb +, 52 Bytes
Lösung:
Beispiele:
Erläuterung:
q
wird von rechts nach links interpretiert.Eingaben in Binärdaten umwandeln, führende Nullen abschneiden, Indizes finden, bei denen sie unterschiedlich sind, invertieren, um Indizes zu erhalten, bei denen sie gleich sind, Liste auf diese Indizes aufteilen, zurück zur Basis 10 konvertieren. Sieht im Vergleich zur APL-Lösung allerdings etwas schwer aus ...
quelle
PHP, 147
Sie müssen bei der letzten Ausgabe zusätzlichen Speicherplatz angeben, da dies keine Einschränkung darstellt. Hinweise werden für die Kurzkodierung angezeigt.
Ungolfed-Version
quelle
Netzhaut, 60
Probieren Sie es online! Oder versuchen Sie es mit einer leicht geänderten Version für alle Testfälle (mit dezimaler E / A).
Leider scheinen Übereinstimmungen mit einer Länge von Null zwei "Seiten" zu haben, was zu Duplikaten führt, wenn sie mit dem regulären Ausdruck aus der dritten Stufe verwendet werden. Kostet allerdings nur ein Byte.
Nimmt Eingaben als unär, Ausgaben als unär. Ich bin mir nicht sicher, ob ich unterschiedliche unäre Ein- / Ausgabewerte verwenden soll, aber das spart 4 Bytes.
quelle
Gelee , 9 Bytes (nicht konkurrierend?)
Probieren Sie es online!
quelle