Introdução

Eu quero encontrar a substring com mais 1's' em uma sequência de 0's 1' e 's.

Entrada

Seu programa possui duas entradas , a sequência e o comprimento da substring.

A sequência é qualquer número de 0'se 1':

01001010101101111011101001010100010101101010101010101101101010010110110110

O comprimento da substring é qualquer número inteiro diferente de zero positivo:

5

Resultado

Seu programa deve gerar o índice inicial da primeira substring do comprimento especificado que contém mais 1. Com a entrada acima, a saída é:

10

O primeiro caractere na sequência começa em um índice de 0.

Pontuação

O código mais curto vence!

Regras

• Seu programa sempre deve gerar o índice correto para quaisquer entradas válidas.
• Você pode escolher seu método de entrada / saída em qualquer resposta com pontuação positiva nas opções padrão . Especifique o método escolhido na sua resposta.

Dyalog APL, 11

(-∘1+⍳⌈/)+/

Experimente aqui. Uso:

   f ← (-∘1+⍳⌈/)+/
   4 f 0 1 1 0 1 1 1 0 0 0 0 1 1
1

Explicação

Essa é uma função diádica (que significa binária) que pega o comprimento da substring da esquerda e a sequência da direita. Sua estrutura é a seguinte:

   ┌───┴────┐
 ┌─┴──┐     /
 ∘  ┌─┼─┐ ┌─┘
┌┴┐ + ⍳ / +  
- 1   ┌─┘    
      ⌈      

Explicação por explosão:

(-∘1+⍳⌈/)+/
(       )+/  ⍝ Take sums of substrings of given length, and feed to function in parentheses
    + ⌈/     ⍝ The array of sums itself, and its maximum
     ⍳       ⍝ First index of right argument in left
 -∘1         ⍝ Subtract 1 (APL arrays are 1-indexed)

Como exemplo, vamos dar 4e 0 1 1 0 1 1 1 0como entradas. Primeiro aplicamos a função +/a eles e obtemos 2 3 3 3 3. Então, +e ⌈/aplicado a essa matriz, fornece-se e 3e é 2 3 3 3 3 ⍳ 3avaliado como 2, uma 3vez que ocorre primeiro como o segundo elemento. Subtraímos 1e obtemos 1como resultado final.

Ruby, 42

f=->s,n{(0..s.size).max_by{|i|s[i,n].sum}}

Recebe entrada chamando-o, por exemplo

f['01001010101101111011101001010100010101101010101010101101101010010110110110',5]

Isso compara substrings usando seu valor ASCII total e retorna o índice do máximo. Não tenho certeza se max_bya especificação do Ruby é exigida para ser estável, mas parece estar na implementação em C.

Python 2, 56

lambda s,l:max(range(len(s)),key=lambda i:sum(s[i:i+l]))

Aceita uma matriz de números inteiros, depois o comprimento.

Lote - 222

Lote é obviamente a linguagem perfeita para esse tipo de operação.

@echo off&setLocal enableDelayedExpansion&set s=%1&set l=-%2
:c
if defined s set/Al+=1&set "s=%s:~1%"&goto c
set s=%1&set x=0&for /l %%a in (0,1,%l%)do set c=!s:~%%a,%2!&set c=!c:0=!&if !c! GTR !x! set x=!c!&set y=%%a
echo !y!

Sem golfe / dissecado:

Configuração inicial. A variável sé a string de entrada e lserá o comprimento da string de entrada, menos o comprimento da sub-string (inicializado em negativo %2onde %2é o comprimento especificado da sub-string).

@echo off
setLocal enableDelayedExpansion
set s=%1
set l=-%2

Obtenha o comprimento da entrada como l, usando uma solução pura de comprimento de cadeia de lotes - isso manipula a variável que scontém a cadeia de entrada e, em seguida, a definimos novamente.

:c
if defined s (
    set /A l += 1
    set "s=%s:~1%"
    goto c
)
set s=%1

O valor de xé usado para verificar qual sub-string tem o maior número de 1s. Inicie um loop de 0 ao comprimento da string, menos o comprimento da sub-string (variável l). Obter a sub-string a partir do ponto atual no loop ( %%a), cé definido como a string de entrada iniciando em%%a e recebendo %2os caracteres (o comprimento especificado da sub-string). Se qualquer 0s for removido c, o valor de cé comparado a x- ou seja, 111é um número maior do que o de 11modo que podemos usar a 'string' para fazer uma comparação maior que a. yé então definido para o local atual na string - que é finalmente gerada.

set x=0
for /l %%a in (0, 1, %l%) do (
    set c=!s:~%%a,%2!
    set c=!c:0=!
    if !c! GTR !x! (
        set x=!c!
        set y=%%a
    )
)
echo !y!

Usando OPs exemplo -

h:\>sub1.bat 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

C # (Regex), 196

class Test{static void Main(string[]a){System.Console.Write(System.Text.RegularExpressions.Regex.Match(a[1],"(?=((?<o>1)|0){"+a[0]+"})(?!.+(?=[10]{"+a[0]+"})(?!((?<-o>1)|0){"+a[0]+"}))").Index);}}

O regex real não é tão longo, mas todos os fluffs necessários para um programa C # compilar o dobro do tamanho do código.

A regex real, configurando o comprimento para 5:

(?=((?<o>1)|0){5})(?!.+(?=[10]{5})(?!((?<-o>1)|0){5}))

• (?=((?<o>1)|0){5}): Olhe para a frente para ler 5 caracteres sem consumir e coloque tudo 1na "pilha"o .
• (?=[10]{5})(?!((?<-o>1)|0){5}): Em uma posição com 5 caracteres à frente, não há item suficiente na "pilha" opara sair, ou seja, a substring tem estritamente mais1 que o que temos na posição atual.
• (?!.+(?=[10]{5})(?!((?<-o>1)|0){5})): Uma posição como descrita acima não pode ser encontrada para o restante da string, ou seja, toda posição tem um número menor ou igual a 1's.

Obter o primeiro resultado fornece a resposta, uma vez que todas as subseqüências à frente têm subseqüências com mais 1's, e verificamos se qualquer índice maior que o índice atual tem um número menor ou igual a 1' s.

(E eu aprendo algo legal: a "pilha" é restaurada no retorno).

Pyth , 12

Mho/<>GNHZUG

Isso define uma função g, que requer uma lista de números e um número como entrada. Por exemplo

Mho/<>GNHZUGg[0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0)5

Você pode testá-lo aqui: Pyth Compiler / Executor

Explicação:

Mho/<>GNHZUG
M             defines a function g(G,H), G is the sequence, H the sequence length
  o       UG  orders the numbers between 0 and len(G)-1 according to the following key
    <>GNH     take the subsequence G[N:N+5]
   /     Z    count the zeros in this subsequence (this is the key)
 h            return the first value of the sorted list (minimum)

Alternativo:

Mho_s<>GNHUG

J, 15 14 caracteres

   ([:(i.>./)+/\)

   5 ([:(i.>./)+/\) 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0
10

Matlab (42)

Vamos sdenotar a string e no comprimento da substring. O resultado é r.

Calcule a convolução de scom uma sequência de nunidades e encontre o máximo. A convolução é feita facilmente com conv, e a maxfunção retorna a posição do primeiro máximo. É necessário subtrair 1para o índice resultante, porque a indexação do Matlab começa às 1, não 0.

[~, r] = max(conv(s, ones(1,n), 'valid'));
r = r-1;

Golfe:

[~,r]=max(conv(s,ones(1,n),'valid'));r=r-1

Haskell, 64 62 bytes

n#l=0-(snd$maximum[(sum$take n$drop x l,-x)|x<-[0..length l]])

Uso:

5#[0,1,0,0,1,0,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,0]

JavaScript (ES6) 73

Uma função retornando o valor solicitado. O loop for varre a sequência de entrada mantendo um total em execução, salvando a posição do valor máximo.

F=(a,n)=>(x=>{for(r=t=i=x;a[i];t>x&&(x=t,r=i-n))t+=a[i]-~~a[i++-n]})(0)|r

Ungolfed

F=(a, n) => {
   for(x = r = t = i = 0; a[i]; i++)
     t += a[i] - ~~a[i-n], // ~~ convert undefined values (at negative index) to 0
     t > x && (x=t, r=i-n+1);
   return r;
}

Teste no console do FireFox / FireBug

F("01001010101101111011101001010100010101101010101010101101101010010110110110",5)

Resultado 10

PHP (96)

for($a=$b=$c=0;(($d=@substr_count($s,1,$a,$n))>$c&&($b=$a)&&($c=$d))||$a++<strlen($s););echo $b;

http://3v4l.org/J4vqa

variáveis $se$n deve ser definido na linha de comando para a cadeia de caracteres de pesquisa e o comprimento da substring, respectivamente.

Isso também funcionaria em qualquer linguagem C, com funções apropriadas para substr_count()e strlen().

Mathematica, 38 36

f=#-1&@@Ordering[-MovingAverage@##]&

Exemplo:

f[{0,1,0,0,1,0,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,0},5]

Resultado:

10

C # (Linq), 148 bytes

using System.Linq;class C{int F(string s,int l){return s.IndexOf(s.Skip(l-1).Select((c,i)=>s.Substring(i,l)).OrderBy(p=>-p.Sum(c=>c)).First());}}

Formatado:

using System.Linq;

class C
{
    int F(string s, int l)
    {
        return s.IndexOf(
            s
                .Skip(l - 1)
                .Select((c, i) => s.Substring(i, l))
                .OrderBy(p => -p.Sum(c => c))
                .First()
        );
    }
}

Recebe entrada como parâmetros de método.

O que faz:

string result = s // string is also char collection
    .Skip(l - 1) // make it collection shorter by l-1
    .Select((c, i) => s.Substring(i, l)) // so we can iterate, and select all substrings
    .OrderBy(p => -p.Sum(c => c)) // order substrings descending by sum of characters
    .First() // take first (most ones)

return s.IndexOf(result); // find index of result string

Scala - 70 bytes

readLine.sliding(readInt).zipWithIndex.maxBy(x=>x._1.count(_=='1'))._2

Mas, com nomes de funções, desde que zipWithIndex , acho que Scala não é a melhor opção para código de golfe.

C, 245 185

#include <stdio.h>
main(int argc,char **argv){char *p,*q;int i,s,m=0;for(p=argv[1];*p;p++){for(s=0,q=p;q-p<atoi(argv[2])&&*q;q++)s+=*q-'0';if(s>m){m=s;i=p-argv[1];}}printf("%d\n", i);}

Formatado:

#include <stdio.h>
main(int argc, char **argv) {
        char *p, *q;
        int i, s, m = 0;
        for (p = argv[1]; *p; p++) {
                for (s = 0, q = p; q - p < atoi(argv[2]) && *q; q++)
                        s += *q - '0';
                if (s > m) {
                        m = s;
                        i = p - argv[1];
                }
        }
        printf("%d\n", i);
}

Uso:

$ ./m1s 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

CJam, 25 21 bytes

q~_,,{1$>2$<:+~}$(]W=

Teste aqui.

Recebe entrada como um número inteiro para o comprimento da substring e uma matriz de zeros e uns como a sequência:

5 
[0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0]

Explicação

q~_,,{1$>2$<:+~}$(p];
q~                    "Read and evaluate the input.";
  _,                  "Duplicate the sequence and get its length N.";
    ,                 "Get an array [0 1 ... N-1].";
     {         }$     "Sort this array stably by the result of the given block.";
      1$              "Copy the sequence.";
        >             "Slice off the first i bits.";
         2$           "Copy the substring length.";
           <          "Truncate the sequence.";
            :+        "Get the sum to find the number of 1s.":
              ~       "Bitwise complement in order to sort from highest to lowest.";
                 (    "Shift off the first index from the sorted list.";
                  ]   "Wrap the entire stack in an array.";
                   W= "Extract the last element (the result), discarding the rest.";

O resultado é impresso automaticamente no final do programa.

Observe também que estou considerando fatias que começam mais perto do final do que o comprimento de substring desejado, mas tudo bem, porque são substrings da última substring válida e, portanto, nunca terão mais 1s do que a última substring válida.

Java 329 bytes

ia implantar um .matches (regex), mas teria sido quase idêntico às soluções python acima, então tentei uma janela deslizante. novo aqui, então se alguém tiver alguma dica, fique feliz em ouvi-la.

public class ssMostOnes{
public static void main(String[] a){
    int b=0,w=0;
    for(int i=0;i<a[0].length()-Integer.valueOf(a[1]);i++){
        int c=a[0].substring(i,i+Integer.valueOf(a[1])).length() - a[0].substring(i,i+Integer.valueOf(a[1])).replace("1","").length();
        if(c>w){w=c;b=i;}
    }
    System.out.println(b);
}

}