Bit run rundown

43

Diberikan bilangan bulat n > 0, menampilkan panjang urutan berdekatan terpanjang 0atau 1dalam representasi binernya.

Contohnya

  • 6ditulis 110dalam biner; urutan terpanjang adalah 11, jadi kita harus kembali2
  • 16100004
  • 89311011111015
  • 13373711010001101000000110116
  • 111
  • 99655461001100000001111111010107
Arnaud
sumber
8
OEIS A043276
alephalpha
Bisakah kita mengasumsikan batas ukuran integer seperti 32 bit atau 64 bit?
xnor
@ xnor ya Anda dapat menganggap int adalah 32 bit maks
Arnaud

Jawaban:

30

Python 2 , 46 45 byte

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

Cobalah online!

Bagaimana itu bekerja

Dengan XORing n dan n / 2 (membaginya dengan 2 pada dasarnya memotong bit terakhir), kita mendapatkan bilangan bulat baru m yang bit-bit yang tidak diset menunjukkan bit-bit yang berdekatan yang cocok dengan n .

Misalnya, jika n = 1337371 , kami memiliki yang berikut ini.

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

Ini mengurangi tugas untuk menemukan angka nol terpanjang. Karena representasi biner dari bilangan bulat positif selalu dimulai dengan angka 1 , kami akan mencoba mencari string angka 10 * terpanjang yang muncul dalam representasi biner dari m . Ini bisa dilakukan secara rekursif.

Inisialisasi k sebagai 1 . Setiap kali f dieksekusi, pertama-tama kita menguji apakah representasi desimal k muncul dalam representasi biner m . Jika ya, kita kalikan k dengan 10 dan panggil f lagi. Jika tidak, kode di sebelah kanan andtidak dijalankan dan kami mengembalikan False .

Untuk melakukan ini, pertama-tama kita menghitung bin(k)[3:]. Dalam contoh kami, bin(k)pengembalian '0b111100101110000010110', dan 0b1di awal dihapus dengan [3:].

Sekarang, -~sebelum kenaikan rekursif panggilan False / 0 satu kali untuk setiap kali f disebut rekursif. Setelah 10 {j} ( 1 diikuti oleh pengulangan j dari 0 ) tidak muncul dalam representasi biner k , jangka panjang nol yang terpanjang dalam k memiliki panjang j - 1 . Karena j - 1 nol berurutan dalam k menunjukkan j yang cocok dengan bit yang berdekatan dalam n , hasil yang diinginkan adalah j , yang adalah apa yang kita peroleh dengan menambahkan False / 0total j kali.

Dennis
sumber
2
Ini sangat pintar!
CraigR8806
1
Wow, itu pintar. Tidak pernah bisa memikirkannya.
HyperNeutrino
Trik yang bagus dengan kekuatan 10, tetapi tidakkah mereka menjadi rindu dengan huruf L?
xnor
@ xnor Akhirnya, tapi itu hanya batasan tipe data. Jawaban C, JavaScript, dan PHP juga menderita karenanya.
Dennis
Ini akan sangat sulit dipelihara jika digunakan dalam produksi. Singkatnya (ghehe) golf tercapai, hole in one :)
JAK
17

Python 2, 46 byte

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

Cobalah online

Ekstrak digit biner nsecara terbalik dengan mengambil n/2dan n%2. Lacak panjang jangka berjalan rdari digit yang sama dengan mengatur ulang ke 0 jika dua digit terakhir tidak sama, lalu tambahkan 1.

Ekspresi ~-n/2%2adalah indikator apakah dua digit terakhir sama, yaitu n0 atau 3 modulo 4. Memeriksa dua digit terakhir bersama-sama ternyata lebih pendek daripada mengingat digit sebelumnya.

Tidak
sumber
14

05AB1E , 6 byte

b.¡€gM

Cobalah online!

Penjelasan

b       # convert to binary
 .¡     # split at difference
   €g   # map length on each
     M  # take max
Emigna
sumber
2
HA! Akhirnya! Suatu penggunaan untuk , saya bisa berhenti memaksa diri untuk mencoba menggunakannya.
Magic Gurita Guci
@carusocomputing: Cukup yakin saya telah menggunakannya dalam beberapa jawaban.
Emigna
9

Mathematica, 38 byte

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

atau

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

Python, 53 byte

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

Fungsi lambda anonim.

R. Kap
sumber
9

Jelly , 6 byte

BŒgL€Ṁ

Cobalah online!

Bagaimana itu bekerja

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
sumber
9

Ruby, 41 40 byte

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

Temukan urutan terpanjang dari '1' di b atau kebalikannya.

Berkat manatwork karena telah menghemat 1 byte.

GB
sumber
2
Tidak yakin tentang versi lain, tetapi dalam 2.3.1 tidak perlu ada ruang di antara versi %b.
manatwork
Anda benar, angka biner negatif dimulai dengan "..". Terima kasih.
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

Solusi rekursif dengan banyak manipulasi bit. nmenyimpan input, rmenyimpan panjang lari saat ini, lmenyimpan panjang lari terpanjang, dan dmenyimpan digit sebelumnya.

Cuplikan tes

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

Produksi ETH
sumber
1
Gagasan yang sama, tetapi menggunakan lebih banyak operasi bit dan mengeksploitasi konversi default yang tidak terdefinisi menjadi 0. Jangan ragu untuk meminjam: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 byte

Solusi fungsi.

@manatwork terbuat dari sihir

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}
Nilai Tinta
sumber
Apakah ini memeriksa angka identik berturut-turut atau hanya 0s berturut-turut ?
ngenisis
2
Hasil salah untuk 893.
orlp
@ Atau tidak lagi! : D
Value Ink
1
Saya akan menggabungkan 1 dan solusi 2: ->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}.
manatwork
6

Python 2, 57 byte

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

Solusi rekursif. Mungkin ada bentuk yang lebih pendek untuk bit magic.

orlp
sumber
6

Perl, 43 byte

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

Menghitung shebang sebagai satu, input diambil dari stdin.

Cobalah online!

primo
sumber
Shebangs dihitung sebagai 0 byte.
CalculatorFeline
Konsensus @CalculatorFeline tentang meta adalah yang #!perldiperhitungkan sebagai nol, bukan #!perl -p.
Primo
@ CalculatorFeline: -pBiaya 1, dengan asumsi bahwa baris perintah Perl Anda tetap memiliki argumen (misalnya -eatau -M5.010), sehingga Anda dapat memasukkan sebuah phanya setelah salah satu tanda hubung. Ini #!perlgratis (walaupun tidak perlu).
Senang mendengarnya. .
CalculatorFeline
5

Pip , 16 byte

Sepertinya harus ada cara yang lebih singkat untuk mendapatkan angka yang sama ...

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

Mengambil input sebagai argumen baris perintah. Cobalah online!

Penjelasan

     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
sumber
5

Perl 6 , 36 byte

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

Penjelasan:

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

Cobalah online .

seseorang
sumber
4

Haskell, 79 karakter

maximum.map length.group.i

dimana

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

Atau dalam versi yang tidak dikoleksi:

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)

Penjelasan:

intToBinmengonversi int ke daftar digit biner (lsb dulu). groupkelompok urutan yang berdekatan, sehingga [1, 1, 0, 0, 0, 1]menjadi [[1, 1],[0, 0, 0],[1]]. maximum . map lengthmenghitung untuk setiap daftar bagian dalam panjangnya dan mengembalikan panjang yang terpanjang.

Sunting: Terima kasih kepada @xnor dan @Laikoni karena menyimpan byte

pengguna3389669
sumber
2
grouptidak ada di Prelude secara default, Anda harus lakukan import Data.Listuntuk menggunakannya
xnor
1
Perhatikan bahwa Anda dapat menggunakan penjaga di tempat let: i n|(q,r)<-n`quotRem`2=r:i q. Lihat tips golf Haskell kami . quotRembisa divMod. Saya pikir Anda dapat menggunakan i 0=[]sebagai alas kasus.
xnor
1
Menggunakan divdan modlangsung bahkan lebih pendek: i n=mod n 2:i(div n 2).
Laikoni
3

Pyth, 7 byte

heSr8.B

Lakukan pengkodean panjang run pada string biner, lalu urutkanlah sehingga run terpanjang datang terakhir, lalu ambil elemen pertama (panjang) dari elemen terakhir (run terpanjang) dari daftar.

Dalam pseudocode:

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

J , 21 byte

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

Cobalah online!

Penjelasan

[:>./#:#;.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
mil
sumber
3

MATLAB 71 byte

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

Ini mengkonversi variabel integer 'a' ke array binary int8 kemudian menghitung berapa kali hasilnya harus dibedakan sampai tidak ada nol dalam hasilnya.

Saya baru disini. Apakah input dan one-liner semacam ini diizinkan oleh aturan PCG?

pertama
sumber
3
Selamat datang di PPCG! Secara default, hanya fungsi atau program lengkap (bukan cuplikan kode) yang diterima. Dalam kasus Anda yang berarti Anda perlu untuk memasukkan adengan a=input('');. Juga, beberapa saran golf: ~abukannya a==0. Apakah Anda benar-benar membutuhkan int8)?
Luis Mendo
3

Oktaf , 31 byte

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

Cobalah online!

Penjelasan

Ini adalah terjemahan dari jawaban MATL saya. Rencana awal saya adalah pendekatan yang berbeda, yaitu @(n)max(diff(find(diff([0 +dec2bin(n) 0])))). Tetapi ternyata Oktaf memiliki runlengthfungsi (yang baru saya ketahui). Secara default itu hanya output array run-length, jadi hasil yang diinginkan adalah maxarray itu. Output dari dec2bin, yang merupakan array char (string) yang berisi '0'dan '1', perlu dikonversi ke array numerik menggunakan +, karena runlengthmengharapkan input numerik.

Luis Mendo
sumber
3

Utilitas Bash / Unix, 66 65 42 byte

Terima kasih kepada @DigitalTrauma untuk peningkatan signifikan (23 byte!).

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

Cobalah online!

Mitchell Spector
sumber
1
@DigitalTrauma Terima kasih atas perbaikannya, terutama untuk memasukkan lipatan, yang belum ada di gudang senjata biasa saya.
Mitchell Spector
3

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

EDIT:

  • Minus 1 byte (kutipan yang dihapus di sekitar ekspresi grep )

Golf

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

Dijelaskan

 #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

Cobalah secara Online!

zeppelin
sumber
AFAIK, grep bukan merupakan bagian dari bash atau coreutils, meskipun dikelola dan didistribusikan dengan sendirinya . Tidak yakin tentang dc, tetapi dulu alat mandiri di dunia GNU. Satu-satunya bagian pembentuk coreutils adalah wc.
Moreaki
@Moreaki, grep adalah POSIX, jadi setiap jawaban berbasis shell menyiratkan bahwa itu sudah tersedia. dc bukan POSIX tetapi merupakan bagian standar dari hampir setiap sistem * Nix di sekitarnya, jadi biasanya tidak disebutkan sebagai dependensi terpisah juga.
zeppelin
Saya rasa kita berada di dua kereta pikiran yang berbeda di sini: poin saya bukanlah apakah grep adalah POSIX atau tidak, poin saya adalah bahwa judul kiriman Anda kepada saya menunjukkan bahwa seseorang akan memerlukan bash + coreutils untuk membuat solusi Anda berfungsi, sementara ini sepertinya tidak terjadi. Ketika saya membacanya pertama kali, informasi ini membingungkan saya. Jika Anda mencoba solusi Anda pada bash shell yang dikirimkan macOS, itu tidak akan berfungsi; dan tidak masalah jika Anda menginstal coreutils atau tidak; Anda membutuhkan grep GNU untuk membuatnya berfungsi.
Moreaki
@Moreaki, ya, saya hanya menyiratkan sistem GNU, ketika saya mengatakan + coreutils, semuanya itu tidak selalu demikian. Saya telah memperbarui judulnya menjadi lebih tepat.
zeppelin
2

Brachylog , 9 byte

$b@b:lotl

Cobalah online!

Penjelasan

$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
Fatalisasi
sumber
2

C #, 106 byte

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

Versi yang diformat:

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

Dan pendekatan alternatif mengakses string dengan indeks pada 118 byte, dengan spasi dihapus:

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
sumber
2

Javascript, 66 Bytes

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

Berkat manatwork untuk kodenya.

Penjelasan

x.toString(2)

Konversi angka menjadi string biner.

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

Pisahkan setiap karakter yang berbeda (0 atau 1) (regex ini menangkap ruang kosong tetapi mereka dapat diabaikan)

map(y=>y.length)

Untuk setiap elemen array, dapatkan panjangnya dan masukkan ke dalam array yang dikembalikan.

...

Konversi array ke daftar argumen ([1,2,3] -> 1,2,3)

Math.max()

Dapatkan jumlah terbesar dari argumen.

Komunitas
sumber
1
Dengan mengkredit Nilai Ink 's Ruby solusi untuk inspirasi, ini bisa diubah menjadi x=>x.toString(2).split(/(0+|1+)/g).map(y=>y.length).sort().pop(). Atau sama panjang: x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.length)).
manatwork
3
Saya pikir Anda mungkin harus menambahkan predikat ke fungsi sortir sort((a,b)=>b-a). Secara default, fungsi sortir menempatkan 10di antara 1dan 2.
Mama Fun Roll
Atau Anda bisa menggunakan Math.max, seperti yang disarankan manatwork.
Mama Fun Roll
Wtf, tapi itu angka. Tolong, JS.
2

Bertanya-tanya , 27 byte

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

Pemakaian:

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

Konversi ke biner, mencocokkan setiap urutan 0 dan 1, mendapatkan panjang setiap pertandingan, dan mendapatkan maksimum.

Mama Fun Roll
sumber
Apakah ini mengubah input ke biner?
Laikoni
oooooh aku merindukan bagian itu. Perbaikan cepat: P
Mama Fun Roll
2

Batch, 102 byte

@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 jawaban @ edc65. %2.. %4akan kosong pada panggilan pertama, jadi saya harus menulis ekspresi sedemikian rupa sehingga mereka akan tetap berfungsi. Kasus yang paling umum adalah %3yang harus saya tulis (%3+0). %2lebih mudah, karena hanya bisa 0atau 1, yang sama dalam oktal, jadi 0%2bekerja di sini. %4ternyata menjadi lebih mudah, karena saya hanya perlu mengurangi itu. (%4-r>>5)digunakan untuk membandingkan ldengan rkarena Batch set/atidak memiliki operator pembanding.

Neil
sumber
2

Dyalog APL , 22 byte

Kereta fungsi anonim

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

⌈/∘(... Maksimum hasil dari kereta fungsi anonim berikut ...

≢¨  penghitungan masing-masing

⊢⊂⍨ partisi argumen, di mana partisi ditentukan oleh yang ada di

1, satu ditambahkan ke

2≠/ tidak sama berpasangan

 argumen

) diaplikasikan ke

2⊥⍣¯1 from-base-2 diterapkan negatif satu kali (yaitu ke-base-2, sekali) ke

 argumen

TryAPL online!

Adm
sumber
2

Japt, 15 byte

2o!q¢ c ml n gJ

Uji secara online! atau Verifikasi semua kasus uji sekaligus .

Bagaimana itu bekerja

                 // 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
Produksi ETH
sumber
2

R, 45 34 byte

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

Memperbaiki kesalahpahaman yang konyol berkat @rturnbull dan @plannapus.

Billywob
sumber
Mungkin saya melewatkan sesuatu, tetapi bukankah seharusnya input bilangan bulat, bukan bilangan biner? Dan kami sedang mencari jalan maksimum 0atau 1tidak 0, bukan?
rturnbull
@plannapus saya tidak tahu jujur. Pasti melewatkan spec sepenuhnya. Diperbaiki sekarang
Billywob
2

PowerShell , 78 74 73 byte

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

Cobalah online!

Ugh metode .Net itu.

Ini hanya menggunakan regex untuk menemukan (dan mencocokkan) urutan yang berdekatan dari satu dan nol, kemudian mengambil Lengthproperti (dengan pola baru yang saya temukan yang menggunakan set parameter yang sedikit diketahui ForEach-Object, untuk menyimpan 1 byte) dari objek pencocokan yang dihasilkan, mengurutkan mereka, dan menampilkan yang terakhir (yang terbesar).

briantis
sumber
1

J, 27 byte

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

Pendekatan yang sedikit berbeda (dan sayangnya lebih lama) untuk jawaban miles .

Pemakaian:

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

Penjelasan

>./>#&.>((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
sumber
Saya tidak berpikir ini valid - ini bukan fungsi dan juga potongan.
Conor O'Brien
@ ConorO'Brien Oke, saya akan melihatnya lagi nanti.
Gareth