Falsify brief truths

Question

Find the longest run of true in a list of booleans. Return the same list, with all other trues falsified.

Input, output

A list; any usual format (e.g., a delimited list as a string).

Details

True and false can be anything your language typically uses for those values, or the integers 1 and 0. If you use single characters, the list can be a concatenation (e.g., 10001).

If there's a tie for longest run, keep all tying runs true, and falsify all shorter runs.

Examples

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

(directly from https://stackoverflow.com/q/37447114)

Answer 1

Jelly, 8 bytes

ṣ0¬¬M¦j0

Try it online! or verify all test cases.

How it works

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

Answer 2

Haskell, 59, 58, 55, 64 bytes

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

Fun note, this works on any list of values where falsy < truthy. So False/True, 0/1, 'f'/'t', etc.

Note:

As several people have pointed out (including @proud haskeller and @nimi), the previous version failed on a list of all falsy values. The addition of .([1<2]:) has fixed this, as suggested by @proud haskeller. I'm leaving the explanation the same for now, because I think it still makes sense. If anyone comments, asking for an explanation of the edit, I'll edit.

Explanation:

I'll first desugar without the group, and then add it back. First, I find that words are often easier on the eyes than symbols, so I'll make a few substitutions. (Note that =<< is 'classy' so it applies differently for lists and functions. I'm calling bind the version of =<< for functions.)

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)

The last details are that x <$ list replaces every element of the list with x and group list splits the list up into chunks of equal elements. So group [1, 1, 2, 3, 3, 3] == [[1, 1], [2], [3, 3, 3]].

To sum it all up, the function splits the list of values into groups of only true and groups of only false. Then for each group, replace each element with the result of the statement this is the biggest group (the largest group of true's will be the biggest) and concatenate the groups.

Four bytes saved by @Zgarb

Answer 3

Retina, 47 43 36

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

Try it online! or try all the test cases

Thanks to msh210 for golfing 4 bytes!

Also big thanks to Martin for 7 bytes!

Explanation:

0
!

Replace all 0s with !s. This is done to make matching groups of 1s shorter, as now 1! and !1 will have a word boundary (\b) between them, which also matches either the start or the end of the string.

T`p`0`

This is a configuration option saying that after applying the regex after the backtick to the input, in every match translate every printable ascii character into a 0 character.

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

This regex matches groups of 1s that are surrounded by zeroes, but do cannot match a 1 followed by itself anywhere in the string. These are the non-maximal groups that will be falsified. In addition, this also matches the ! characters we added to convert them back into 0s.

Answer 4

MATL, 14 bytes

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

Try it Online!

Modified version with all test cases

Explanation

        % 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

Answer 5

Python 2, 62 bytes

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

Test it on Ideone.

How it works

s.split('0') splits the input string s into runs of zero or more 1's

For each run t, we check whether t+'1' is a substring of s.

• If it is, the run isn't maximal, t+'1'in s return True, 1-(t+'1'in s) return 1 - True = 0 and the run is replaced with a run of 0's of the same length.

• If it isn't, the run is maximal, t+'1'in s return False, 1-(t+'1'in s) return 1 - False = 1 and the run is replaced with a run of 1's of the same length, i.e., by itself.

Finally, '0'.join restores all removed 0's.

Answer 6

Pyth, 26 24 23 21 bytes

M,G&HGJrgMrQ8 9qReSJJ

Test suite.

• Uses 1/0 or true/false in input.
• Uses true/false in output.

Explanation

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

Previous 23-byte

M,G&HGJrgMrQ8 9msqdeSJJ

Test suite.

• Uses 1/0 or true/false in input.
• Uses 1/0 in output.

Previous 24-byte

Jrm,hd&edhdrQ8 9msqdeSJJ

Test suite.

• Uses 1/0 or true/false in input.
• Uses 1/0 in output.

Previous 26-byte

rm?nhdeS.u&YhNQ0,hd0drQ8 9

Test suite.

• Uses 1/0 or true/false in input.
• Uses 1/0 in output.

Answer 7

J, 25 bytes

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

This is a monadic verb that takes and returns a 0-1 array. Use it like this:

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

Explanation

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

Answer 8

Mathematica, 46 41

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

Works on lists of 0 and 1. I thought I had done pretty well until I looked at the other answers!

---

Explanation for 46 character version; I shall update when I cannot improve it further.

An explanation of this code was requested.
A non-code-golf equivalent (using version 10 operator forms) is:

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

This means a function made up of five steps (sub-functions) applied in order from top to bottom.

• Split: break up into runs of identical elements: {1,1,0,1,1,0,1} ↦ {{1,1}, {0}, {1,1}, {0,0}}

• Map[# Tr@# &]: For each sub-list (Map) multiply it (#) by its sum (vector trace, Tr): {1,1} ↦ {2, 2}

• # - Max[1, #] & subtract from every element the maximum value appearing anywhere in the list of lists, or one, whichever is higher. (The one handles the case of all zeros.)

• UnitStep: equal to 0 for x < 0 and 1 for x >= 0, applied to every element.

• Apply[Join]: join the sub-lists into a single list. Could also be done with Flatten or Catenate, but in short form Join@@ is more terse.

Answer 9

Oracle SQL 12.1, 137 135 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,"')||'"')));

Un-golfed

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

Input use single characters. Ex: '1100111'

Answer 10

C, 135 129 bytes

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

Ungolfed

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

Answer 11

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

First partitions the input into consecutive zeros and ones and maps these into "tuples" of partitions' first element and the count of elements. It then repeats the needed number of zeros or ones, depending if this is the max-length sequence of ones or not.

Less golfed:

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

Answer 12

JavaScript (ES6), 56 bytes

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

Works by checking all runs of 1s and replacing the characters with 0s unless the run is (equally) longest, as measured by searching the string for a longer run of 1s.

Previous 72-byte recursive solution:

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

Does nothing if there are no runs of 1s (i.e. single 1s at most). Otherwise, subtracts one 1 from each 1 or run thereof, then calls itself recursively on the shorter runs, then adds one 1 back on the (now equally longest) runs. The number of recursive calls is one less than the length of the longest run.

Answer 13

Julia, 51 bytes

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

Try it online!

How it works

replace finds all all runs of one or more 1's in the input string s via the regex r"1+" and calls the lambda t->map(c->c-contains(s,"1"t),t) to determine the replacement string.

The lambda maps c->c-contains(s,"1"t) over all characters in the run of ones t.

• If "1"t (concatenation) is a substring of s, the run isn't maximal, contains returns true and c-contains(s,"1"t) returns '1' - true = '0', replacing all 1's in that run with 0's.

• If "1"t (concatenation) is not a substring of s, the run is maximal, contains returns false and c-contains(s,"1"t) returns '1' - false = '1', leaving the run unmodified.

Answer 14

Java 8, 205 bytes

This is a lambda expression for 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 is a String where true is represented by 1 and false is represented by 0. There are no delimiter characters separating the values.

code with explanation:

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

see ideone for the test cases

Answer 15

APL, 22 chars

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

In English (from right to left in blocks):

• prepend 0 to the input
• box starting with each 0
• multiply each box by its sum
• flatten
• 1 if number equal to the max, 0 otherwise

Answer 16

Perl 5, 68 bytes

67, plus 1 for -pe instead of -e

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

Expects and prints a string (concatenation) of 0s and 1s.