Wybieg bitów

43

Biorąc pod uwagę liczbę całkowitą n > 0, wypisz długość najdłuższej ciągłej sekwencji 0lub 1jej reprezentacji binarnej.

Przykłady

  • 6jest zapisany 110binarnie; najdłuższa sekwencja jest 11, więc powinniśmy powrócić2
  • 16100004
  • 89311011111015
  • 13373711010001101000000110116
  • 111
  • 99655461001100000001111111010107
Arnaud
źródło
8
OEIS A043276
alephalpha
Czy możemy założyć dowolną granicę wielkości całkowitej, na przykład 32-bitową lub 64-bitową?
xnor
@ xnor tak, możesz założyć, że int to maksymalnie 32 bity
Arnaud

Odpowiedzi:

30

Python 2 , 46 45 bajtów

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

Wypróbuj online!

Jak to działa

Przez XORing n i n / 2 (dzielenie przez 2 zasadniczo odcina ostatni bit), otrzymujemy nową liczbę całkowitą m, której nieuzbrojone bity wskazują pasujące sąsiednie bity w n .

Na przykład, jeśli n = 1337371 , mamy następujące.

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

Zmniejsza to zadanie znalezienia najdłuższego ciągu zer. Ponieważ binarna reprezentacja dodatniej liczby całkowitej zawsze zaczyna się od 1 , spróbujemy znaleźć najdłuższy 10 * ciąg cyfr, który pojawia się w binarnej reprezentacji m . Można to zrobić rekurencyjnie.

Zainicjuj k jako 1 . Za każdym razem , gdy wykonuje się f , najpierw sprawdzamy, czy dziesiętna reprezentacja k pojawia się w binarnej reprezentacji m . Jeśli tak, mnożymy k przez 10 i ponownie wywołujemy f . Jeśli nie, kod po prawej stronie andnie jest wykonywany, a my zwracamy False .

Aby to zrobić, najpierw wykonujemy obliczenia bin(k)[3:]. W naszym przykładzie bin(k)zwraca '0b111100101110000010110', a 0b1na początku usuwa się za pomocą [3:].

Teraz -~przed wywołaniem rekurencyjnym inkrementuje wartość False / 0 za każdym razem, gdy f jest wywoływane rekurencyjnie. Gdy 10 {j} ( 1, po których następuje j powtórzeń 0 ) nie pojawia się w binarnej reprezentacji k , najdłuższy ciąg zer w k ma długość j - 1 . Ponieważ J - 1 kolejnymi zerami w k wskazuje J dopasowania sąsiednie bity n pożądany rezultat jest j , która jest co uzyskać zwiększając wartość fałsz / 0w sumie j razy.

Dennis
źródło
2
To jest naprawdę sprytne!
CraigR8806
1
Wow, to sprytne. Nigdy nie mogłem o tym myśleć.
HyperNeutrino,
Dobra sztuczka z mocami 10, ale czy nie stają się długimi z L?
xnor
@ xnor Ostatecznie, ale to tylko ograniczenie typu danych. Cierpią na tym również odpowiedzi C, JavaScript i PHP.
Dennis
Byłoby to poważnie niemożliwe do utrzymania, gdyby zastosowano je w produkcji. W skrócie (ghehe) golf osiągnięty, dołek w jednym :)
JAK
17

Python 2, 46 bajtów

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

Wypróbuj online

Wyodrębnia cyfry binarne z nodwrotnej kolejności przez wielokrotne pobieranie n/2i n%2. Śledzi długość bieżącego przebiegu rrównych cyfr, resetując go do 0, jeśli dwie ostatnie cyfry są nierówne, a następnie dodając 1.

Wyrażenie ~-n/2%2jest wskaźnikiem tego, czy dwie ostatnie cyfry są równe, tj. nWynosi 0 lub 3 modulo 4. Sprawdzanie razem dwóch ostatnich cyfr okazało się krótsze niż zapamiętanie poprzedniej cyfry.

xnor
źródło
14

05AB1E , 6 bajtów

b.¡€gM

Wypróbuj online!

Wyjaśnienie

b       # convert to binary
 .¡     # split at difference
   €g   # map length on each
     M  # take max
Emigna
źródło
2
HA! Wreszcie! Zastosowanie , mogę przestać zmuszać się do spróbowania z niego skorzystać.
Magic Octopus Urn
@carusocomputing: Jestem pewien, że użyłem go w kilku odpowiedziach.
Emigna
9

Mathematica, 38 bajtów

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

lub

Max[Tr/@(1^Split[#~IntegerDigits~2])]&
ngenisis
źródło
9

Python, 53 bajty

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

Anonimowa funkcja lambda.

R. Kap
źródło
9

Galaretka , 6 bajtów

BŒgL€Ṁ

Wypróbuj online!

Jak to działa

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
źródło
9

Rubin, 41 40 bajtów

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

Znajdź najdłuższą sekwencję „1” wb lub jej odwrotność.

Dziękujemy za zaoszczędzenie 1 bajtu.

GB
źródło
2
Nie jestem pewien co do innych wersji, ale w 2.3.1 nie ma potrzeby odstępów między nimi %b.
manatwork
Masz rację, ujemne liczby binarne zaczynają się od „..”. Dzięki.
GB
7

JavaScript (ES6), 54 bajty

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

Rozwiązanie rekurencyjne z wieloma manipulacjami bitowymi. nprzechowuje dane wejściowe, rprzechowuje długość bieżącego przebiegu, lprzechowuje długość najdłuższego przebiegu i dprzechowuje poprzednią cyfrę.

Testowy fragment kodu

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)}`)

ETHprodukcje
źródło
1
Ten sam pomysł, ale przy użyciu większej liczby operacji bitowych i wykorzystaniu domyślnej konwersji niezdefiniowanej na 0. Zapraszam do wypożyczenia:f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m
edc65
7

Ruby, 51 44 43 bajtów

Rozwiązanie funkcji.

@manatwork jest zrobiony z magii

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}
Wartość tuszu
źródło
Czy to sprawdza kolejne identyczne cyfry lub tylko kolejne 0s?
ngenisis
2
Niepoprawny wynik dla 893.
lub
@orlp już nie! : D
Wartość tuszu
1
Chciałbym połączyć 1 i 2 rozwiązania: ->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}.
manatwork
6

Python 2, 57 bajtów

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

Rozwiązanie rekurencyjne. Może istnieć krótsza forma magii bitów.

orlp
źródło
6

Perl, 43 bajty

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

Licząc shebang jako jeden, dane wejściowe są pobierane ze standardowego wejścia.

Wypróbuj online!

primo
źródło
Shebangs liczą się jako 0 bajtów.
CalculatorFeline
@CalculatorFeline konsensus w sprawie meta jest taki, że #!perlliczy się jako zero, a nie #!perl -p.
primo
@CalculatorFeline: -pKoszt 1, przy założeniu, że twoja linia poleceń Perla i tak miałaby argument (np. -eLub -M5.010), więc możesz wstawić znak pzaraz po jednym z łączników. #!perlJest wolny (chociaż zbędne).
Dobrze wiedzieć. .
CalculatorFeline
5

Pip , 16 bajtów

Wydaje się, że musi istnieć krótszy sposób, aby uzyskać ciągi tej samej cyfry ...

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

Pobiera dane wejściowe jako argument wiersza polecenia. Wypróbuj online!

Wyjaśnienie

     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
źródło
5

Perl 6 , 36 bajtów

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

Wyjaśnienie:

{                                 }   # 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

Wypróbuj online .

smls
źródło
4

Haskell, 79 znaków

maximum.map length.group.i

gdzie

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

Lub w wersji bez golfa:

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)

Wyjaśnienie:

intToBinkonwertuje liczbę int na listę cyfr binarnych (najpierw lsb). groupgrupuje ciągłe sekwencje, takie, które [1, 1, 0, 0, 0, 1]stają się [[1, 1],[0, 0, 0],[1]]. maximum . map lengthoblicza dla każdej wewnętrznej listy jego długość i zwraca długość najdłuższej.

Edycja: Dzięki @xnor i @Laikoni za oszczędzanie bajtów

użytkownik3389669
źródło
2
groupdomyślnie nie jest w Preludium, musisz go import Data.Listużyć.
xnor
1
Pamiętaj, że możesz używać strażników zamiast let: i n|(q,r)<-n`quotRem`2=r:i q. Zobacz nasze wskazówki dotyczące golfa Haskell . quotRemmoże być divMod. Myślę, że możesz użyć i 0=[]jako podstawy.
xnor
1
Używanie divi modbezpośrednio jest jeszcze krótszy: i n=mod n 2:i(div n 2).
Laikoni
3

Pyth, 7 bajtów

heSr8.B

Wykonaj kodowanie długości przebiegu w ciągu binarnym, a następnie posortuj je tak, aby najdłuższe przebiegi były ostatnie, a następnie weź pierwszy element (długość) ostatniego elementu (najdłuższy przebieg) z listy.

W pseudokodzie:

'  S     ' sorted(
'   r8   '   run_length_encode(
'     .BQ'     bin(input()) ))  \
'he      '   [-1][0]
busukxuan
źródło
3

J , 21 bajtów

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

Wypróbuj online!

Wyjaśnienie

[:>./#:#;.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
mile
źródło
3

MATLAB 71 bajtów

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

Konwertuje zmienną całkowitą „a” na binarną tablicę int8, a następnie zlicza liczbę różnic, w których wynik musi być różnicowany, dopóki w wyniku nie będzie zero.

Jestem tu nowy. Czy tego rodzaju dane wejściowe i jednoliniowe są dozwolone przez reguły PCG?

pierwszy
źródło
3
Witamy w PPCG! Domyślnie akceptowane są tylko funkcje lub pełne programy (nie fragmenty kodu). W twoim przypadku, że środki potrzebne do wejścia az a=input('');. Również kilka porad golfowych: ~azamiast a==0. Czy naprawdę potrzebujesz int8)?
Luis Mendo,
3

Oktawa , 31 bajtów

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

Wypróbuj online!

Wyjaśnienie

To jest tłumaczenie mojej odpowiedzi MATL. Mój pierwotny plan był inny, a mianowicie @(n)max(diff(find(diff([0 +dec2bin(n) 0])))). Ale okazuje się, że Octave ma runlengthfunkcję (o której właśnie się dowiedziałem). Domyślnie wyświetla tylko tablicę długości przebiegu, więc pożądanym wynikiem jest maxtablica. Dane wyjściowe dec2bin, który jest tablicą znaków (ciąg) zawierającą '0'i '1', należy przekonwertować na tablicę numeryczną +, ponieważ runlengthoczekuje danych liczbowych.

Luis Mendo
źródło
3

Narzędzia Bash / Unix, 66 65 42 bajtów

Dzięki @DigitalTrauma za znaczące ulepszenia (23 bajty!).

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

Wypróbuj online!

Mitchell Spector
źródło
1
@DigitalTrauma Dziękuję za ulepszenia, szczególnie za włączenie fold, którego nie było w moim zwykłym arsenale.
Mitchell Spector,
3

Bash (+ coreutils, + GNU grep), 33, 32 bajty

EDYCJE:

  • Minus 1 bajt (usunięte cudzysłowy wokół wyrażenia grep )

Grał w golfa

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

Wyjaśniono

 #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

Wypróbuj online!

zepelin
źródło
AFAIK, grep nie stanowi części bash ani coreutils, choć jest utrzymywany i dystrybuowany samodzielnie . Nie jestem pewien co do dc, ale było to samodzielne narzędzie w świecie GNU. Jedyną częścią Coreutils jest wc.
Moreaki,
@ Moreaki, grep jest POSIX, więc każda odpowiedź oparta na powłoce sugeruje, że jest już dostępna. dc nie jest POSIX-em, ale jest standardową częścią prawie każdego systemu * Nix, więc nie jest zwykle wymieniany jako osobna zależność.
zeppelin
Wydaje mi się, że jesteśmy tutaj w dwóch różnych ciągach myśli: nie chodziło mi o to, czy grep to POSIX, czy nie. Chodziło mi o to, że tytuł przesłania do mnie wskazywał, że potrzebny będzie bash + coreutils, aby twoje rozwiązanie działało, podczas gdy wydaje się, że tak nie jest. Kiedy przeczytałem ją po raz pierwszy, ta informacja była dla mnie myląca. Jeśli wypróbujesz swoje rozwiązanie w powłoce bash dostarczanej w systemie macOS, nie zadziała; i nie ma znaczenia, czy zainstalowałeś coreutils, czy nie; potrzebujesz GNU grep, aby działał.
Moreaki,
@Moreaki, tak, po prostu sugeruję system GNU, kiedy mówię + coreutils, choć nie zawsze tak jest. Zaktualizowałem tytuł, aby był bardziej precyzyjny.
zeppelin
2

Brachylog , 9 bajtów

$b@b:lotl

Wypróbuj online!

Wyjaśnienie

$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
Fatalizować
źródło
2

C #, 106 bajtów

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;};

Wersja sformatowana:

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;
};

I alternatywne podejście do dostępu do ciągu według indeksu na 118 bajtów, z usuniętymi białymi znakami:

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
źródło
2

JavaScript, 66 bajtów

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

Dzięki manatwork dla kodu.

Wyjaśnienie

x.toString(2)

Konwertuj liczbę na ciąg binarny.

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

Podziel każdą inną postać (0 lub 1) (to wyrażenie regularne przechwytuje puste miejsca, ale można je zignorować)

map(y=>y.length)

Dla każdego elementu tablicy uzyskaj jego długość i umieść go w zwróconej tablicy.

...

Konwertuj tablicę na listę argumentów ([1,2,3] -> 1,2,3)

Math.max()

Uzyskaj największą liczbę argumentów.

Społeczność
źródło
1
Poprzez uznanie Value Ink „s rozwiązanie Ruby do inspiracji, to może być przekształcona x=>x.toString(2).split(/(0+|1+)/g).map(y=>y.length).sort().pop(). Lub taką samą długość: x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.length)).
manatwork
3
Myślę, że może być konieczne dodanie predykatu do funkcji sortowania sort((a,b)=>b-a). Domyślnie funkcja sortowania umieszcza 10pomiędzy 1i 2.
Mama Fun Roll
Lub możesz użyć Math.max, jak sugeruje manatwork.
Mama Fun Roll
Wtf, ale to liczby. JS proszę.
2

Cud , 27 bajtów

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

Stosowanie:

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

Konwertuje na binarne, dopasowuje każdą sekwencję zer i jedynek, pobiera długość każdego dopasowania i dostaje maksimum.

Mama Fun Roll
źródło
Czy to przekształca dane wejściowe na binarne?
Laikoni
oooooh tęskniłem za tą częścią. Szybka poprawka: P
Mama Fun Roll
2

Partia, 102 bajty

@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 odpowiedzi @ edc65. %2.. %4będzie puste przy pierwszym wywołaniu, więc muszę napisać wyrażenia w taki sposób, aby nadal działały. Najbardziej ogólny przypadek, %3który musiałem napisać jako (%3+0). %2jest łatwiejsze, ponieważ może być 0lub 1, które są takie same w liczbie ósemkowej, więc 0%2działa tutaj. %4okazało się jeszcze łatwiejsze, bo muszę tylko odjąć od tego. (%4-r>>5)służy do porównania lz rjak Batch użytkownika set/anie posiada operator porównania.

Neil
źródło
2

Dyalog APL , 22 bajty

Anonimowy ciąg funkcji

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

⌈/∘(... Maksymalna liczba wyników następujących anonimowych ciągów funkcji ...

≢¨  podsumowanie każdego

⊢⊂⍨ partycja argumentu, gdzie partycjonowanie jest określone przez te w

1, jeden wcześniej

2≠/ para nierówna

 argument

) stosowane do

2⊥⍣¯1 z bazy-2 zastosował jeden raz ujemny (tj. do bazy-2, raz) do

 argument

Wypróbuj APL online!

Adám
źródło
2

Japt, 15 bajtów

2o!q¢ c ml n gJ

Przetestuj online! lub Zweryfikuj wszystkie przypadki testowe jednocześnie .

Jak to działa

                 // 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
ETHprodukcje
źródło
2

R, 45 34 bajtów

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

Naprawiono głupie nieporozumienie dzięki @rturnbull i @plannapus.

Billywob
źródło
Być może coś mi brakuje, ale czy dane wejściowe nie powinny być liczbami całkowitymi, a nie liczbami binarnymi? I szukamy maksymalnego nakładu 0lub 1nie 0, prawda?
rturnbull
@plannapus Nie wiem szczerze. Musiał całkowicie pominąć specyfikację. Naprawiono teraz.
Billywob
2

PowerShell , 78 74 73 bajty

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

Wypróbuj online!

Ugh, te metody .Net.

To po prostu używa wyrażenia regularnego, aby znaleźć (i dopasować) ciągłe ciągi zer i jedynek, a następnie bierze Lengthwłaściwość (z nowym wzorcem, który znalazłem, który używa mało znanego zestawu parametrów ForEach-Object, aby zapisać 1 bajt) wynikowych obiektów dopasowania, sortuje je i wysyła ostatni (największy).

briantist
źródło
1

J, 27 bajtów

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

Nieco inne (i niestety dłuższe) podejście do odpowiedzi mil .

Stosowanie:

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

Wyjaśnienie

>./>#&.>((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
źródło
Nie sądzę, że jest to poprawne - to nie jest funkcja, podobnie jak fragment kodu.
Conor O'Brien
@ ConorO'Brien Dobra, przyjrzę się temu później.
Gareth,