Wprowadzenie

Chcę znaleźć podciąg z największą liczbą 1w sekwencji 0„i 1”.

Wejście

Twój program ma dwa wejścia , sekwencję i długość podciągu.

Kolejność jest dowolna liczba 0„S 1” s

01001010101101111011101001010100010101101010101010101101101010010110110110

Długość podciągu jest dowolną dodatnią wartość niezerową całkowita:

5

Wynik

Twój program powinien wypisać indeks początkowy pierwszego podłańcucha o podanej długości, który zawiera najwięcej 1. Przy powyższym wejściu dane wyjściowe są następujące:

10

Pierwszy znak w ciągu zaczyna się od indeksu 0.

Punktacja

Najkrótszy kod wygrywa!

Zasady

• Twój program musi zawsze wyświetlać poprawny indeks dla wszystkich prawidłowych danych wejściowych.
• Możesz wybrać metodę wejścia / wyjścia z dowolnej odpowiedzi z pozytywnym wynikiem w opcjach domyślnych . Podaj metodę wybraną w odpowiedzi.

Dyalog APL, 11

(-∘1+⍳⌈/)+/

Wypróbuj tutaj. Stosowanie:

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

Wyjaśnienie

Jest to funkcja dynamiczna (czyli binarna), która pobiera długość podciągu od lewej, a sekwencję od prawej. Jego struktura jest następująca:

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

Wyjaśnienie przez wybuch:

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

Jako przykład weźmy 4i 0 1 1 0 1 1 1 0jak wejść. Najpierw zastosujemy +/dla nich funkcję i otrzymamy 2 3 3 3 3. Następnie, +i ⌈/stosuje się do tej tablicy i dają się 3i 2 3 3 3 3 ⍳ 3ocenia się 2, jako 3pierwszy występuje w drugim elemencie. Odejmujemy 1i otrzymujemy 1jako wynik końcowy.

Ruby, 42 lata

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

Pobiera dane, wywołując je, np

f['01001010101101111011101001010100010101101010101010101101101010010110110110',5]

To porównuje podciągi przy użyciu ich całkowitej wartości ASCII i zwraca indeks wartości maksymalnej. Nie jestem pewien, czy max_bywymagana jest stabilna specyfikacja Ruby, ale wydaje się, że jest w implementacji C.

Python 2, 56

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

Akceptuje tablicę liczb całkowitych, a następnie długość.

Partia - 222

Batch jest oczywiście idealnym językiem dla tego rodzaju operacji.

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

Nie golfa / rozcięta:

Początkowe ustawienia. Zmienna sjest łańcuchem wejściowym i lbędzie długością łańcucha wejściowego, pomniejszoną o długość łańcucha podrzędnego (zainicjalizowana przy wartości ujemnej, %2gdzie %2jest podana długość łańcucha podrzędnego).

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

Uzyskaj długość danych wejściowych jako l, używając rozwiązania o długości łańcucha Batch - to zmienia zmienną szawierającą łańcuch wejściowy, więc ustawiamy go ponownie.

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

Wartość xsłuży do sprawdzenia, który podciąg ma największą liczbę jedynek. Rozpocznij pętlę od 0 do długości łańcucha minus długość podciągu (zmienna l). Pobierz łańcuch podrzędny zaczynając od bieżącego punktu w pętli ( %%a), custawiany jako łańcuch wejściowy rozpoczynający się od %%ai przyjmujący %2znaki (podana długość łańcucha podrzędnego). Wszelkie 0s są usuwane c, a następnie cporównywana jest wartość x- tzn. 111Jest to większa liczba niż, 11więc możemy po prostu użyć „łańcucha” do wykonania większej niż porównanie. yjest następnie ustawiany na bieżącą lokalizację w ciągu - który jest ostatecznie wyprowadzany.

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!

Na przykładzie 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);}}

Rzeczywiste wyrażenie regularne nie jest tak długie, ale wszystkie puchnięcia potrzebne do skompilowania przez program C # dwukrotności kodu.

Rzeczywiste wyrażenie regularne, ustawiając długość na 5:

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

• (?=((?<o>1)|0){5}): Spoglądaj w przyszłość, aby przeczytać 5 znaków bez zużywania, i wepchnij wszystkie 1do „stosu” o.
• (?=[10]{5})(?!((?<-o>1)|0){5}): Na pozycji, która ma 5 znaków do przodu, w „stosie” nie ma wystarczającej ilości przedmiotu, oaby wyskoczyć, tzn. Podciąg ma znacznie więcej 1niż to, co mamy na bieżącej pozycji.
• (?!.+(?=[10]{5})(?!((?<-o>1)|0){5})): Pozycji opisanej powyżej nie można znaleźć dla reszty łańcucha, tzn. Wszystkie pozycje mają mniejszą lub równą liczbę 1.

Biorąc pierwszy wynik, daje odpowiedź, ponieważ wszystkie podciągi przed nim mają pewne podciągi z większą liczbą 1, a my sprawdzamy, czy jakikolwiek indeks większy niż bieżący indeks ma mniejszą lub równą liczbę 1.

(I uczę się czegoś ładnego: „stos” jest przywracany podczas cofania).

Pyth , 12

Mho/<>GNHZUG

Definiuje funkcję g, która wymaga listy liczb i liczby jako danych wejściowych. Na przykład

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

Możesz to przetestować tutaj: Pyth Compiler / Executor

Wyjaśnienie:

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)

Alternatywny:

Mho_s<>GNHUG

J, 15 14 znaków

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

Niech soznacza ciąg i ndługość podciągu. Rezultatem jest r.

Oblicz splot sz sekwencji njedności, a następnie znajdź maksimum. Konwolucję można łatwo wykonać conv, a maxfunkcja zwraca pozycję pierwszego maksimum. Konieczne jest odjęcie 1od wynikowego indeksu, ponieważ indeksowanie Matlaba zaczyna się od 1, a nie 0.

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

Gra w golfa:

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

Haskell, 64 62 bajtów

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

Stosowanie:

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

Funkcja zwracająca żądaną wartość. Pętla for skanuje ciąg wejściowy, zachowując bieżącą sumę, zapisując pozycję wartości maksymalnej.

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

Nie golfił

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

Testuj w konsoli FireFox / FireBug

F("01001010101101111011101001010100010101101010101010101101101010010110110110",5)

Wynik 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

zmienne $si $npowinny być zdefiniowane w wierszu poleceń odpowiednio do szukanego ciągu i długości podłańcucha.

Działa to również w dowolnym języku podobnym do C z odpowiednimi funkcjami dla substr_count()i strlen().

Mathematica, 38 36

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

Przykład:

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]

Wynik:

10

C # (Linq), 148 bajtów

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

Sformatowany:

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

Pobiera dane wejściowe jako parametry metody.

Co to robi:

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 bajtów

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

Ale z nazwami funkcji tak długo, jak zipWithIndex , chyba Scala nie jest najlepszym wyborem dla golfa kodowego.

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

Sformatowany:

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

Stosowanie:

$ ./m1s 01001010101101111011101001010100010101101010101010101101101010010110110110 5
10

CJam, 25 21 bajtów

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

Sprawdź to tutaj.

Pobiera dane wejściowe jako liczbę całkowitą dla długości podłańcucha, a tablicę zer i jedynek jako sekwencję:

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]

Wyjaśnienie

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

Wynik jest drukowany automatycznie na końcu programu.

Zauważ, że rozważam również wycinki, które zaczynają się bliżej końca niż pożądana długość podciągu, ale to dobrze, ponieważ są podciągami ostatniego ważnego podłańcucha i dlatego nigdy nie będą miały więcej 1s niż ten ostatni prawidłowy podłańcuch.

Java 329 bajtów

zamierzałem zaimplementować .matches (regex), ale byłoby to prawie identyczne z powyższymi rozwiązaniami Pythona, więc zamiast tego spróbowałem przesuwać okno. nowe tutaj, więc jeśli ktoś ma jakieś wskazówki, chętnie je usłyszę.

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

}