introduction

Je veux trouver la sous-chaîne avec le plus 1 dans une séquence de 0«et 1».

Contribution

Votre programme a deux entrées , la séquence et la longueur de la sous-chaîne.

La séquence est un nombre quelconque de 0«et 1»:

01001010101101111011101001010100010101101010101010101101101010010110110110

La longueur de la sous-chaîne est un entier positif non nul:

5

Production

Votre programme devrait sortir l'index de départ de la première sous-chaîne de la longueur donnée qui contient le plus 1. Avec l'entrée ci-dessus, la sortie est:

10

Le premier caractère de la chaîne commence à un index de 0.

Notation

Le code le plus court gagne!

Règles

• Votre programme doit toujours générer l'index correct pour toute entrée valide.
• Vous pouvez choisir votre méthode d'entrée / sortie à partir de n'importe quelle réponse avec un score positif sur les options par défaut . Veuillez spécifier la méthode que vous choisissez dans votre réponse.

Dyalog APL, 11

(-∘1+⍳⌈/)+/

Essayez-le ici. Usage:

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

Explication

Il s'agit d'une fonction dyadique (signifiant binaire) qui prend la longueur de la sous-chaîne à gauche et la séquence à droite. Sa structure est la suivante:

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

Explication par explosion:

(-∘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)

À titre d'exemple, prenons 4et 0 1 1 0 1 1 1 0comme entrées. D'abord, nous leur appliquons la fonction +/et obtenons 2 3 3 3 3. Ensuite, +et ⌈/appliqué à ce tableau, donnez-lui et 3, et 2 3 3 3 3 ⍳ 3évaluez à 2, puisque 3premier apparaît comme deuxième élément. Nous soustrayons 1et obtenons 1le résultat final.

Rubis, 42

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

Prend une entrée en l'appelant, par exemple

f['01001010101101111011101001010100010101101010101010101101101010010110110110',5]

Cela compare les sous-chaînes en utilisant leur valeur ASCII totale et renvoie l'index du maximum. Je ne sais pas si max_byla spécification Ruby est requise pour être stable, mais il semble que ce soit dans l'implémentation C.

Python 2, 56

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

Accepte un tableau d'entiers, puis la longueur.

Lot - 222

Batch est évidemment le langage parfait pour ce type d'opération.

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

Non golfé / disséqué:

La configuration initiale. La variable sest la chaîne d'entrée, et lsera la longueur de la chaîne d'entrée, moins la longueur de la sous-chaîne (initialisée à négatif %2où %2est la longueur de sous-chaîne donnée).

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

Obtenez la longueur de l'entrée en lutilisant une solution de longueur de chaîne Batch pure - cela modifie la variable scontenant la chaîne d'entrée, nous la définissons donc à nouveau.

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

La valeur de xest utilisée pour vérifier quelle sous-chaîne a le plus grand nombre de 1. Commencez une boucle de 0 à la longueur de la chaîne, moins la longueur de la sous-chaîne (variable l). Récupère la sous-chaîne à partir du point actuel dans la boucle ( %%a), cest définie comme la chaîne d'entrée commençant par %%aet prenant %2(la longueur de sous-chaîne donnée) des caractères. Tous les 0s sont supprimés de c, puis la valeur de cest comparée à x- c'est- à -dire 111est un nombre supérieur à 11ce que nous pouvons simplement utiliser la «chaîne» pour faire une comparaison supérieure à. yest ensuite défini à l'emplacement actuel dans la chaîne - qui est finalement sorti.

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!

Exemple d'utilisation des OP -

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

Le regex réel n'est pas si long, mais tous les fluffs nécessaires pour qu'un programme C # compile le double de la taille du code.

La regex réelle, définissant la longueur à 5:

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

• (?=((?<o>1)|0){5}): Anticipez pour lire 5 caractères sans consommer, et poussez tous 1dans la "pile" o.
• (?=[10]{5})(?!((?<-o>1)|0){5}): À une position qui a 5 caractères devant, il n'y a pas assez d'objets dans la "pile" o pour sortir, c'est-à-dire que la sous-chaîne a strictement plus 1que ce que nous avons dans la position actuelle.
• (?!.+(?=[10]{5})(?!((?<-o>1)|0){5})): Une position telle que décrite ci-dessus est introuvable pour le reste de la chaîne, c'est-à-dire que toute position a un nombre inférieur ou égal à 1 .

Prendre le premier résultat donne la réponse, car toutes les sous-chaînes devant lui ont une sous-chaîne en avant avec plus 1 de, et nous avons vérifié que tout index plus grand que l'index actuel a un nombre inférieur ou égal à1 .

(Et j'apprends quelque chose de sympa: la "pile" est restaurée lors du retour en arrière).

Pyth , 12

Mho/<>GNHZUG

Cela définit une fonction g, qui nécessite une liste de nombres et un nombre en entrée. Par exemple

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

Vous pouvez le tester ici: Pyth Compiler / Executor

Explication:

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)

Alternative:

Mho_s<>GNHUG

J, 15 14 caractères

   ([:(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)

Soit sla chaîne et nla longueur de la sous-chaîne. Le résultat est r.

Calculez la convolution de savec une séquence d' nunités, puis trouvez le maximum. La convolution se fait facilement avecconv , et la maxfonction renvoie la position du premier maximum. Il est nécessaire de soustraire 1à l'index résultant, car l'indexation Matlab commence à 1, non 0.

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

Golfé:

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

Haskell, 64 62 octets

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

Usage:

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

Une fonction renvoyant la valeur demandée. La boucle for analyse la chaîne d'entrée en conservant un total cumulé, en enregistrant la position de la valeur maximale.

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

Non golfé

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

Test dans la console FireFox / FireBug

F("01001010101101111011101001010100010101101010101010101101101010010110110110",5)

Production 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

variables $set $ndoivent être définies sur la ligne de commande pour la chaîne de recherche et la longueur de la sous-chaîne, respectivement.

Cela fonctionnerait également dans n'importe quel langage de type C avec des fonctions appropriées pour substr_count()et strlen().

Mathematica, 38 36

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

Exemple:

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]

Production:

dix

C # (Linq), 148 octets

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

Formaté:

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

Prend l'entrée comme paramètres de méthode.

Ce qu'il fait:

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 octets

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

Mais avec des noms de fonction aussi longtemps que zipWithIndex, je suppose que Scala n'est pas le meilleur choix pour le golf de code.

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

Formaté:

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

Usage:

$ ./m1s 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

CJam, 25 21 octets

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

Testez-le ici.

Prend l'entrée comme un entier pour la longueur de la sous-chaîne, et un tableau de zéros et de uns comme séquence:

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]

Explication

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.";

Le résultat est imprimé automatiquement à la fin du programme.

Notez que je considère également des tranches qui commencent plus près de la fin que la longueur de sous-chaîne souhaitée, mais ce n'est pas grave, car ce sont des sous-chaînes de la dernière sous-chaîne valide et n'auront donc jamais plus de 1s que cette dernière sous-chaîne valide.

Java 329 octets

allait impliquer un .matches (regex), mais il aurait été presque identique aux solutions python ci-dessus, j'ai donc essayé une fenêtre coulissante à la place. nouveau ici, donc si quelqu'un a des pointeurs, soyez heureux de les entendre.

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

}