Dado um número inteiro n > 0
, imprima o comprimento da maior sequência contígua de 0
ou 1
em sua representação binária.
Exemplos
6
é escrito110
em binário; a sequência mais longa é11
, então devemos retornar2
16
→10000
→4
893
→1101111101
→5
1337371
→101000110100000011011
→6
1
→1
→1
9965546
→100110000000111111101010
→7
code-golf
sequence
binary
subsequence
Arnaud
fonte
fonte
Respostas:
Python 2 ,
4645 bytesExperimente online!
Como funciona
Ao XORing n e n / 2 (a divisão por 2 corta essencialmente o último bit), obtemos um novo número inteiro m cujos bits não definidos indicam os bits adjacentes correspondentes em n .
Por exemplo, se n = 1337371 , temos o seguinte.
Isso reduz a tarefa de encontrar a execução mais longa de zeros. Como a representação binária de um número inteiro positivo sempre começa com 1 , tentaremos encontrar a seqüência de caracteres 10 * mais longa que aparece na representação binária de m . Isso pode ser feito recursivamente.
Inicialize k como 1 . Toda vez que f é executado, primeiro testamos se a representação decimal de k aparece na representação binária de m . Nesse caso, multiplicamos k por 10 e chamamos f novamente. Caso contrário, o código à direita de
and
não é executado e retornamos False .Para fazer isso, primeiro calculamos
bin(k)[3:]
. Em nosso exemplo,bin(k)
retorna'0b111100101110000010110'
, e o0b1
no início é removido com[3:]
.Agora, a
-~
chamada anterior recursiva aumenta Falso / 0 uma vez para cada vez que f é chamado recursivamente. Uma vez que 10 {j} ( 1 seguido de j repetições de 0 ) não aparece na representação binária de k , o maior número de zeros em k tem comprimento j - 1 . Como j - 1 zeros consecutivos em k indicam j bits adjacentes correspondentes em n , o resultado desejado é j , que é o que obtemos incrementando False / 0um total de j vezes.fonte
Python 2, 46 bytes
Experimente online
Extrai dígitos binários de
n
modo inverso, usandon/2
e repetidamenten%2
. Rastreia o comprimento da execução atualr
de dígitos iguais, redefinindo-o para 0 se os dois últimos dígitos forem desiguais e adicionando 1.A expressão
~-n/2%2
é um indicador de se os dois últimos dígitos são iguais, ou seja,n
é 0 ou 3 do módulo 4. Verificar os dois últimos dígitos juntos diminuiu mais do que lembrar o dígito anterior.fonte
05AB1E , 6 bytes
Experimente online!
Explicação
fonte
.¡
, posso parar de me forçar a tentar usá-lo.Mathematica, 38 bytes
ou
fonte
Python, 53 bytes
Função lambda anônima.
fonte
Gelatina , 6 bytes
Experimente online!
Como funciona
fonte
Ruby,
4140 bytesEncontre a sequência mais longa de '1' em b ou em sua inversa.
Agradecimentos ao manatwork por economizar 1 byte.
fonte
%b
.JavaScript (ES6), 54 bytes
Uma solução recursiva com muita manipulação de bits.
n
armazena a entrada,r
armazena a duração da execução atual,l
armazena a duração da execução mais longa ed
armazena o dígito anterior.Snippet de teste
fonte
f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m
Ruby,
514443 bytesSolução de função.
@manatwork é feito de mágica
fonte
0
s consecutivos ?->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}
.Python 2, 57 bytes
Uma solução recursiva. Pode haver uma forma mais curta para a mágica do bit.
fonte
Perl, 43 bytes
Contando o shebang como um, a entrada é obtida de stdin.
Experimente online!
fonte
#!perl
conta como zero, não#!perl -p
.-p
custo é 1, supondo que sua linha de comando Perl tenha um argumento de qualquer maneira (por exemplo,-e
ou-M5.010
), para que você possa entrarp
logo após um dos hífens. O#!perl
é gratuito (embora desnecessário).Pip , 16 bytes
Parece que deve haver uma maneira mais curta de obter as execuções do mesmo dígito ...
Recebe entrada como argumento da linha de comando. Experimente online!
Explicação
fonte
Perl 6 , 36 bytes
Explicação:
Experimente online .
fonte
Haskell, 79 caracteres
Onde
Ou na versão ungolfed:
Explicação:
intToBin
converte um int em uma lista de dígitos binários (lsb primeiro).group
agrupa sequências contíguas, de modo que[1, 1, 0, 0, 0, 1]
se tornem[[1, 1],[0, 0, 0],[1]]
.maximum . map length
calcula para cada lista interna seu comprimento e retorna o comprimento do maior.Edit: Obrigado a @xnor e @Laikoni por salvar bytes
fonte
group
não está no Prelude por padrão, você precisaimport Data.List
usá-lo.let
:i n|(q,r)<-n`quotRem`2=r:i q
. Veja nossas dicas de golfe em Haskell .quotRem
pode serdivMod
. Eu acho que você pode usari 0=[]
como o caso base.div
emod
diretamente é ainda menor:i n=mod n 2:i(div n 2)
.Pitão, 7 bytes
Execute a codificação de comprimento na cadeia binária e, em seguida, classifique-a para que as execuções mais longas cheguem por último e, em seguida, pegue o primeiro elemento (o comprimento) do último elemento (a execução mais longa) da lista.
No pseudocódigo:
fonte
J , 21 bytes
Experimente online!
Explicação
fonte
MATLAB 71 bytes
Isso converte a variável inteira 'a' em uma matriz binária int8 e conta o número de vezes que o resultado deve ser diferenciado até que não haja zero no resultado.
Eu sou novo aqui. Esse tipo de entrada e uma linha são permitidos pelas regras do PCG?
fonte
a
coma=input('');
. Além disso, alguns conselhos de golfe: em~a
vez dea==0
. Você realmente precisaint8
)?Oitava , 31 bytes
Experimente online!
Explicação
Esta é uma tradução da minha resposta MATL. Meu plano inicial era uma abordagem diferente, a saber
@(n)max(diff(find(diff([0 +dec2bin(n) 0]))))
. Mas acontece que o Octave tem umarunlength
função (sobre a qual acabei de descobrir). Por padrão, ele gera apenas a matriz de comprimentos de execução; portanto, o resultado desejado é omax
dessa matriz. A saída dedec2bin
, que é uma matriz de caracteres (string) contendo'0'
e'1'
, precisa ser convertida em uma matriz numérica usando+
, porquerunlength
espera entrada numérica.fonte
Utilitários Bash / Unix,
666542 bytesObrigado a @DigitalTrauma por melhorias significativas (23 bytes!).
Experimente online!
fonte
Bash (+ coreutils, + GNU grep),
33, 32 bytesEDITAR% S:
Golfe
Explicado
Experimente Online!
fonte
Braquilog , 9 bytes
Experimente online!
Explicação
fonte
C #, 106 bytes
Versão formatada:
E uma abordagem alternativa de acessar a string pelo índice em 118 bytes, com o espaço em branco removido:
fonte
Javascript, 66 bytes
Obrigado ao manatwork pelo código.
Explicação
Converta o número em sequência binária.
Divida cada caractere diferente (0 ou 1) (esse regex captura espaços vazios, mas eles podem ser ignorados)
Para cada elemento da matriz, obtenha seu comprimento e coloque-o na matriz retornada.
Converter matriz em lista de argumentos ([1,2,3] -> 1,2,3)
Obtenha o maior número dos argumentos.
fonte
x=>x.toString(2).split(/(0+|1+)/g).map(y=>y.length).sort().pop()
. Ou o mesmo comprimento:x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.length))
.sort((a,b)=>b-a)
. Por padrão, a função de classificação coloca10
entre1
e2
.Maravilha , 27 bytes
Uso:
Converte em binário, corresponde a cada sequência de 0 e 1, obtém a duração de cada correspondência e o máximo.
fonte
Lote, 102 bytes
Porto da resposta do @ edc65.
%2
..%4
ficará vazio na primeira chamada, então eu tenho que escrever as expressões de forma que elas ainda funcionem. O caso mais geral é o%3
qual eu tive que escrever como(%3+0)
.%2
é mais fácil, pois só pode ser0
ou1
, que são iguais em octal, então0%2
funciona aqui.%4
acabou sendo ainda mais fácil, pois só preciso subtraí-lo.(%4-r>>5)
é usado para compararl
comr
a do lote deset/a
não ter um operador de comparação.fonte
Dyalog APL , 22 bytes
Trem de função anônima
⌈/∘(
... O máximo dos resultados do seguinte trem de função anônimo ...≢¨
a contagem de cada⊢⊂⍨
partição do argumento, onde a partição é determinada por aqueles em1,
um anexado a2≠/
o desigual par de⊢
o argumento)
aplicado a2⊥⍣¯1
da base 2 aplicada negativa uma vez (ou seja, à base 2, uma vez) para⊢
o argumentoTryAPL online!
fonte
Japonês, 15 bytes
Teste online! ou Verifique todos os casos de teste de uma só vez .
Como funciona
fonte
R,
4534 bytesCorrigido um mal entendido graças a @rturnbull e @plannapus.
fonte
0
ou de1
, não apenas0
, certo?PowerShell ,
787473 bytesExperimente online!
Ugh esses métodos .Net.
Isso apenas usa uma regex para encontrar (e corresponder) seqüências contíguas de uns e zeros, e leva o
Length
propriedade (com um novo padrão que descobri que usa um conjunto de parâmetros pouco conhecido deForEach-Object
, para salvar 1 byte) dos objetos de correspondência resultantes, classifica-os e gera o último (o maior).fonte
J, 27 bytes
Uma abordagem ligeiramente diferente (e infelizmente mais longa) para resposta das milhas .
Uso:
Explicação
fonte