Znajdź najdłuższą serię prawdy na liście booleanów. Zwróć tę samą listę, a wszystkie inne prawdy sfałszowane.

Wejście wyjście

Lista; dowolny zwykły format (np. lista rozdzielana jako ciąg).

Detale

Prawda i fałsz mogą być wszystkim, czego Twój język używa do tych wartości, lub liczbami całkowitymi 1 i 0. Jeśli używasz pojedynczych znaków, lista może być konkatenacją (np 10001.).

Jeśli istnieje remis dla najdłuższego biegu, utrzymuj wszystkie wiązania wiązania prawdziwe, i fałszuj wszystkie krótsze przebiegi.

Przykłady

input ↦ output
1,0,1,0,1 ↦ 1,0,1,0,1
1,1,0,1,1,0,1 ↦ 1,1,0,1,1,0,0
1,1,0,1,1,1,0,1,1 ↦ 0,0,0,1,1,1,0,0,0
1,1,1 ↦ 1,1,1
0,0,1 ↦ 0,0,1
0,0 ↦ 0,0
1,1,1,0,0,0,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,0,0,1,0 ↦ 0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0

(bezpośrednio z /programming//q/37447114 )

Galaretka , 8 bajtów

ṣ0¬¬M¦j0

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

ṣ0¬¬M¦j0  Main link. Argument: A (list of Booleans)

ṣ0        Split at zeroes. This leaves a 2D list of ones.
  ¬       Negate each 1, replacing it with 0.
     ¦    Conditional application:
    M       Yield all maximal indices.
            In lexicographical list comparison, a shorter list of zeroes is less
            than a longer one, so this identifies the longest runs.
   ¬        Negate the items in those lists, changing zeroes back to ones.
      j0  Join, separating by single zeroes.

Haskell, 59 , 58 , 55 , 64 bajtów

import Data.List
((=<<)=<<(=<<)(<$).(==).maximum.([1<2]:)).group

Zabawna uwaga, działa to na dowolnej liście wartości gdzie falsy < truthy. Więc False/True, 0/1, 'f'/'t', itd.

Uwaga:

Jak zauważyło kilka osób (w tym @proud haskelleri @nimi), poprzednia wersja nie powiodła się na liście wszystkich wartości fałszowania. Dodanie .([1<2]:)poprawiło to, zgodnie z sugestią @proud haskeller. Na razie pozostawiam to samo wyjaśnienie, ponieważ myślę, że nadal ma sens. Jeśli ktoś komentuje i poprosi o wyjaśnienie edycji, dokonam edycji.

Wyjaśnienie:

Najpierw odinstaluję bez group, a następnie dodam z powrotem. Po pierwsze, stwierdzam, że słowa są często łatwiejsze dla oczu niż symboli, więc dokonam kilku podstawień. (Zauważ, że =<<jest to „klasyczne”, więc ma inne zastosowanie do list i funkcji. Dzwonię binddo wersji =<<funkcji).

bind :: (a -> b -> c) -> (b -> a) -> b -> c
bind k f = k =<< f
bind k f = \ r -> k (f r) r

f = ((=<<)=<<(=<<)(<$).(==).maximum)
f = ((bind) concatMap (bind)(<$).equals.maximum)
f = (bind concatMap (bind (<$) . equals . maximum))
f = bind concatMap ((bind (<$)) . equals . maximum))
f = bind concatMap ((\f r -> (<$) (f r) r) . equals . maximum))
f = bind concatMap ((\f r -> (f r) <$ r) . equals . maximum)
f = bind concatMap ((\g r -> (g r) <$ r) . equals . maximum)
f = (\h r -> concatMap (h r) r) ((\g r -> (g r) <$ r) . equals . maximum)
f = \r -> concatMap (((\g r -> (g r) <$ r) . equals . maximum) r) r
f = \r -> concatMap (((\g r -> (g r) <$ r) . equals) (maximum r)) r
f = \r -> concatMap (((\g s -> (g s) <$ s)) (equals (maximum r))) r
f = \r -> concatMap (((\s -> ((equals (maximum r)) s) <$ s))) r
f = \r -> concatMap (\s -> (s == (maximum r)) <$ s) r

f . group = ((=<<)=<<(=<<)(<$).(==).maximum).group
f . group = \r -> concatMap (\s -> (s == (maximum (group r))) <$ s) (group r)

Ostatnie szczegóły są takie, że x <$ listzastępuje każdy element listz xi group listdzieli listsię na kawałki równych elementów. Tak group [1, 1, 2, 3, 3, 3] == [[1, 1], [2], [3, 3, 3]].

Podsumowując, funkcja dzieli listę wartości na grupy tylko prawda i grupy tylko fałsz. Następnie dla każdej grupy zamień każdy element na wynik instrukcji this is the biggest group(największa grupa truebędzie największa) i połącz grupy.

Cztery bajty zapisane przez @Zgarb

Siatkówka oka, 47 43 36

0
!
T`p`0`\b(1+)\b(?<=(?=.*1\1).*)|!

Wypróbuj online! lub wypróbuj wszystkie przypadki testowe

Dzięki msh210 za grę w golfa 4 bajty!

Wielkie podziękowania dla Martina za 7 bajtów!

Wyjaśnienie:

0
!

Zamień wszystkie 0s na !s. Robi się to, aby dopasować grupy 1s, tak jak teraz, 1!i !1będą miały \bmiędzy nimi granicę słowa ( ), która również pasuje do początku lub końca łańcucha.

T`p`0`

Jest to opcja konfiguracji mówiąca, że ​​po zastosowaniu wyrażenia regularnego po kliknięciu wstecz na dane wejściowe, w każdym dopasowaniu tłumaczy każdy drukowany znak ascii na 0znak.

\b(1+)\b(?<=(?=.*1\1).*)|!

Ten wyrażenie regularne pasuje do grup 1s otoczonych zerami, ale nie może pasować do 1następnej po sobie w dowolnym miejscu ciągu. Są to nie maksymalne grupy, które zostaną sfałszowane. Ponadto, pasuje to również do !znaków, które dodaliśmy, aby przekonwertować je z powrotem na 0s.

MATL, 14 bajtów

Y'yy*X>y=b*wY"

Wypróbuj online!

Zmodyfikowana wersja ze wszystkimi przypadkami testowymi

Wyjaśnienie

        % Implicitly grab the input as an array
Y'      % Perform run-length encoding of the input. Yields an array of values and an array
        % of run-lengths
yy      % Copy these outputs
*       % Multiply the values (booleans) by the run-lengths. This will zero-out all
        % zero-valued runs so we don't consider them when computing the longest run.
X>      % Compute the longest run of 1's
y       % Copy the run lengths vector
=       % Determine which runs are the same length as the longest run of ones
b*      % Bubble-up the values from the run-length encoding and multiply element-wise
        % With this boolean. This substitutes all 1's that are not in the longest run
        % of ones with 0's
w       % Flip the run-lengths and values on the stack
Y"      % Perform run-length decoding using these substituted values
        % Implicitly display the resulting boolean

Python 2, 62 bajty

lambda s:'0'.join(`1-(t+'1'in s)`*len(t)for t in s.split('0'))

Przetestuj na Ideone .

Jak to działa

s.split('0')Dzieli ciąg wejściowy s do tras zera lub więcej 1 „s

Dla każdego przebiegu t sprawdzamy, czy t+'1'jest podciągiem s .

• Jeśli tak, przebieg nie jest maksymalny, t+'1'in szwróć True , 1-(t+'1'in s)zwróć 1 - True = 0, a przebieg zostanie zastąpiony biegiem 0 tej samej długości.

• Jeśli tak nie jest, bieg jest maksymalny, t+'1'in szwraca False , 1-(t+'1'in s)zwraca 1 - False = 1, a bieg jest zastępowany biegiem 1 tej samej długości, tj. Sam.

Wreszcie '0'.joinprzywraca wszystkie usunięte 0 .

J, 25 bajtów

[:(}.=>./)@;0<@(*#);.1@,]

Jest to czasownik monadyczny, który przyjmuje i zwraca tablicę 0-1. Użyj tego w ten sposób:

   f =: [:(}.=>./)@;0<@(*#);.1@,]
   f 1 1 0 1 1 1 0 1 1
0 0 0 1 1 1 0 0 0

Wyjaśnienie

[:(}.=>./)@;0<@(*#);.1@,]  Input is y.
            0          ,]  Prepend 0 to y, and
                   ;.1@    cut the result along occurrences of 0,
                           so that each piece begins with a 0.
               (*#)        Multiply each piece element-wise by its length,
             <@            and put it in a box.
                           Without the boxing, the pieces would go in a 0-padded array.
           ;               Join the pieces back together.
                           Now all runs of 1 have been replaced by runs of (1+length of run).
[:(      )@                Apply verb in parentheses:
   }.                        remove the prepended 0,
     =                       form the 0-1 array of equality with
      >./                    the maximum value.

Pyth, 26 24 23 21 bajtów

M,G&HGJrgMrQ8 9qReSJJ

Zestaw testowy.

• Używa 1/0lub true/falsew danych wejściowych.
• Wykorzystuje true/falsew wyniku.

Wyjaśnienie

M,G&HGJrgMrQ8 9qReSJJ

           Q      input
          r 8     run-length encode
        gM        convert each run of 1 to their length
                  for example: [1,1,1,0,1,1] will be
                  converted to [3,3,3,0,2,2]
                  in the run-length encoded version
                  [1,1,1,0,1,1] will be [[3,1],[1,0],[2,1]]
                  [3,3,3,0,2,2] will be [[3,3],[1,0],[2,2]]
                  therefore basically [G,H] becomes [G,H and G]
                  which is what the code below does:
M,G&HG            def g(G,H): return [G,H and G]
       r      9   run-length decode
      J           store to J

               qReSJJ

                R   J   in each element of J
               q eSJ    check if equal to maximum of J

Poprzednie 23 bajty

M,G&HGJrgMrQ8 9msqdeSJJ

Zestaw testowy.

• Używa 1/0lub true/falsew danych wejściowych.
• Wykorzystuje 1/0w wyniku.

Poprzednie 24 bajty

Jrm,hd&edhdrQ8 9msqdeSJJ

Zestaw testowy.

• Używa 1/0lub true/falsew danych wejściowych.
• Wykorzystuje 1/0w wyniku.

Poprzednie 26 bajtów

rm?nhdeS.u&YhNQ0,hd0drQ8 9

Zestaw testowy.

• Używa 1/0lub true/falsew danych wejściowych.
• Wykorzystuje 1/0w wyniku.

Oracle SQL 12.1, 137 135 bajtów

SELECT REPLACE(REPLACE(REPLACE(:1,m,2),1,0),2,m)FROM(SELECT MAX(TRIM(COLUMN_VALUE))m FROM XMLTABLE(('"'||REPLACE(:1,0,'",0,"')||'"')));

Nie grał w golfa

-- Replace the max value with 2
-- Then replace every 1 with 0
-- Then replace 2 with the max value
SELECT REPLACE(REPLACE(REPLACE(:1,m,2),1,0),2,m)
FROM   ( -- Split on 0 and keep the max value
         SELECT MAX(TRIM(COLUMN_VALUE))m 
         FROM XMLTABLE(('"'||REPLACE(:1,'0','",0,"')||'"'))
       );

Wprowadź użyj pojedynczych znaków. Np .: „1100111”

Mathematica , 46 41

1-Join@@Sign[1~Max~#-#]&[#*Tr/@#]&@*Split

Działa na listach 0i 1. Myślałem, że poradziłem sobie całkiem dobrze, dopóki nie spojrzałem na inne odpowiedzi!

Wyjaśnienie dotyczące wersji 46 znaków; Będę aktualizować, gdy nie będę mógł go dalej ulepszać.

Poproszono o wyjaśnienie tego kodu.
Niekodowy ekwiwalent golfa (przy użyciu formularzy operatora w wersji 10) to:

RightComposition[
  Split,
  Map[# Tr@# &],
  # - Max[1, #] &,
  UnitStep,
  Apply[Join]
]

Oznacza to funkcję złożoną z pięciu kroków (podfunkcji) zastosowanych w kolejności od góry do dołu.

• Split: rozbicie na serie identycznych elementów: {1,1,0,1,1,0,1} ↦ {{1,1}, {0}, {1,1}, {0,0}}

• Map[# Tr@# &]: Dla każdej podlisty ( Map) pomnóż ją ( #) przez jej sumę (ślad wektorowy Tr): {1,1} ↦ {2, 2}

• # - Max[1, #] &odejmij od każdego elementu maksymalną wartość pojawiającą się w dowolnym miejscu na liście list lub jeden, w zależności od tego, która wartość jest wyższa. (Ten obsługuje wielkość liter wszystkich zer).

• UnitStep: równa 0 dla x <0 i 1 dla x> = 0, stosowane do każdego elementu.

• Apply[Join]: połącz podlisty w jedną listę. Można to również zrobić za pomocą Flattenlub Catenate, ale w skrócie Join@@jest bardziej zwięzły.

C, 135 129 bajtów

Wypróbuj online

m,c,i,d,j;f(int*l,int s){while(i<s)c=l[i++]?c+1:0,m=c>m?c:m;while(j<s)if(l[j++])d=d+1;else if(d<m)while(d)l[j-1-d--]=0;else d=0;}

Nie golfił

m,c,i;
f(int*l,int s)
{
    // obtain max
    while(i<s)
        c = l[i++] ? c+1 : 0,
        m = c>m ? c : m;

    c=0,i=0;

    // remove smaller segments
    while(i<s)
        if(l[i++]) c=c+1;
        else if(c<m) while(c) l[(i-1)-c--]=0;
        else c=0;
}

JavaScript (ES6), 56 bajtów

s=>s.replace(/1+/g,t=>t.replace(/1/g,+!~s.indexOf(t+1)))

Działa poprzez sprawdzanie wszystkich przebiegów 1s i zastępowanie znaków zerami, chyba że przebieg jest (równie) najdłuższy, mierzony przez przeszukiwanie ciągu pod kątem dłuższego ciągu 1s.

Poprzednie 72-bajtowe rozwiązanie rekurencyjne:

f=s=>/11/.test(s)?f(s.replace(/1(1*)/g,"0$1")).replace(/0(1+)/g,"1$1"):s

Nie robi nic, jeśli nie ma serii 1 (tzn. Najwyżej pojedynczych 1). W przeciwnym razie odejmuje jeden 1z każdego 1lub jednego z nich , a następnie wywołuje się rekurencyjnie w krótszych seriach, a następnie dodaje jeden z 1powrotem w przypadku (obecnie równie najdłuższych) serii. Liczba wywołań rekurencyjnych jest o jeden mniejsza niż długość najdłuższego przebiegu.

Julia, 51 bajtów

s->replace(s,r"1+",t->map(c->c-contains(s,"1"t),t))

Wypróbuj online!

Jak to działa

replacewyszukuje wszystkie przebiegi jednego lub więcej 1 w ciągu wejściowym s poprzez wyrażenie regularne r"1+"i wywołuje lambda w t->map(c->c-contains(s,"1"t),t)celu ustalenia ciągu zastępującego.

Mapa lambda obejmuje c->c-contains(s,"1"t)wszystkie postacie z serii t .

• Jeśli "1"t(konkatenacji) jest podłańcuchem s , bieg nie jest maksymalna, containspowraca prawdziwa i c-contains(s,"1"t)powraca „1” - PRAWDA = „0” , zastępując wszystkie 1 „S w tym cyklu z 0 ” S.

• Jeśli "1"t(konkatenacja) nie jest podciągiem s , przebieg jest maksymalny, containszwraca false i c-contains(s,"1"t)zwraca „1” - false = „1” , pozostawiając przebieg niezmodyfikowany.

APL, 22 znaki

(⊣=⌈/)∊(⊣×+/¨)(~⊂⊣)0,⎕

W języku angielskim (od prawej do lewej w blokach):

• dodaj 0 do wejścia
• pole zaczynające się od 0
• pomnóż każde pole przez jego sumę
• spłaszczyć
• 1, jeśli liczba jest równa maksimum, 0 w przeciwnym razie

Java 8, 205 bajtów

To jest wyrażenie lambda dla Function<String,String>:

s->{int x=s.length();for(String t="1",f="0";s.indexOf(t+1)>=0;t+=1){s=s.replaceAll(0+t+0,0+f+0);if(s.indexOf(t+0)==0)s=s.replaceFirst(t,f);if(s.lastIndexOf(0+t)==--x-1)s=s.substring(0,x)+f;f+=0;}return s;}

wejście / wyjście to miejsce, Stringgdzie prawda jest reprezentowana przez 1, a fałsz jest reprezentowany przez 0. Nie ma znaków ograniczających oddzielających wartości.

kod z wyjaśnieniem:

inputString -> {
  int x = inputString.length();
  //starting with the truth combination "1",
  //loop until the input string does not contain the combination appended with another "1"
  //with each consecutive loop appending a "1" to the combination
  for( String truthCombo = "1", falseCombo = "0"; inputString.indexOf( truthCombo + 1 ) >= 0; truthCombo += 1 ) {
    //all instances in the input string 
    //where the combination has a "0" on either side of it
    //are replaced by "0"'s
    inputString = inputString.replaceAll( 0 + truthCombo + 0, 0 + falseCombo + 0 );
    //if the combination followed by a "0"
    //is found at the beginning of the input string
    //replace it with "0"'s
    if( inputString.indexOf( truthCombo + 0 ) == 0 )
      inputString = inputString.replaceFirst( truthCombo , falseCombo );
    //if the combination preceeded by a "0"
    //is found at the end of the input string
    //replace it with "0"'s
    if( inputString.lastIndexOf( 0 + truthCombo ) == --x - 1 )
      inputString = inputString.substring( 0, x ) + falseCombo;
    falseCombo += 0;
  }
  return inputString;
}

zobacz ideone dla przypadków testowych

Clojure, 137 bajtów

#(let[v(map(juxt first count)(partition-by #{1}%))](mapcat(fn[t](repeat(t 1)(if(=[1(apply max(map(fn[[f c]](if(= 1 f)c 0))v))]t)1 0)))v))

Najpierw dzieli dane wejściowe na kolejne zera i jedynki i mapuje je na „krotki” pierwszego elementu partycji i liczbę elementów. Następnie powtarza potrzebną liczbę zer lub jedynek, w zależności od tego, czy jest to sekwencja jedności, czy nie.

Mniej golfa:

(def f #(let [v(map(juxt first count)(partition-by #{1}%))
              m(apply max(map(fn[[f c]](if(= 1 f)c 0))v))]
           (mapcat (fn[[f c]](repeat c(if(=[1 m][f c])1 0))) v)))

Perl 5, 68 bajtów

67, plus 1 za -pezamiast-e

y/0/ /;$_<${[sort@a]}[-1]&&y/1/0/for@a=split/\b/;$_=join"",@a;y; ;0

Oczekuje i drukuje ciąg (konkatenację) zera i jedynki.