Encuentre la ejecución más larga de verdadero en una lista de booleanos. Devuelve la misma lista, con todas las demás falsas falsas.

De entrada y salida

Una lista; cualquier formato habitual (por ejemplo, una lista delimitada como una cadena).

Detalles

Verdadero y falso puede ser cualquier cosa que su lenguaje use típicamente para esos valores, o los enteros 1 y 0. Si usa caracteres individuales, la lista puede ser una concatenación (por ejemplo, 10001).

Si hay un empate para la carrera más larga, mantén todas las carreras de empate verdaderas y falsifica todas las carreras más cortas.

Ejemplos

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

(directamente desde /programming//q/37447114 )

code-golf array-manipulation msh210
fuente

19

Jalea , 8 bytes

ṣ0¬¬M¦j0

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

ṣ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.

Dennis
fuente

23

Por Dios ... este idioma ...

AdmBorkBork

11

Haskell, 59 , 58 , 55 , 64 bytes

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

Nota divertida, esto funciona en cualquier lista de valores donde falsy < truthy. Así False/True, 0/1, 'f'/'t', etc.

Nota:

Como varias personas han señalado (incluyendo @proud haskellery @nimi), la versión anterior falló en una lista de todos los valores falsos. La adición de .([1<2]:)ha solucionado esto, como lo sugiere @proud haskeller. Dejo la explicación igual por ahora, porque creo que todavía tiene sentido. Si alguien comenta, solicitando una explicación de la edición, editaré.

Explicación:

Primero desugaré sin el group, y luego lo volveré a agregar. Primero, encuentro que las palabras son más fáciles de ver que los símbolos, así que haré algunas sustituciones. (Tenga en cuenta que =<<es 'elegante', por lo que se aplica de manera diferente para las listas y funciones. Llamo a bindla versión de =<<para funciones).

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)

Los últimos detalles son los que x <$ listreemplazan cada elemento del listcon xy lo group listdivide listen trozos de elementos iguales. Por lo tanto group [1, 1, 2, 3, 3, 3] == [[1, 1], [2], [3, 3, 3]].

Para resumirlo todo, la función divide la lista de valores en grupos de solo verdadero y grupos de solo falso. Luego, para cada grupo, reemplace cada elemento con el resultado de la declaración this is the biggest group(el grupo más grande trueserá el más grande) y concatene los grupos.

Cuatro bytes guardados por @Zgarb

Michael Klein
fuente

1

Creo que puedes reemplazarlo (\y->(maximum g==y)<$y)con ((<$)=<<(==maximum g)). Sin embargo, no lo he probado.

Zgarb

@ Zgarb Acabo de resolverlo a partir de la declaración de instancia y funciona. Gracias.

Michael Klein

3

Aún mejor: reemplace la definición completa de fpor la función sin puntos ((=<<)=<<(=<<)(<$).(==).maximum).group. ¡Ahorra tres bytes y es completamente ilegible!

Zgarb

@ Zgarb: ¡Genial! En ese punto, b=(=<<);b b(b(<$).(==).maximum).groupes un byte más corto aún. Nunca he visto algo así antes en Haskell golf :)

Lynn

1

Si no me equivoco, puede solucionarlo insertando (:[t])antes del máximo o algo similar

orgulloso Haskeller

6

Retina, 47 43 36

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

Pruébalo en línea! o prueba todos los casos de prueba

¡Gracias a msh210 por jugar al golf 4 bytes!

También muchas gracias a Martin por 7 bytes!

Explicación:

0
!

Reemplace todos los 0s con !s. Esto se hace para 1acortar los grupos de s, como ahora 1!y !1tendrá un límite de palabra ( \b) entre ellos, que también coincide con el inicio o el final de la cadena.

T`p`0`

Esta es una opción de configuración que dice que después de aplicar la expresión regular después del toque de retroceso a la entrada, en cada coincidencia, traducir cada carácter ascii imprimible en un 0carácter.

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

Esta expresión regular coincide con grupos de 1s rodeados por ceros, pero no puede coincidir con un 1seguido por sí mismo en ninguna parte de la cadena. Estos son los grupos no máximos que serán falsificados. Además, esto también coincide con los !caracteres que agregamos para convertirlos nuevamente en 0s.

FryAmTheEggman
fuente

5

MATL, 14 bytes

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

Pruébalo en línea!

Versión modificada con todos los casos de prueba.

Explicación

        % 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

Suever
fuente

4

Python 2, 62 bytes

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

Pruébalo en Ideone .

Cómo funciona

s.split('0')divide la cadena de entrada s en series de cero o más 1 's

Para cada ejecución t , verificamos si t+'1'es una subcadena de s .

Si es así, la ejecución no es máxima, t+'1'in sdevuelve True , 1-(t+'1'in s)devuelve 1 - True = 0 y la ejecución se reemplaza con una ejecución de 0 's de la misma longitud.
Si no es así, la ejecución es máxima, t+'1'in sdevuelve False , 1-(t+'1'in s)devuelve 1 - False = 1 y la ejecución se reemplaza con una ejecución de 1 's de la misma longitud, es decir, por sí misma.

Finalmente, '0'.joinrestaura todos los 0 eliminados .

Dennis
fuente

3

J, 25 bytes

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

Este es un verbo monádico que toma y devuelve una matriz 0-1. Úselo así:

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

Explicación

[:(}.=>./)@;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.

Zgarb
fuente

Buen uso de corte ;..

millas

3

Pyth, 26 24 23 21 bytes

M,G&HGJrgMrQ8 9qReSJJ

Banco de pruebas.

Usos 1/0o true/falseen entrada.
Usos true/falseen salida.

Explicación

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

23 bytes anteriores

M,G&HGJrgMrQ8 9msqdeSJJ

Banco de pruebas.

Usos 1/0o true/falseen entrada.
Usos 1/0en salida.

24 bytes anteriores

Jrm,hd&edhdrQ8 9msqdeSJJ

Banco de pruebas.

Usos 1/0o true/falseen entrada.
Usos 1/0en salida.

26 bytes anteriores

rm?nhdeS.u&YhNQ0,hd0drQ8 9

Banco de pruebas.

Usos 1/0o true/falseen entrada.
Usos 1/0en salida.

Monja permeable
fuente

Crear una función que solo se llama en una única ubicación es casi siempre un error. Por ejemplo, podría reemplazarlo con: Jr.b,N&YNrQ8)9qReSJJo Jrm,hd*FdrQ8 9qReSJJ. Ambas versiones guardan un byte. O ir aún más loco con JrXR1*FdrQ8 9qReSJJy guardar dos. ;-)

Jakube

2

Oracle SQL 12.1, 137135 bytes

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

Sin golf

-- 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,"')||'"'))
       );

La entrada usa caracteres individuales. Ej: '1100111'

Jeto
fuente

2

Mathematica , 46 41

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

Trabaja en listas de 0y 1. ¡Pensé que lo había hecho bastante bien hasta que miré las otras respuestas!

Explicación para la versión de 46 caracteres; Actualizaré cuando no pueda mejorarlo más.

Se solicitó una explicación de este código.
Un equivalente sin código de golf (utilizando formularios de operador de la versión 10) es:

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

Esto significa una función compuesta de cinco pasos (subfunciones) aplicadas en orden de arriba a abajo.

Split: se dividen en series de elementos idénticos: {1,1,0,1,1,0,1} ↦ {{1,1}, {0}, {1,1}, {0,0}}
Map[# Tr@# &]: Para cada sublista ( Map) multiplíquela ( #) por su suma (traza vectorial Tr): {1,1} ↦ {2, 2}
# - Max[1, #] &reste de cada elemento el valor máximo que aparece en cualquier lugar de la lista de listas, o uno, el que sea más alto. (El uno maneja el caso de todos los ceros).
UnitStep: igual a 0 para x <0 y 1 para x> = 0, aplicado a cada elemento.
Apply[Join]: une las sublistas en una sola lista. También podría hacerse con Flatteno Catenate, pero en forma abreviada Join@@es más conciso.

Señor mago
fuente

2

C, 135 129 bytes

Probar en línea

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

Sin golf

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

Khaled.K
fuente

1

JavaScript (ES6), 56 bytes

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

Funciona comprobando todas las ejecuciones de 1s y reemplazando los caracteres con 0s a menos que la ejecución sea (igualmente) más larga, según se mide buscando en la cadena una ejecución más larga de 1s.

Solución recursiva anterior de 72 bytes:

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

No hace nada si no hay corridas de 1s (es decir, 1s como máximo). De lo contrario, resta uno 1de cada uno 1o de cada uno de ellos, luego se llama recursivamente en las ejecuciones más cortas, luego agrega uno 1nuevamente en las ejecuciones (ahora igualmente más largas). El número de llamadas recursivas es uno menos que la duración de la ejecución más larga.

Neil
fuente

"En todas las corridas de 1s, reemplace cada 1 con 0 si existe una corrida de 1s una más larga que la corrida actual, de lo contrario reemplace con 0". ¡Brillante!

Patrick Roberts

1

Julia, 51 bytes

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

Pruébalo en línea!

Cómo funciona

replaceencuentra todas las ejecuciones de uno o más 1 's en la cadena de entrada s a través de la expresión regular r"1+"y llama a lambda t->map(c->c-contains(s,"1"t),t)para determinar la cadena de reemplazo.

La lambda asigna c->c-contains(s,"1"t)todos los caracteres en la ejecución de unos t .

Si "1"t(concatenación) es una subcadena de s , la ejecución no es máxima, containsdevuelve verdadero y c-contains(s,"1"t)devuelve '1' - verdadero = '0' , reemplazando todos los 1 's en esa ejecución con 0 ' s.
Si "1"t(concatenación) no es una subcadena de s , la ejecución es máxima, containsdevuelve falso y c-contains(s,"1"t)devuelve '1' - falso = '1' , dejando la ejecución sin modificar.

Dennis
fuente

1

APL, 22 caracteres

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

En inglés (de derecha a izquierda en bloques):

anteponer 0 a la entrada
cuadro que comienza con cada 0
multiplica cada caja por su suma
aplanar
1 si el número es igual al máximo, 0 de lo contrario

lstefano
fuente

1

Java 8, 205 bytes

Esta es una expresión lambda para a 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;}

input / output es un lugar Stringdonde verdadero está representado por 1 y falso está representado por 0. No hay caracteres delimitadores que separen los valores.

código con explicación:

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

ver ideone para los casos de prueba

Jack munición
fuente

1

Clojure, 137 bytes

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

Primero divide la entrada en ceros y unos consecutivos y los asigna en "tuplas" del primer elemento de las particiones y el recuento de elementos. Luego repite el número necesario de ceros o unos, dependiendo de si esta es la secuencia de longitud máxima de unos o no.

Menos golfizado:

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

NikoNyrh
fuente

0

Perl 5, 68 bytes

67, más 1 para en -pelugar de-e

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

Espera e imprime una cadena (concatenación) de 0s y 1s.

msh210
fuente

Falsificar verdades breves

De entrada y salida

Detalles

Ejemplos

Respuestas:

Jalea , 8 bytes

Cómo funciona

Haskell, 59 , 58 , 55 , 64 bytes

Nota:

Explicación:

Retina, 47 43 36

Explicación:

MATL, 14 bytes

Python 2, 62 bytes

Cómo funciona

J, 25 bytes

Explicación

Pyth, 26 24 23 21 bytes

Explicación

23 bytes anteriores

24 bytes anteriores

26 bytes anteriores

Oracle SQL 12.1, 137135 bytes

Mathematica , 46 41

C, 135 129 bytes

JavaScript (ES6), 56 bytes

Julia, 51 bytes

Cómo funciona

APL, 22 caracteres

Java 8, 205 bytes

Clojure, 137 bytes

Perl 5, 68 bytes