Geben Sie bei einer Ganzzahl n > 0
die Länge der längsten zusammenhängenden Folge von 0
oder 1
in ihrer Binärdarstellung aus.
Beispiele
6
ist110
binär geschrieben; Die längste Sequenz ist11
, also sollten wir zurückkehren2
16
→10000
→4
893
→1101111101
→5
1337371
→101000110100000011011
→6
1
→1
→1
9965546
→100110000000111111101010
→7
code-golf
sequence
binary
subsequence
Arnaud
quelle
quelle
Antworten:
Python 2 ,
4645 BytesProbieren Sie es online!
Wie es funktioniert
Durch XOR-Verknüpfung von n und n / 2 (Division durch 2 schneidet im wesentlichen das letzte Bit ab) erhalten wir eine neue Ganzzahl m, deren nicht gesetzte Bits übereinstimmende benachbarte Bits in n anzeigen .
Wenn beispielsweise n = 1337371 ist , haben wir Folgendes.
Dies reduziert die Aufgabe, den längsten Lauf von Nullen zu finden. Da die Binärdarstellung einer positiven Ganzzahl immer mit einer 1 beginnt , versuchen wir, die längste 10 * -Ziffernfolge zu finden, die in der Binärdarstellung von m vorkommt . Dies kann rekursiv erfolgen.
Initialisiere k als 1 . Jedes Mal , wenn f ausgeführt wird, prüfen wir zuerst, ob die Dezimaldarstellung von k in der Binärdarstellung von m erscheint . In diesem Fall multiplizieren wir k mit 10 und rufen f erneut auf. Wenn dies nicht der Fall ist, wird der Code rechts von
and
nicht ausgeführt und es wird False zurückgegeben .Dazu berechnen wir zunächst
bin(k)[3:]
. In unserem Beispiel wirdbin(k)
zurückgegeben'0b111100101110000010110'
und das0b1
am Anfang mit entfernt[3:]
.Nun wird der
-~
Wert vor dem rekursiven Aufruf jedes Mal, wenn f rekursiv aufgerufen wird, einmal auf False / 0 erhöht . Sobald 10 {j} ( 1 gefolgt von j Wiederholungen von 0 ) nicht in der binären Darstellung von k erscheint , hat der längste Lauf von Nullen in k die Länge j - 1 . Da j - 1 aufeinanderfolgende Nullen in k j übereinstimmende benachbarte Bits in n anzeigen , ist das gewünschte Ergebnis j , was wir durch Inkrementieren von False / 0 erhalteninsgesamt j mal.quelle
Python 2, 46 Bytes
Probieren Sie es online aus
Extrahiert binäre Ziffern
n
in umgekehrter Reihenfolge, indem wiederholtn/2
und verwendet werdenn%2
. Verfolgt die Länge des aktuellen Laufsr
mit gleichen Ziffern, indem es auf 0 zurückgesetzt wird, wenn die letzten beiden Ziffern ungleich sind, und dann 1 hinzugefügt wird.Der Ausdruck
~-n/2%2
ist ein Indikator dafür, ob die letzten beiden Ziffern gleich sind, dhn
0 oder 3 Modulo 4. Das Überprüfen der letzten beiden Ziffern zusammen hat sich als kürzer herausgestellt als das Erinnern an die vorherige Ziffer.quelle
05AB1E , 6 Bytes
Probieren Sie es online!
Erläuterung
quelle
.¡
, ich kann mich stoppen zwingen , um zu versuchen , es zu benutzen.Mathematica, 38 Bytes
oder
quelle
Python, 53 Bytes
Anonyme Lambda-Funktion.
quelle
Gelee , 6 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Ruby,
41 bis40 BytesFinde die längste Folge von '1' in b oder umgekehrt.
Dank an manatwork für das Speichern von 1 Byte.
quelle
%b
.JavaScript (ES6), 54 Byte
Eine rekursive Lösung mit viel Bitmanipulation.
n
speichert die Eingabe,r
speichert die Länge des aktuellen Laufs,l
speichert die Länge des längsten Laufs undd
speichert die vorherige Ziffer.Testschnipsel
quelle
f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m
Ruby,
514443 BytesFunktion lösung.
@manatwork besteht aus Magie
quelle
0
s?->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}
.Python 2, 57 Bytes
Eine rekursive Lösung. Es könnte eine kürzere Form für das bisschen Magie geben.
quelle
Perl, 43 Bytes
Zählt man den Shebang als einen, wird die Eingabe von stdin übernommen.
Probieren Sie es online!
quelle
#!perl
als Null zählt, nicht#!perl -p
.-p
Kosten 1, unter der Annahme, dass Ihre Perl-Befehlszeile ohnehin ein Argument hätte (z. B.-e
oder-M5.010
), sodass Siep
direkt nach einem der Bindestriche einfügen können. Das#!perl
ist kostenlos (obwohl nicht notwendig).Pip , 16 Bytes
Es scheint, als gäbe es einen kürzeren Weg, um die gleichen Zahlen zu erhalten ...
Übernimmt die Eingabe als Befehlszeilenargument. Probieren Sie es online!
Erläuterung
quelle
Perl 6 , 36 Bytes
Erläuterung:
Probieren Sie es online aus .
quelle
Haskell, 79 Zeichen
wo
Oder in ungolfed version:
Erläuterung:
intToBin
konvertiert ein int in eine Liste von Binärziffern (lsb zuerst).group
gruppiert zusammenhängende Sequenzen, so dass[1, 1, 0, 0, 0, 1]
wird[[1, 1],[0, 0, 0],[1]]
.maximum . map length
berechnet für jede innere Liste ihre Länge und gibt die Länge der längsten zurück.Edit: Danke an @xnor und @Laikoni für das Speichern von Bytes
quelle
group
ist nicht standardmäßig in Prelude, müssen Sie tunimport Data.List
, um es zu verwenden.let
: verwenden könneni n|(q,r)<-n`quotRem`2=r:i q
. Lesen Sie unsere Haskell Golf-Tipps .quotRem
kann seindivMod
. Ich denke, Sie könneni 0=[]
als Basisfall verwenden.div
undmod
direkt ist noch kürzer:i n=mod n 2:i(div n 2)
.Pyth, 7 Bytes
Führen Sie eine Lauflängencodierung für die Binärzeichenfolge durch, sortieren Sie sie dann so, dass die längsten Läufe als letzte angezeigt werden, und nehmen Sie dann das erste Element (die Länge) des letzten Elements (den längsten Lauf) der Liste.
Im Pseudocode:
quelle
J , 21 Bytes
Probieren Sie es online!
Erläuterung
quelle
MATLAB 71 Bytes
Dies konvertiert die Ganzzahlvariable 'a' in ein binäres int8-Array und zählt dann, wie oft das Ergebnis differenziert werden muss, bis das Ergebnis keine Null mehr enthält.
Ich bin neu hier. Ist diese Art von Eingabe und Einzeiler gemäß den PCG-Regeln zulässig?
quelle
a
mita=input('');
. Auch ein paar Golftipps:~a
statta==0
. Brauchen Sie wirklichint8
)?Oktave , 31 Bytes
Probieren Sie es online!
Erläuterung
Dies ist eine Übersetzung meiner MATL-Antwort. Mein ursprünglicher Plan war ein anderer Ansatz, nämlich
@(n)max(diff(find(diff([0 +dec2bin(n) 0]))))
. Aber es stellt sich heraus, dass Octave einerunlength
Funktion hat (von der ich gerade erfahren habe). Standardmäßig wird nur das Array mit den Lauflängen ausgegeben, sodass das gewünschte Ergebnis dasmax
des Arrays ist. Die Ausgabe vondec2bin
, bei der es sich um ein Zeichen-Array (String) handelt, das'0'
und enthält'1'
, muss mithilfe von in ein numerisches Array konvertiert werden+
, darunlength
numerische Eingaben erwartet werden.quelle
Bash / Unix-Dienstprogramme,
666542 BytesVielen Dank an @DigitalTrauma für signifikante Verbesserungen (23 Bytes!).
Probieren Sie es online!
quelle
Bash (+ coreutils, + GNU grep),
3332 BytesEDITS:
Golf gespielt
Erklärt
Probieren Sie es online!
quelle
Brachylog , 9 Bytes
Probieren Sie es online!
Erläuterung
quelle
C # 106 Bytes
Formatierte Version:
Und ein alternativer Ansatz für den Indexzugriff auf die Zeichenfolge mit 118 Byte ohne Leerzeichen:
quelle
Javascript, 66 Bytes
Danke an manatwork für den Code.
Erläuterung
Wandle die Zahl in einen Binärstring um.
Teile jedes Zeichen auf (0 oder 1) (dieser Regex fängt Leerzeichen ein, aber sie können ignoriert werden)
Für jedes Element des Arrays wird dessen Länge ermittelt und in das zurückgegebene Array eingefügt.
Array in Liste der Argumente konvertieren ([1,2,3] -> 1,2,3)
Holen Sie sich die größte Anzahl aus den Argumenten.
quelle
x=>x.toString(2).split(/(0+|1+)/g).map(y=>y.length).sort().pop()
. Oder die gleiche Länge:x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.length))
.sort((a,b)=>b-a)
. Standardmäßig wird die Sortierfunktion10
zwischen1
und gesetzt2
.Wunder , 27 Bytes
Verwendungszweck:
Wandelt in Binär um, stimmt mit jeder Folge von Nullen und Einsen überein, ermittelt die Länge jeder Übereinstimmung und ermittelt das Maximum.
quelle
Batch, 102 Bytes
Port von @ edc65's Antwort.
%2
..%4
ist beim ersten Aufruf leer, daher muss ich die Ausdrücke so schreiben, dass sie noch funktionieren. Der allgemeinste Fall ist%3
der, als den ich schreiben musste(%3+0)
.%2
ist einfacher, da es nur sein kann0
oder1
, die im oktal gleich sind, also0%2
hier funktioniert.%4
stellte sich als noch einfacher heraus, da ich nur davon abziehen muss.(%4-r>>5)
wird zum Vergleichenl
mit verwendet,r
da Batch'sset/a
keinen Vergleichsoperator hat.quelle
Dyalog APL , 22 Bytes
Anonymer Funktionszug
⌈/∘(
... das Maximum der Ergebnisse des folgenden anonymen Funktionstrainings ...≢¨
die Bilanz von jedem⊢⊂⍨
Partition des Arguments, wobei die Partitionierung von denen in bestimmt wird1,
ein vorangestellt zu2≠/
die paarweise ungleich⊢
das Argument)
angewendet2⊥⍣¯1
from-base-2 wurde einmal negativ angewendet (dh einmal zur Base-2)⊢
das ArgumentTryAPL online!
quelle
Japt, 15 Bytes
Online testen! oder Überprüfen Sie alle Testfälle auf einmal .
Wie es funktioniert
quelle
R
4534 BytesBehebung eines albernen Missverständnisses dank @rturnbull und @plannapus.
quelle
0
oder von1
, nicht nur0
, richtig?PowerShell ,
787473 BytesProbieren Sie es online!
Ugh diese .Net Methoden.
Dies verwendet lediglich einen regulären Ausdruck, um zusammenhängende Folgen von Einsen und Nullen zu finden (und abzugleichen). Anschließend wird die
Length
Eigenschaft (mit einem neuen gefundenen Muster, das einen wenig bekannten Parametersatz von verwendetForEach-Object
, um 1 Byte zu speichern) der resultierenden Übereinstimmungsobjekte verwendet. sortiert sie und gibt die letzte (die größte) aus.quelle
J, 27 Bytes
Eine etwas andere (und leider längere) Herangehensweise an die Antwort von miles .
Verwendungszweck:
Erläuterung
quelle