Falsifier de brèves vérités

28

Trouvez la plus longue série de true dans une liste de booléens. Renvoie la même liste, avec toutes les autres vérités falsifiées.

Entrée sortie

Une liste; tout format habituel (par exemple, une liste délimitée sous forme de chaîne).

Détails

Vrai et faux peuvent être tout ce que votre langue utilise généralement pour ces valeurs, ou les entiers 1 et 0. Si vous utilisez des caractères uniques, la liste peut être une concaténation (par exemple, 10001).

S'il y a une égalité pour la course la plus longue, gardez toutes les courses égales vraies et falsifiez toutes les courses plus courtes.

Exemples

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

(directement depuis /programming//q/37447114 )

msh210
la source

Réponses:

19

Gelée , 8 octets

ṣ0¬¬M¦j0

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça marche

ṣ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
la source
23
Jeez ... cette langue ...
AdmBorkBork
11

Haskell, 59 , 58 , 55 , 64 octets

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

Note amusante, cela fonctionne sur n'importe quelle liste de valeurs où falsy < truthy. Alors False/True, 0/1,'f'/'t' , etc.

Remarque:

Comme plusieurs personnes l'ont souligné (y compris @proud haskelleret @nimi), la version précédente a échoué sur une liste de toutes les valeurs de falsification. L'ajout de .([1<2]:)a corrigé cela, comme suggéré par @proud haskeller. Je laisse l'explication la même pour l'instant, car je pense que cela a toujours du sens. Si quelqu'un commente et demande une explication de la modification, je la modifierai.

Explication:

Je vais d'abord désugar sans le group, puis l'ajouter à nouveau. Tout d'abord, je trouve que les mots sont souvent plus agréables aux yeux que les symboles, donc je vais faire quelques substitutions. (Notez que =<<c'est «chic», donc cela s'applique différemment pour les listes et les fonctions. J'appelle bindla version de =<<pour les fonctions.)

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)

Les derniers détails sont ceux qui x <$ listremplacent chaque élément du listavec xet group listdivisent le listhaut en morceaux d'éléments égaux. Alors group [1, 1, 2, 3, 3, 3] == [[1, 1], [2], [3, 3, 3]].

Pour résumer le tout, la fonction divise la liste de valeurs en groupes de seulement vrai et groupes de seulement faux. Ensuite, pour chaque groupe, remplacez chaque élément par le résultat de la déclaration this is the biggest group(le plus grand groupe de truesera le plus grand) et concaténez les groupes.

Quatre octets enregistrés par @Zgarb

Michael Klein
la source
1
Je pense que vous pouvez remplacer (\y->(maximum g==y)<$y)par ((<$)=<<(==maximum g)). Je ne l'ai pas testé cependant.
Zgarb
@Zgarb Je viens de le résoudre à partir de la déclaration d'instance et cela fonctionne. Merci.
Michael Klein
3
Encore mieux: remplacez toute la définition de fpar la fonction sans point ((=<<)=<<(=<<)(<$).(==).maximum).group. Enregistre trois octets et est totalement illisible!
Zgarb
@Zgarb: Cool! À ce stade, b=(=<<);b b(b(<$).(==).maximum).groupest encore un octet plus court. Je n'ai jamais rien vu de tel auparavant au golf Haskell :)
Lynn
1
Si je ne me trompe pas, vous pouvez le corriger en insérant (:[t])avant le maximum ou quelque chose de similaire
fier haskeller
6

Rétine, 47 43 36

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

Essayez-le en ligne! ou essayez tous les cas de test

Merci à msh210 pour avoir joué au golf 4 octets!

Un grand merci également à Martin pour 7 octets!

Explication:

0
!

Remplacez tous les 0s par !s. Ceci est fait pour 1raccourcir les groupes de s correspondants , comme maintenant 1!et !1aura une limite de mot ( \b) entre eux, qui correspond également au début ou à la fin de la chaîne.

T`p`0`

Il s'agit d'une option de configuration indiquant qu'après avoir appliqué l'expression régulière après le backtick à l'entrée, dans chaque correspondance, traduire chaque caractère ascii imprimable en un 0caractère.

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

Cette expression régulière correspond à des groupes de 1s qui sont entourés de zéros, mais ne peut correspondre à un 1suivi de lui-même nulle part dans la chaîne. Ce sont les groupes non maximaux qui seront falsifiés. De plus, cela correspond également aux !caractères que nous avons ajoutés pour les reconvertir en 0s.

FryAmTheEggman
la source
5

MATL, 14 octets

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

Essayez-le en ligne!

Version modifiée avec tous les cas de test

Explication

        % 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
la source
4

Python 2, 62 octets

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

Testez-le sur Ideone .

Comment ça marche

s.split('0')divise la chaîne d'entrée est en courses de zéro ou plus 1 « s

Pour chaque exécution t , nous vérifions si t+'1'est une sous-chaîne de s .

  • Si c'est le cas, la course n'est pas maximale, t+'1'in sretourne True , 1-(t+'1'in s)retourne 1 - True = 0 et la course est remplacée par une course de 0 de même longueur.

  • Si ce n'est pas le cas, la course est maximale, t+'1'in sretourne False , 1-(t+'1'in s)retourne 1 - False = 1 et la course est remplacée par une course de 1 de même longueur, c'est-à-dire par elle-même.

Enfin, '0'.joinrestaure tous les 0 supprimés .

Dennis
la source
3

J, 25 octets

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

Il s'agit d'un verbe monadique qui prend et renvoie un tableau 0-1. Utilisez-le comme ceci:

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

Explication

[:(}.=>./)@;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
la source
Belle utilisation de coupe ;..
miles
3

Pyth, 26 24 23 21 octets

M,G&HGJrgMrQ8 9qReSJJ

Suite de tests.

  • Utilise 1/0ou true/falseen entrée.
  • Utilise true/falseen sortie.

Explication

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

Précédent 23 octets

M,G&HGJrgMrQ8 9msqdeSJJ

Suite de tests.

  • Utilise 1/0ou true/falseen entrée.
  • Utilise 1/0en sortie.

Précédent 24 octets

Jrm,hd&edhdrQ8 9msqdeSJJ

Suite de tests.

  • Utilise 1/0ou true/falseen entrée.
  • Utilise 1/0en sortie.

26 octets précédents

rm?nhdeS.u&YhNQ0,hd0drQ8 9

Suite de tests.

  • Utilise 1/0ou true/falseen entrée.
  • Utilise 1/0en sortie.
Leaky Nun
la source
La création d'une fonction qui n'est appelée qu'à un seul emplacement est presque toujours une erreur. Vous pouvez par exemple le remplacer par: Jr.b,N&YNrQ8)9qReSJJou Jrm,hd*FdrQ8 9qReSJJ. Les deux versions économisent un octet. Ou allez encore plus fou avec JrXR1*FdrQ8 9qReSJJet économisez deux. ;-)
Jakube
2

Oracle SQL 12.1, 137 135 octets

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

Non 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 saisie utilise des caractères uniques. Ex: '1100111'

Jeto
la source
2

Mathematica , 46 41

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

Fonctionne sur les listes de 0et 1. Je pensais avoir assez bien réussi jusqu'à ce que je regarde les autres réponses!


Explication pour la version à 46 caractères; Je mettrai à jour quand je ne peux pas l'améliorer davantage.

Une explication de ce code a été demandée.
Un équivalent sans code-golf (en utilisant les formulaires d'opérateur de la version 10) est:

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

Cela signifie une fonction composée de cinq étapes (sous-fonctions) appliquées dans l'ordre de haut en bas.

  • Split: décompose en séries d'éléments identiques: {1,1,0,1,1,0,1} ↦ {{1,1}, {0}, {1,1}, {0,0}}

  • Map[# Tr@# &]: Pour chaque sous-liste ( Map) multipliez-la ( #) par sa somme (trace vectorielle, Tr): {1,1} ↦ {2, 2}

  • # - Max[1, #] &soustrayez de chaque élément la valeur maximale apparaissant n'importe où dans la liste des listes, ou une, la plus élevée des deux. (L'un gère le cas de tous les zéros.)

  • UnitStep: égal à 0 pour x <0 et 1 pour x> = 0, appliqué à chaque élément.

  • Apply[Join]: joindre les sous-listes en une seule liste. Pourrait également être fait avec Flattenou Catenate, mais en bref, il Join@@est plus concis.

Mr.Wizard
la source
2

C, 135 129 octets

Essayez en ligne

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

Non 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
la source
1

JavaScript (ES6), 56 octets

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

Fonctionne en vérifiant toutes les séries de 1 et en remplaçant les caractères par 0 à moins que la série ne soit (également) la plus longue, comme mesuré en recherchant dans la chaîne une série plus longue de 1.

Solution récursive précédente de 72 octets:

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

Ne fait rien s'il n'y a pas d'exécutions de 1 (c.-à-d. 1 seul maximum). Sinon, soustrayez-en un 1à chacun 1ou à l' un d'eux , puis appelez-le récursivement sur les cycles les plus courts, puis ajoutez-en un 1aux cycles (désormais tout aussi longs). Le nombre d'appels récursifs est inférieur de un à la durée de la plus longue exécution.

Neil
la source
"Dans toutes les séries de 1, remplacez chaque 1 par 0 s'il existe une série de 1 plus longue que la série actuelle, sinon remplacez par 0." Brillant!
Patrick Roberts
1

Julia, 51 octets

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

Essayez-le en ligne!

Comment ça marche

replacetrouve toutes les exécutions d'un ou plusieurs 1 dans la chaîne d'entrée s via l'expression régulièrer"1+" et appelle le lambda t->map(c->c-contains(s,"1"t),t)pour déterminer la chaîne de remplacement.

Le lambda mappe c->c-contains(s,"1"t)tous les caractères dans la course de ceux t .

  • Si "1"t(concaténation) est une sous-chaîne de s , la course n'est pas maximale, containsretourne vrai et c-contains(s,"1"t)retourne '1' - vrai = '0' , en remplaçant tous les 1 de cette course par 0 .

  • Si "1"t(concaténation) n'est pas une sous-chaîne de s , l'exécution est maximale, containsrenvoie faux et c-contains(s,"1"t)renvoie «1» - faux = «1» , laissant l'exécution non modifiée.

Dennis
la source
1

APL, 22 caractères

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

En anglais (de droite à gauche en blocs):

  • ajouter 0 à l'entrée
  • case commençant par chaque 0
  • multiplier chaque case par sa somme
  • aplatir
  • 1 si nombre égal au max, 0 sinon
lstefano
la source
1

Java 8, 205 octets

Il s'agit d'une expression lambda pour 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;}

entrée / sortie est un String où true est représenté par 1 et false est représenté par 0. Aucun délimiteur ne sépare les valeurs.

code avec explication:

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

voir ideone pour les cas de test

Jack Ammo
la source
1

Clojure, 137 octets

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

Commence par partitionner l'entrée en zéros et uns consécutifs et les mappe en «tuples» du premier élément des partitions et du nombre d'éléments. Il répète ensuite le nombre nécessaire de zéros ou de uns, selon qu'il s'agit de la séquence de longueur maximale de uns ou non.

Moins golfé:

(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
la source
0

Perl 5, 68 octets

67, plus 1 pour -peau lieu de-e

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

Attend et imprime une chaîne (concaténation) de 0 et de 1.

msh210
la source