Etwas heruntergekommen

43

Geben Sie bei einer Ganzzahl n > 0die Länge der längsten zusammenhängenden Folge von 0oder 1in ihrer Binärdarstellung aus.

Beispiele

  • 6ist 110binär geschrieben; Die längste Sequenz ist 11, also sollten wir zurückkehren2
  • 16100004
  • 89311011111015
  • 13373711010001101000000110116
  • 111
  • 99655461001100000001111111010107
Arnaud
quelle
8
OEIS A043276
Alephalpha
Können wir eine beliebige Grenze der Größe der Ganzzahl annehmen, z. B. 32 Bit oder 64 Bit?
Xnor
@ Xnor ja, Sie können davon ausgehen, dass die Int ist 32 Bit max
Arnaud

Antworten:

30

Python 2 , 46 45 Bytes

f=lambda n,k=1:`k`in bin(n^n/2)and-~f(n,k*10)

Probieren 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.

n    = 1337371 = 101000110100000011011₂
n/2  =  668685 =  10100011010000001101₂
m    = 1989654 = 111100101110000010110₂

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 andnicht ausgeführt und es wird False zurückgegeben .

Dazu berechnen wir zunächst bin(k)[3:]. In unserem Beispiel wird bin(k)zurückgegeben '0b111100101110000010110'und das 0b1am 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.

Dennis
quelle
2
Das ist wirklich schlau!
CraigR8806
1
Wow, das ist schlau. Daran hätte ich nie gedacht.
HyperNeutrino
Nizza Trick mit den Kräften von 10, aber werden sie nicht Longs mit einem L?
Xnor
@xnor Irgendwann, aber das ist nur eine Einschränkung des Datentyps. Darunter leiden auch die C-, JavaScript- und PHP-Antworten.
Dennis
Dies wäre bei der Verwendung in der Produktion ernsthaft unerreichbar. Kurz (ghehe) Golf erreicht, Loch in eins :)
JAK
17

Python 2, 46 Bytes

f=lambda n,r=1:max(r,n and f(n/2,1+~-n/2%2*r))

Probieren Sie es online aus

Extrahiert binäre Ziffern nin umgekehrter Reihenfolge, indem wiederholt n/2und verwendet werden n%2. Verfolgt die Länge des aktuellen Laufs rmit 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%2ist ein Indikator dafür, ob die letzten beiden Ziffern gleich sind, dh n0 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.

xnor
quelle
14

05AB1E , 6 Bytes

b.¡€gM

Probieren Sie es online!

Erläuterung

b       # convert to binary
 .¡     # split at difference
   €g   # map length on each
     M  # take max
Emigna
quelle
2
HA! Endlich! Eine Verwendung für , ich kann mich stoppen zwingen , um zu versuchen , es zu benutzen.
Magic Octopus Urn
@carusocomputing: Ich bin mir ziemlich sicher, dass ich es in ein paar Antworten verwendet habe.
Emigna
9

Mathematica, 38 Bytes

Max[Length/@Split[#~IntegerDigits~2]]&

oder

Max[Tr/@(1^Split[#~IntegerDigits~2])]&
Genisis
quelle
9

Python, 53 Bytes

import re;lambda g:max(map(len,re.findall('1+|0+',bin(g))))

Anonyme Lambda-Funktion.

R. Kap
quelle
9

Gelee , 6 Bytes

BŒgL€Ṁ

Probieren Sie es online!

Wie es funktioniert

BŒgL€Ṁ  Main link. Argument: n

B       Binary; convert n to base 2.
 Œg     Group adjacent, identical elements.
   L€   Map length over the groups.
     Ṁ  Take the maximum.
Dennis
quelle
9

Ruby, 41 bis 40 Bytes

->b{("%b%b"%[b,~b]).scan(/1+/).max.size}

Finde die längste Folge von '1' in b oder umgekehrt.

Dank an manatwork für das Speichern von 1 Byte.

GB
quelle
2
Bei anderen Versionen nicht sicher, aber in 2.3.1 ist der Abstand zwischen den nicht erforderlich %b.
Manatwork
Sie haben recht, negative Binärzahlen beginnen mit "..". Vielen Dank.
GB
7

JavaScript (ES6), 54 Byte

f=(n,r=0,l=1,d=2)=>n?f(n>>1,d^n&1?1:++r,r>l?r:l,n&1):l

Eine rekursive Lösung mit viel Bitmanipulation. nspeichert die Eingabe, rspeichert die Länge des aktuellen Laufs, lspeichert die Länge des längsten Laufs und dspeichert die vorherige Ziffer.

Testschnipsel

f=(n,r=0,l=1,d=2)=>n?f(n>>1,d^n&1?1:++r,r>l?r:l,n&1):l

for(var i of [0,1,2,3,4,5,6,7,8,9,16,893,1337371]) console.log(`f(${i}): ${f(i)}`)

ETHproductions
quelle
1
Dieselbe Idee, aber mit mehr Bit-Operationen und Ausnutzung der Standardkonvertierung von undefined in 0. Sie können sich f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m
Folgendes
7

Ruby, 51 44 43 Bytes

Funktion lösung.

@manatwork besteht aus Magie

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}
Wert Tinte
quelle
Prüft dies auf aufeinanderfolgende identische Ziffern oder nur aufeinanderfolgende 0s?
Genisis
2
Falsches Ergebnis für 893.
orlp
@orlp nicht mehr! : D
Value Ink
1
Ich würde die 1. und 2. Lösungen kombinieren: ->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}.
Manatwork
6

Python 2, 57 Bytes

a=lambda n:n and max((n&-n|~n&-~n).bit_length()-1,a(n/2))

Eine rekursive Lösung. Es könnte eine kürzere Form für das bisschen Magie geben.

orlp
quelle
6

Perl, 43 Bytes

#!perl -p
\@a[$a+=$_-1+($_>>=1)&1||-$a]while$_;$_=@a

Zählt man den Shebang als einen, wird die Eingabe von stdin übernommen.

Probieren Sie es online!

primo
quelle
Shebangs zählen als 0 Bytes.
CalculatorFeline
@CalculatorFeline Konsens über Meta ist, dass #!perlals Null zählt, nicht #!perl -p.
Primo
@CalculatorFeline: Die -pKosten 1, unter der Annahme, dass Ihre Perl-Befehlszeile ohnehin ein Argument hätte (z. B. -eoder -M5.010), sodass Sie pdirekt nach einem der Bindestriche einfügen können. Das #!perlist kostenlos (obwohl nicht notwendig).
Gut zu wissen. .
CalculatorFeline
5

Pip , 16 Bytes

Es scheint, als gäbe es einen kürzeren Weg, um die gleichen Zahlen zu erhalten ...

MX#*(TBa`1+|0+`)

Übernimmt die Eingabe als Befehlszeilenargument. Probieren Sie es online!

Erläuterung

     TBa          1st cmdline arg, To Binary
    (   `1+|0+`)  Find all matches of this regex
  #*              Map length operator to that list
MX                Get the maximum and autoprint it
DLosc
quelle
5

Perl 6 , 36 Bytes

{(.base(2)~~m:g/1+|0+/)».chars.max}

Erläuterung:

{                                 }   # a lambda
  .base(2)                            # convert the argument to base 2
          ~~m:g/     /                # regex match, with global matching turned on
                1+|0+                 # match one or more 1, or one or more 0
 (                    )».chars        # replace each match by its length
                              .max    # take the maximum number

Probieren Sie es online aus .

smls
quelle
4

Haskell, 79 Zeichen

maximum.map length.group.i

wo

import Data.List
i 0=[]
i n=mod n 2:i(div n 2)

Oder in ungolfed version:

import Data.List
pcg :: Int -> Int
pcg = maximum . map length . group . intToBin

intToBin :: Int -> [Int]
intToBin 0 = []
intToBin n = n `mod` 2 : intToBin (n `div` 2)

Erläuterung:

intToBinkonvertiert ein int in eine Liste von Binärziffern (lsb zuerst). groupgruppiert zusammenhängende Sequenzen, so dass [1, 1, 0, 0, 0, 1]wird [[1, 1],[0, 0, 0],[1]]. maximum . map lengthberechnet 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

user3389669
quelle
2
groupist nicht standardmäßig in Prelude, müssen Sie tun import Data.List, um es zu verwenden.
xnor
1
Beachten Sie, dass Sie Wachen anstelle von let: verwenden können i n|(q,r)<-n`quotRem`2=r:i q. Lesen Sie unsere Haskell Golf-Tipps . quotRemkann sein divMod. Ich denke, Sie können i 0=[]als Basisfall verwenden.
13.
1
Mit divund moddirekt ist noch kürzer: i n=mod n 2:i(div n 2).
Laikoni
3

Pyth, 7 Bytes

heSr8.B

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:

'  S     ' sorted(
'   r8   '   run_length_encode(
'     .BQ'     bin(input()) ))  \
'he      '   [-1][0]
busukxuan
quelle
3

J , 21 Bytes

[:>./#:#;.1~1,2~:/\#:

Probieren Sie es online!

Erläuterung

[:>./#:#;.1~1,2~:/\#:  Input: integer n
                   #:  Binary digits of n
              2   \    For each continuous subarray of 2 digits
               ~:/       Reduce it using not-equals
            1,         Prepend a 1 to those results
     #:                Binary digits of n
        ;.1~           Cut the binary digits at each location with a 1
       #                 Get the length of each cut
[:>./                  Reduce those lengths using maximum and return
Meilen
quelle
3

MATLAB 71 Bytes

m=1;a=diff(int8(dec2bin(a)));while(any(a==0)),m=m+1;a=diff(a);end;m

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?

zuerst
quelle
3
Willkommen bei PPCG! Standardmäßig werden nur Funktionen oder vollständige Programme (keine Codefragmente) akzeptiert. In Ihrem Fall , dass Mittel benötigen Sie zur Eingabe amit a=input('');. Auch ein paar Golftipps: ~astatt a==0. Brauchen Sie wirklich int8)?
Luis Mendo
3

Oktave , 31 Bytes

@(n)max(runlength(+dec2bin(n)))

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 eine runlengthFunktion hat (von der ich gerade erfahren habe). Standardmäßig wird nur das Array mit den Lauflängen ausgegeben, sodass das gewünschte Ergebnis das maxdes Arrays ist. Die Ausgabe von dec2bin, 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 +, da runlengthnumerische Eingaben erwartet werden.

Luis Mendo
quelle
3

Bash / Unix-Dienstprogramme, 66 65 42 Bytes

Vielen Dank an @DigitalTrauma für signifikante Verbesserungen (23 Bytes!).

dc<<<`dc -e2o?p|fold -1|uniq -c|sort -n`rp

Probieren Sie es online!

Mitchell Spector
quelle
1
@DigitalTrauma Danke für die Verbesserungen, insbesondere für das Einbinden von Fold, die in meinem üblichen Arsenal nicht vorhanden waren.
Mitchell Spector
3

Bash (+ coreutils, + GNU grep), 3332 Bytes

EDITS:

  • Minus 1 Byte (entfernte Anführungszeichen um Grep- Ausdruck)

Golf gespielt

dc -e2o$1p|grep -Po 1+\|0+|wc -L

Erklärt

 #Convert to binary
 >dc -e2o893p
 1101111101

 #Place each continuous run of 1es or 0es on its own line
 >dc -e2o893p|grep -Po '1+|0+'
 11
 0
 11111
 0
 1

 #Output the length of the longest line
 >dc -e2o893p|grep -Po '1+|0+'|wc -L
 5

Probieren Sie es online!

Zeppelin
quelle
AFAIK, grep Formen weder Teil bash noch coreutils wird jedoch beibehalten und durch seine verteilte eigene . Ich bin nicht sicher, was DC angeht, aber es war ein eigenständiges Tool in der GNU-Welt. Der einzige Bestandteil von coreutils ist wc.
Moreaki
@ Moreaki, grep ist POSIX, daher impliziert jede Shell-basierte Antwort, dass sie bereits verfügbar ist. dc ist kein POSIX, sondern ein Standardbestandteil fast aller * Nix-Systeme. Daher wird dc normalerweise auch nicht als separate Abhängigkeit erwähnt.
Zeppelin
Ich gehe davon aus, dass wir hier zwei unterschiedliche Gedankengänge verfolgen: Mein Punkt war nicht, ob grep POSIX war oder nicht, mein Punkt war, dass der Titel Ihrer Übermittlung an mich angab, dass man bash + coreutils benötigen würde, damit Ihre Lösung funktioniert, während das scheint nicht der Fall zu sein. Als ich es zuerst las, war diese Information für mich verwirrend. Wenn Sie Ihre Lösung auf einer mit macOS gelieferten Bash-Shell testen, funktioniert sie nicht. und es ist egal, ob Sie coreutils installiert haben oder nicht; Sie brauchen GNU grep, damit es funktioniert.
Moreaki
@ Moreaki, yep, ich impliziere nur das GNU-System, wenn ich + coreutils sage, obwohl das nicht immer der Fall ist. Ich habe den Titel genauer aktualisiert.
Zeppelin
2

Brachylog , 9 Bytes

$b@b:lotl

Probieren Sie es online!

Erläuterung

$b          List of binary digits of the input
  @b        Runs of consecutive identical digits in that list
    :lo     Order those runs by length
       tl   Output is the length of the last one
Tödlich
quelle
2

C # 106 Bytes

n=>{int l=1,o=0,p=0;foreach(var c in System.Convert.ToString(n,2)){o=c!=p?1:o+1;l=o>l?o:l;p=c;}return l;};

Formatierte Version:

System.Func<int, int> f = n =>
{
    int l = 1, o = 0, p = 0;
    foreach (var c in System.Convert.ToString(n, 2))
    {
        o = c != p ? 1 : o + 1;

        l = o > l ? o : l;

        p = c;
    }

    return l;
};

Und ein alternativer Ansatz für den Indexzugriff auf die Zeichenfolge mit 118 Byte ohne Leerzeichen:

System.Func<int, int> f2 = n =>
{
    var s = System.Convert.ToString(n, 2);

    int l = 1, c = 1, i = 0;

    for (; i < s.Length - 1; )
    {
        c = s[i] == s[++i] ? c + 1 : 1;
        l = l < c ? c : l;
    }

    return l;
};
TheLethalCoder
quelle
2

Javascript, 66 Bytes

x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.leng‌​th))

Danke an manatwork für den Code.

Erläuterung

x.toString(2)

Wandle die Zahl in einen Binärstring um.

split(/(0+|1+)/g)

Teile jedes Zeichen auf (0 oder 1) (dieser Regex fängt Leerzeichen ein, aber sie können ignoriert werden)

map(y=>y.length)

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)

Math.max()

Holen Sie sich die größte Anzahl aus den Argumenten.

Gemeinschaft
quelle
1
Gutsch Wert Ink ‚s Ruby - Lösung für die Inspiration, kann dies in umgewandelt werden 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)).
Handarbeit
3
Möglicherweise müssen Sie der Sortierfunktion ein Prädikat hinzufügen sort((a,b)=>b-a). Standardmäßig wird die Sortierfunktion 10zwischen 1und gesetzt 2.
Mama Fun Roll
Oder Sie könnten Math.max verwenden, wie von Hand vorgeschlagen.
Mama Fun Roll
Wtf, aber sie sind Zahlen. JS bitte.
2

Wunder , 27 Bytes

max.map#len.mstr`0+|1+`g.bn

Verwendungszweck:

(max.map#len.mstr`0+|1+`g.bn)123

Wandelt in Binär um, stimmt mit jeder Folge von Nullen und Einsen überein, ermittelt die Länge jeder Übereinstimmung und ermittelt das Maximum.

Mama Fun Roll
quelle
Wandelt dies die Eingabe in Binär um?
Laikoni
Oh, ich habe diesen Teil verpasst. Schnellkorrektur: P
Mama Fun Roll
2

Batch, 102 Bytes

@set/a"n=%1/2,d=%1%%2,r=1+(%3+0)*!(0%2^d),l=%4-(%4-r>>5)
@if not %n%==0 %0 %n% %d% %r% %l%
@echo %l%

Port von @ edc65's Antwort. %2.. %4ist beim ersten Aufruf leer, daher muss ich die Ausdrücke so schreiben, dass sie noch funktionieren. Der allgemeinste Fall ist %3der, als den ich schreiben musste (%3+0). %2ist einfacher, da es nur sein kann 0oder 1, die im oktal gleich sind, also 0%2hier funktioniert. %4stellte sich als noch einfacher heraus, da ich nur davon abziehen muss. (%4-r>>5)wird zum Vergleichen lmit verwendet, rda Batch's set/akeinen Vergleichsoperator hat.

Neil
quelle
2

Dyalog APL , 22 Bytes

Anonymer Funktionszug

⌈/∘(≢¨⊢⊂⍨1,2≠/⊢)2⊥⍣¯1

⌈/∘(... das Maximum der Ergebnisse des folgenden anonymen Funktionstrainings ...

≢¨  die Bilanz von jedem

⊢⊂⍨ Partition des Arguments, wobei die Partitionierung von denen in bestimmt wird

1, ein vorangestellt zu

2≠/ die paarweise ungleich

 das Argument

) angewendet

2⊥⍣¯1 from-base-2 wurde einmal negativ angewendet (dh einmal zur Base-2)

 das Argument

TryAPL online!

Adam
quelle
2

Japt, 15 Bytes

2o!q¢ c ml n gJ

Online testen! oder Überprüfen Sie alle Testfälle auf einmal .

Wie es funktioniert

                 // Implicit: U = input integer, J = -1
2o               // Create the range [0...2), or [0,1].
  ! ¢            // Map each item Z in this range to U.s(2)
   q             //                                        .q(Z).
                 // This returns the runs of 1's and 0's in the binary
                 // representation of U, respectively.
      c          // Flatten into a single list.
        ml       // Map each item Z to Z.length.
           n gJ  // Sort the result and grab the item at index -1, or the last item.
                 // This returns the largest element in the list.
                 // Implicit: output result of last expression
ETHproductions
quelle
2

R 45 34 Bytes

max(rle(miscFuncs::bin(scan()))$l)

Behebung eines albernen Missverständnisses dank @rturnbull und @plannapus.

Billywob
quelle
Vielleicht fehlt mir etwas, aber soll die Eingabe keine Binärzahl, sondern eine Ganzzahl sein? Und wir suchen den maximalen Lauf von 0oder von 1, nicht nur 0, richtig?
rturnbull
@plannapus Ich weiß es nicht ehrlich. Muss die Spezifikation komplett verpasst haben. Jetzt behoben.
Billywob
2

PowerShell , 78 74 73 Bytes

([regex]::Matches([convert]::ToString("$args",2),'0+|1+')|% Le*|sort)[-1]

Probieren 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 LengthEigenschaft (mit einem neuen gefundenen Muster, das einen wenig bekannten Parametersatz von verwendet ForEach-Object, um 1 Byte zu speichern) der resultierenden Übereinstimmungsobjekte verwendet. sortiert sie und gibt die letzte (die größte) aus.

Briantist
quelle
1

J, 27 Bytes

>./>#&.>((1,2~:/\[)<;.1])#:

Eine etwas andere (und leider längere) Herangehensweise an die Antwort von miles .

Verwendungszweck:

    >./>#&.>((1,2~:/\[)<;.1])#:893
5

Erläuterung

>./>#&.>((1,2~:/\[)<;.1])#:
                         #: Convert to base 2
        (               )   A fork
                       ]    Previous result
         (1,2~:/\[)         Find where each new sequence begins
                   <;.1     Cut the string of integers based on where each sequence begins and box them
    #&.>                    Count under open - open each box and count the items in it
>./>                        Open all the boxes and find the maximum value
Gareth
quelle
Ich glaube nicht, dass dies gültig ist - es ist keine Funktion und auch kein Ausschnitt.
Conor O'Brien
@ ConorO'Brien Okay, ich schaue es mir später nochmal an.
Gareth