Find the substring with the most 1's in a sequence

Question

Introduction

I want to find the substring with the most 1's in a sequence of 0's and 1's.

Input

Your program has two inputs, the sequence and the substring length.

The sequence is any number of 0's and 1's:

01001010101101111011101001010100010101101010101010101101101010010110110110

The substring length is any positive non-zero integer:

5

Output

Your program should output the starting index of the first substring of the given length that contains the most 1's. With the above input, the output is:

10

The first character in the string starts at an index of 0.

Scoring

Shortest code wins!

Rules

• Your program must always output the correct index for any valid inputs.
• You can pick your input/output method from any answer with positive score on the default options. Please specify the method you pick in your answer.

Answer 1

Dyalog APL, 11

(-∘1+⍳⌈/)+/

Try it here. Usage:

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

Explanation

This is a dyadic (meaning binary) function that takes the substring length from the left, and the sequence from the right. Its structure is the following:

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

Explanation by 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)

As an example, let's take 4 and 0 1 1 0 1 1 1 0 as inputs. First we apply the function +/ to them and get 2 3 3 3 3. Then, + and ⌈/ applied to this array give itself and 3, and 2 3 3 3 3 ⍳ 3 evaluates to 2, since 3 first occurs as the second element. We subtract 1 and get 1 as the final result.

Answer 2

Ruby, 42

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

Takes input by calling it, e.g.

f['01001010101101111011101001010100010101101010101010101101101010010110110110',5]

This compares substrings using their total ASCII value and returns the index of the maximum. I'm not sure if max_by is required by the Ruby spec to be stable but it appears to be in the C implementation.

Answer 3

Python 2, 56

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

Accepts an array of integers, then the length.

Answer 4

Batch - 222

Batch is obviously the perfect language for this kind of operation.

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

Un-golfed / dissected:

Initial setup. The variable s is the input string, and l will be the length of the input string, minus the sub-string length (initialized at negative %2 where %2 is the given sub-string length).

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

Get the length of the input as l, using a pure Batch string length solution - this mangles the variable s containing the input string, so we then set it again.

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

The value of x is used to check which sub-string had the greatest number of 1's. Start a loop from 0 to the length of the string, minus the sub-string length (variable l). Get the sub-string starting from the current point in the loop (%%a), c is set as the input string starting at %%a, and taking %2 (the given sub-string length) characters. Any 0s are removed from c, then the value of c is compared to x - i.e. 111 is a greater number than 11 so we can just use the 'string' to do a greater than comparison. y is then set to current location in the string - which is finally outputted.

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!

Using OPs example -

h:\>sub1.bat 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

Answer 5

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

The actual regex is not that long, but all the fluffs needed for a C# program to compile double the size of the code.

The actual regex, setting the length to 5:

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

• (?=((?<o>1)|0){5}): Look-ahead to read 5 characters without consuming, and push all 1's into "stack" o.
• (?=[10]{5})(?!((?<-o>1)|0){5}): At a position which has 5 characters ahead, there is not enough item in "stack" o to pop out, i.e. the substring has strictly more 1 than what we have in the current position.
• (?!.+(?=[10]{5})(?!((?<-o>1)|0){5})): A position as described above can't be found for the rest of the string, i.e. all position has less than or equal number of 1's.

Taking the first result gives the answer, since all substrings in front of it has some substring ahead with more 1's, and we have check that any index larger than the current index has less than or equal number of 1's.

(And I learn something nice: the "stack" is restored on backtracking).

Answer 6

Pyth, 12

Mho/<>GNHZUG

This defines a function g, which requires a list of numbers and a number as input. E.g.

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

You can test it here: Pyth Compiler/Executor

Explanation:

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

Answer 7

J, 15 14 chars

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

Answer 8

Haskell, 64 62 Bytes

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]

Answer 9

Matlab (42)

Let s denote the string and n the substring length. The result is r.

Compute convolution of s with a sequence of n ones, then find the maximum. Convolution is done easily with conv, and the max function returns the position of the first maximum. It's necessary to subtract 1 to the resulting index, because Matlab indexing starts at 1, not 0.

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

Golfed:

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

Answer 10

JavaScript (ES6) 73

A function returning the requested value. The for loop scans the input string keeping a running total, saving the position of the max value.

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

Test In FireFox/FireBug console

F("01001010101101111011101001010100010101101010101010101101101010010110110110",5)

Output 10

Answer 11

Mathematica, 38 36

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

Example:

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]

Output:

10

Answer 12

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 $s and $n should be defined on the command line to the search string and substring length, respectively.

This would also work in any C-like language with appropriate functions for substr_count() and strlen().

Answer 13

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

Formatted:

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

Takes input as method params.

What it does:

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

Answer 14

Scala - 70 Bytes

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

But with function names as long as zipWithIndex I guess Scala is not the best choice for code golf.

Answer 15

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

Formatted:

#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

Answer 16

CJam, 25 21 bytes

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

Test it here.

Takes input as an integer for the substring length, and an array of zeroes and ones as the sequence:

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]

Explanation

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

The result is printed automatically at the end of the program.

Note that I'm also considering slices that start closer to the end than the desired substring length, but that's okay, because they are substrings of the last valid substring and will therefore never have more 1s than that last valid substring.

Answer 17

Java 329 bytes

was going to implent a .matches(regex), but it would have been near identical to the python solutions above, so i tried a sliding window instead. new here, so if anyone has any pointers be glad to hear them.

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

}