Biorąc pod uwagę liczbę całkowitą n > 0
, wypisz długość najdłuższej ciągłej sekwencji 0
lub 1
jej reprezentacji binarnej.
Przykłady
6
jest zapisany110
binarnie; najdłuższa sekwencja jest11
, więc powinniśmy powrócić2
16
→10000
→4
893
→1101111101
→5
1337371
→101000110100000011011
→6
1
→1
→1
9965546
→100110000000111111101010
→7
code-golf
sequence
binary
subsequence
Arnaud
źródło
źródło
Odpowiedzi:
Python 2 ,
4645 bajtówWypró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.
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
and
nie jest wykonywany, a my zwracamy False .Aby to zrobić, najpierw wykonujemy obliczenia
bin(k)[3:]
. W naszym przykładziebin(k)
zwraca'0b111100101110000010110'
, a0b1
na 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.źródło
Python 2, 46 bajtów
Wypróbuj online
Wyodrębnia cyfry binarne z
n
odwrotnej kolejności przez wielokrotne pobieranien/2
in%2
. Śledzi długość bieżącego przebiegur
ró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%2
jest wskaźnikiem tego, czy dwie ostatnie cyfry są równe, tj.n
Wynosi 0 lub 3 modulo 4. Sprawdzanie razem dwóch ostatnich cyfr okazało się krótsze niż zapamiętanie poprzedniej cyfry.źródło
05AB1E , 6 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
.¡
, mogę przestać zmuszać się do spróbowania z niego skorzystać.Mathematica, 38 bajtów
lub
źródło
Python, 53 bajty
Anonimowa funkcja lambda.
źródło
Galaretka , 6 bajtów
Wypróbuj online!
Jak to działa
źródło
Rubin,
4140 bajtówZnajdź najdłuższą sekwencję „1” wb lub jej odwrotność.
Dziękujemy za zaoszczędzenie 1 bajtu.
źródło
%b
.JavaScript (ES6), 54 bajty
Rozwiązanie rekurencyjne z wieloma manipulacjami bitowymi.
n
przechowuje dane wejściowe,r
przechowuje długość bieżącego przebiegu,l
przechowuje długość najdłuższego przebiegu id
przechowuje poprzednią cyfrę.Testowy fragment kodu
źródło
f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m
Ruby,
514443 bajtówRozwiązanie funkcji.
@manatwork jest zrobiony z magii
źródło
0
s?->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}
.Python 2, 57 bajtów
Rozwiązanie rekurencyjne. Może istnieć krótsza forma magii bitów.
źródło
Perl, 43 bajty
Licząc shebang jako jeden, dane wejściowe są pobierane ze standardowego wejścia.
Wypróbuj online!
źródło
#!perl
liczy się jako zero, a nie#!perl -p
.-p
Koszt 1, przy założeniu, że twoja linia poleceń Perla i tak miałaby argument (np.-e
Lub-M5.010
), więc możesz wstawić znakp
zaraz po jednym z łączników.#!perl
Jest wolny (chociaż zbędne).Pip , 16 bajtów
Wydaje się, że musi istnieć krótszy sposób, aby uzyskać ciągi tej samej cyfry ...
Pobiera dane wejściowe jako argument wiersza polecenia. Wypróbuj online!
Wyjaśnienie
źródło
Perl 6 , 36 bajtów
Wyjaśnienie:
Wypróbuj online .
źródło
Haskell, 79 znaków
gdzie
Lub w wersji bez golfa:
Wyjaśnienie:
intToBin
konwertuje liczbę int na listę cyfr binarnych (najpierw lsb).group
grupuje ciągłe sekwencje, takie, które[1, 1, 0, 0, 0, 1]
stają się[[1, 1],[0, 0, 0],[1]]
.maximum . map length
oblicza 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
źródło
group
domyślnie nie jest w Preludium, musisz goimport Data.List
użyć.let
:i n|(q,r)<-n`quotRem`2=r:i q
. Zobacz nasze wskazówki dotyczące golfa Haskell .quotRem
może byćdivMod
. Myślę, że możesz użyći 0=[]
jako podstawy.div
imod
bezpośrednio jest jeszcze krótszy:i n=mod n 2:i(div n 2)
.Pyth, 7 bajtów
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:
źródło
J , 21 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
MATLAB 71 bajtów
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?
źródło
a
za=input('');
. Również kilka porad golfowych:~a
zamiasta==0
. Czy naprawdę potrzebujeszint8
)?Oktawa , 31 bajtów
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 marunlength
funkcję (o której właśnie się dowiedziałem). Domyślnie wyświetla tylko tablicę długości przebiegu, więc pożądanym wynikiem jestmax
tablica. Dane wyjściowedec2bin
, który jest tablicą znaków (ciąg) zawierającą'0'
i'1'
, należy przekonwertować na tablicę numeryczną+
, ponieważrunlength
oczekuje danych liczbowych.źródło
Narzędzia Bash / Unix,
666542 bajtówDzięki @DigitalTrauma za znaczące ulepszenia (23 bajty!).
Wypróbuj online!
źródło
Bash (+ coreutils, + GNU grep),
33, 32 bajtyEDYCJE:
Grał w golfa
Wyjaśniono
Wypróbuj online!
źródło
Brachylog , 9 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
C #, 106 bajtów
Wersja sformatowana:
I alternatywne podejście do dostępu do ciągu według indeksu na 118 bajtów, z usuniętymi białymi znakami:
źródło
JavaScript, 66 bajtów
Dzięki manatwork dla kodu.
Wyjaśnienie
Konwertuj liczbę na ciąg binarny.
Podziel każdą inną postać (0 lub 1) (to wyrażenie regularne przechwytuje puste miejsca, ale można je zignorować)
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)
Uzyskaj największą liczbę argumentów.
źródło
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))
.sort((a,b)=>b-a)
. Domyślnie funkcja sortowania umieszcza10
pomiędzy1
i2
.Cud , 27 bajtów
Stosowanie:
Konwertuje na binarne, dopasowuje każdą sekwencję zer i jedynek, pobiera długość każdego dopasowania i dostaje maksimum.
źródło
Partia, 102 bajty
Port odpowiedzi @ edc65.
%2
..%4
bę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,%3
który musiałem napisać jako(%3+0)
.%2
jest łatwiejsze, ponieważ może być0
lub1
, które są takie same w liczbie ósemkowej, więc0%2
działa tutaj.%4
okazało się jeszcze łatwiejsze, bo muszę tylko odjąć od tego.(%4-r>>5)
służy do porównanial
zr
jak Batch użytkownikaset/a
nie posiada operator porównania.źródło
Dyalog APL , 22 bajty
Anonimowy ciąg funkcji
⌈/∘(
... Maksymalna liczba wyników następujących anonimowych ciągów funkcji ...≢¨
podsumowanie każdego⊢⊂⍨
partycja argumentu, gdzie partycjonowanie jest określone przez te w1,
jeden wcześniej2≠/
para nierówna⊢
argument)
stosowane do2⊥⍣¯1
z bazy-2 zastosował jeden raz ujemny (tj. do bazy-2, raz) do⊢
argumentWypróbuj APL online!
źródło
Japt, 15 bajtów
Przetestuj online! lub Zweryfikuj wszystkie przypadki testowe jednocześnie .
Jak to działa
źródło
R,
4534 bajtówNaprawiono głupie nieporozumienie dzięki @rturnbull i @plannapus.
źródło
0
lub1
nie0
, prawda?PowerShell ,
787473 bajtyWypró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
Length
właściwość (z nowym wzorcem, który znalazłem, który używa mało znanego zestawu parametrówForEach-Object
, aby zapisać 1 bajt) wynikowych obiektów dopasowania, sortuje je i wysyła ostatni (największy).źródło
J, 27 bajtów
Nieco inne (i niestety dłuższe) podejście do odpowiedzi mil .
Stosowanie:
Wyjaśnienie
źródło