Бит беги краткое изложение

43

Учитывая целое число n > 0, выведите длину самой длинной непрерывной последовательности 0или 1в ее двоичном представлении.

Примеры

  • 6записано 110в двоичном виде; самая длинная последовательность 11, поэтому мы должны вернуть2
  • 16100004
  • 89311011111015
  • 13373711010001101000000110116
  • 111
  • 99655461001100000001111111010107
Arnaud
источник
8
OEIS A043276
алефальфа
Можем ли мы принять какую-либо границу размера целого числа, например 32-битную или 64-битную?
xnor
@xnor да, вы можете предположить, что int - это максимум 32 бита
Арно

Ответы:

30

Python 2 , 46 45 байт

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

Попробуйте онлайн!

Как это работает

Используя XOR n и n / 2 (деление на 2, по существу, обрезает последний бит), мы получаем новое целое число m, чьи неустановленные биты указывают на совпадение соседних битов в n .

Например, если n = 1337371 , мы имеем следующее.

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

Это уменьшает задачу, чтобы найти самый длинный пробег нулей. Поскольку двоичное представление положительного целого числа всегда начинается с 1 , мы попытаемся найти самую длинную 10 * строку цифр, которая появляется в двоичном представлении m . Это можно сделать рекурсивно.

Инициализируйте k как 1 . Каждый раз, когда выполняется f , мы сначала проверяем, появляется ли десятичное представление k в двоичном представлении m . Если это так, мы умножаем k на 10 и снова вызываем f . Если это не так, код справа от andне выполняется, и мы возвращаем False .

Для этого мы сначала вычислим bin(k)[3:]. В нашем примере bin(k)возвращает '0b111100101110000010110', и 0b1в начале удаляется с [3:].

Теперь -~рекурсивный вызов before увеличивает значение False / 0 один раз для каждого вызова f рекурсивно. Если 10 {j} ( 1 за которым следуют j повторений по 0 ) не появятся в двоичном представлении k , самый длинный ряд нулей в k будет иметь длину j - 1 . Поскольку j - 1 последовательных нулей в k указывают j, совпадающих с соседними битами в n , желаемый результат равен j , что мы и получаем, увеличивая значение False / 0в общей сложности J раз.

Деннис
источник
2
Это действительно умно!
CraigR8806
1
Вау, это умно. Никогда бы не подумал об этом.
HyperNeutrino
Хороший трюк со степенью 10, но разве они не становятся длинными с L?
xnor
@xnor В конце концов, но это только ограничение типа данных. Ответы C, JavaScript и PHP также страдают от этого.
Деннис
Это было бы серьезно недопустимо, если бы оно использовалось в производстве. Короче говоря (ghehe) гольф достигнут, дыра в одном :)
JAK
17

Python 2, 46 байт

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

Попробуйте онлайн

Извлекает двоичные цифры из nобратного путем многократного взятия n/2и n%2. Отслеживает длину текущего цикла rравных цифр, сбрасывая ее на 0, если последние две цифры не равны, а затем добавляя 1.

Выражение ~-n/2%2является индикатором того, равны ли последние две цифры, то nесть 0 или 3 по модулю 4. Проверка двух последних цифр вместе оказалась более короткой, чем запоминание предыдущей цифры.

XNOR
источник
14

05AB1E , 6 байтов

b.¡€gM

Попробуйте онлайн!

объяснение

b       # convert to binary
 .¡     # split at difference
   €g   # map length on each
     M  # take max
Emigna
источник
2
ХА! В заключение! Использование для , я могу перестать заставлять себя пытаться использовать его.
Волшебная Урна Осьминога
@carusocomputing: Я уверен, что использовал это в нескольких ответах.
Эминья
9

Mathematica, 38 байт

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

или

Max[Tr/@(1^Split[#~IntegerDigits~2])]&
ngenisis
источник
9

Python, 53 байта

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

Анонимная лямбда-функция.

Р. Кап
источник
9

Желе , 6 байт

BŒgL€Ṁ

Попробуйте онлайн!

Как это работает

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.
Деннис
источник
9

Рубин, 41 40 байт

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

Найдите самую длинную последовательность «1» в b или ее обратную.

Спасибо manatwork за сохранение 1 байта.

гигабайт
источник
2
Не уверен насчет других версий, но в 2.3.1 нет необходимости для пробела между %bсимволами.
manatwork
Вы правы, отрицательные двоичные числа начинаются с "..". Спасибо.
GB
7

JavaScript (ES6), 54 байта

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

Рекурсивное решение с большим количеством битовых манипуляций. nсохраняет входные данные, rсохраняет длину текущего цикла, lсохраняет длину самого длинного цикла и dсохраняет предыдущую цифру.

Тестовый фрагмент

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
источник
1
Та же идея, но с использованием большего количества битовых операций и использованием преобразования по умолчанию undefined в 0. Не стесняйтесь брать:f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m
edc65
7

Рубин, 51 44 43 байта

Функциональное решение.

@manatwork сделан из магии

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}
Значение чернил
источник
Проверяет ли это последовательные идентичные цифры или только последовательные 0?
ngenisis
2
Неверный результат для 893.
orlp
@ или больше нет! : D
Value Ink
1
Я бы совместить 1 - й и 2 - го решения: ->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}.
manatwork
6

Python 2, 57 байт

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

Рекурсивное решение. Там может быть более короткая форма для немного магии.

orlp
источник
6

Perl, 43 байта

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

Считая Шебанг как единое, ввод берется из стандартного ввода.

Попробуйте онлайн!

Примо
источник
Шебанги считаются 0 байтами.
CalculatorFeline
@CalculatorFeline консенсус в отношении мета , что #!perlсчитается нулем, а не #!perl -p.
прима
@CalculatorFeline: -pстоит 1, исходя из предположения, что ваша командная строка Perl в любом случае будет иметь аргумент (например, -eили -M5.010), поэтому вы можете вставить pсразу после одного из дефисов. Это #!perlбесплатно (хотя и не нужно).
Хорошо знать. ,
CalculatorFeline
5

Пип , 16 байт

Кажется, должен быть более короткий способ получить пробеги той же самой цифры ...

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

Принимает ввод в качестве аргумента командной строки. Попробуйте онлайн!

объяснение

     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
источник
5

Perl 6 , 36 байт

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

Объяснение:

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

Попробуйте онлайн .

SMLS
источник
4

Хаскель, 79 персонажей

maximum.map length.group.i

где

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

Или в разряженной версии:

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)

Объяснение:

intToBinпреобразует int в список двоичных цифр (сначала lsb). groupгруппирует смежные последовательности, такие, что [1, 1, 0, 0, 0, 1]становится [[1, 1],[0, 0, 0],[1]]. maximum . map lengthвычисляет для каждого внутреннего списка его длину и возвращает длину самого длинного.

Изменить: Спасибо @xnor и @Laikoni за сохранение байтов

user3389669
источник
2
groupпо умолчанию не включен в Prelude, вам нужно сделать это, import Data.Listчтобы использовать его.
xnor
1
Обратите внимание , что вы можете использовать охранник на месте let: i n|(q,r)<-n`quotRem`2=r:i q. Посмотрите наши советы по игре в гольф на Haskell . quotRemможет быть divMod. Я думаю, что вы можете использовать i 0=[]в качестве базового варианта.
xnor
1
Использование divи modнапрямую еще короче i n=mod n 2:i(div n 2).
Лайкони
3

Pyth, 7 байт

heSr8.B

Выполните кодирование длины серии в двоичной строке, затем отсортируйте ее так, чтобы самые длинные серии были последними, а затем возьмите первый элемент (длину) последнего элемента (самый длинный цикл) списка.

В псевдокоде:

'  S     ' sorted(
'   r8   '   run_length_encode(
'     .BQ'     bin(input()) ))  \
'he      '   [-1][0]
busukxuan
источник
3

J , 21 байт

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

Попробуйте онлайн!

объяснение

[:>./#:#;.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
миль
источник
3

MATLAB 71 байт

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

Это преобразует целочисленную переменную 'a' в двоичный массив int8, а затем подсчитывает, сколько раз результат должен быть дифференцирован, пока в результате не будет нулевого значения.

Я здесь новичок. Разрешен ли такой ввод и однострочный текст правилами PCG?

первый
источник
3
Добро пожаловать в PPCG! По умолчанию принимаются только функции или полные программы (не фрагменты кода). В вашем случае это означает, что вам нужно ввести aс a=input('');. Также несколько советов по гольфу: ~aвместо a==0. Вы действительно нуждаетесь int8)?
Луис Мендо
3

Октава , 31 байт

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

Попробуйте онлайн!

объяснение

Это перевод моего ответа MATL. Мой первоначальный план был другой подход, а именно @(n)max(diff(find(diff([0 +dec2bin(n) 0])))). Но оказывается, что у Octave есть runlengthфункция (о которой я только что узнал). По умолчанию он выводит только массив длин серий, поэтому желаемым результатом будет maxэтот массив. Выходные данные dec2bin, представляющие собой массив символов (строку), содержащий '0'и '1', должны быть преобразованы в числовой массив с использованием +, поскольку runlengthожидается числовой ввод.

Луис Мендо
источник
3

Утилиты Bash / Unix, 66 65 42 байта

Спасибо @DigitalTrauma за значительные улучшения (23 байта!).

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

Попробуйте онлайн!

Митчелл Спектор
источник
1
@DigitalTrauma Спасибо за улучшения, особенно за включение фолда, которого не было в моем обычном арсенале.
Митчелл Спектор
3

Bash (+ coreutils, + GNU grep), 3332 байта

правок:

  • Минус 1 байт (удалены кавычки вокруг выражения grep )

Golfed

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

Разъяснения

 #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

Попробуйте онлайн!

дирижабль
источник
На самом деле, grep не входит ни в bash, ни в coreutils, хотя поддерживается и распространяется самостоятельно . Не уверен насчет DC, но раньше он был автономным инструментом в мире GNU. Единственная составляющая часть coreutils - это туалет.
Мореаки
@Moreaki, grep - это POSIX, поэтому любой ответ на основе оболочки подразумевает, что он уже доступен. dc - это не POSIX, а стандартная часть почти каждой системы * Nix, поэтому он также обычно не упоминается как отдельная зависимость.
Цеппелин
Я считаю, что мы находимся здесь в двух разных направлениях: моя точка зрения была не о том, был ли grep POSIX или нет, я хотел сказать, что в названии вашей статьи указано, что для работы вашего решения потребуется bash + coreutils, в то время как это кажется не так. Когда я прочитал это впервые, эта информация меня смутила. Если вы попробуете ваше решение на bash-оболочке, поставляемой с macOS, оно не будет работать; и это не имеет значения, если вы установили coreutils или нет; вам понадобится GNU grep, чтобы он заработал.
Мореаки
@Moreaki, да, я просто подразумеваю систему GNU, когда говорю «coreutils», хотя это не всегда так. Я обновил название, чтобы быть более точным.
Zeppelin
2

C #, 106 байт

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

Отформатированная версия:

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

И альтернативный подход к доступу к строке по индексу в 118 байтов с удалением пробелов:

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
источник
2

Javascript, 66 байт

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

Спасибо manatwork за код.

объяснение

x.toString(2)

Преобразовать число в двоичную строку.

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

Разделить каждый символ (0 или 1) (это регулярное выражение захватывает пустые места, но их можно игнорировать)

map(y=>y.length)

Для каждого элемента массива получите его длину и поместите его в возвращаемый массив.

...

Преобразовать массив в список аргументов ([1,2,3] -> 1,2,3)

Math.max()

Получить наибольшее число из аргументов.

Сообщество
источник
1
По кредитованию Значения Ink «ы решения Ruby , за вдохновение, это может быть преобразовано в x=>x.toString(2).split(/(0+|1+)/g).map(y=>y.length).sort().pop(). Или же длина: x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.length)).
manatwork
3
Я думаю, что вам, возможно, придется добавить предикат в функцию сортировки sort((a,b)=>b-a). По умолчанию функция сортировки находится 10между 1и 2.
Mama Fun Roll
Или вы можете использовать Math.max, как предполагает manatwork.
Mama Fun Roll
Wtf, но они числа. JS пожалуйста.
2

Чудо , 27 байт

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

Использование:

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

Преобразует в двоичный файл, сопоставляет каждую последовательность из 0 и 1, получает длину каждого совпадения и получает максимум.

Mama Fun Roll
источник
Преобразует ли это ввод в двоичный файл?
Лайкони
ооооо, я пропустил эту часть. Быстрое исправление: P
Mama Fun Roll
2

Пакетная, 102 байта

@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%

Порт ответа @ edc65. %2.. %4будет пустым при первом вызове, поэтому я должен написать выражения таким образом, чтобы они все еще работали. Наиболее общий случай, %3который я должен был написать как (%3+0). %2проще, так как это может быть только 0или 1, которые одинаковы в восьмеричном, поэтому 0%2работает здесь. %4Оказалось даже проще, так как от меня нужно только вычесть. (%4-r>>5)используются для сравнения lс , rкак Batch - й set/aне имеют оператора сравнения.

Нил
источник
2

Дьялог АПЛ , 22 байта

Поезд анонимной функции

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

⌈/∘(... Максимум результатов следующей анонимной функции-поезда ...

≢¨  подсчет каждого

⊢⊂⍨ разделение аргумента, где разделение определяется теми, в

1, один, предшествующий

2≠/ попарно неравный

 Аргумент

) применительно к

2⊥⍣¯1 От-базы-2 применяется отрицательный один раз (то есть от-базы-2, один раз)

 Аргумент

Попробуй APL онлайн!

Адам
источник
2

Japt, 15 байт

2o!q¢ c ml n gJ

Проверьте это онлайн! или Проверьте все тестовые случаи одновременно .

Как это работает

                 // 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
источник
2

R, 45 34 байта

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

Исправлено глупое недоразумение благодаря @rturnbull и @plannapus.

Billywob
источник
Возможно, я что-то упустил, но не должен ли ввод быть целым числом, а не двоичным числом? И мы ищем максимальный пробег 0или 1, а не только 0, верно?
rturnbull
@plannapus Я не знаю, честно. Должно быть, пропустил спецификацию полностью. Исправлено сейчас.
Billywob
2

PowerShell , 78 74 73 байта

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

Попробуйте онлайн!

Тьфу те методы .Net.

Он просто использует регулярное выражение для поиска (и сопоставления) смежных последовательностей единиц и нулей, а затем принимает Lengthсвойство (с новым обнаруженным мной шаблоном, который использует малоизвестный набор параметров ForEach-Object, чтобы сохранить 1 байт) результирующих объектов сопоставления, сортирует их и выводит последний (самый большой).

briantist
источник
1

J, 27 байт

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

Немного другой (и, к сожалению, более длинный) подход к ответу миль .

Использование:

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

объяснение

>./>#&.>((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
источник
Я не думаю, что это действительно - это не функция, а фрагмент кода.
Конор О'Брайен
@ ConorO'Brien Хорошо, я посмотрю на это позже.
Гарет