Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Challenge:

Write a function or program that accepts a list of boolean values and returns all of the ranges of True's.

Test Cases:

f [F]                               = []
f [T]                               = [[0,0]]
f [T,T,F,T]                         = [[0,1],[3,3]]
f [F,T,T,F,F,T,T,T]                 = [[1,2],[5,7]]
f [F,T,T,F,F,F,T,T,T,T]             = [[1,2],[6,9]]
f [T,T,F,F,F,T,T,T,T,T,T,T,T,T,T,F] = [[0,1],[5,14]]
f [F,F,T,T,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T] = [[2,3],[12,19],[33,54],[93,94]]

Rules:

  • You may choose how input is encoded, e.g. a list, array, string, etc.
  • The output must be encoded as a list-like of list-likes or a string showing such, so arrays, lists, tuples, matrices, vectors, etc.
  • The boolean values must be encoded as constants, but otherwise any simple conversion of T/F to desired constants is allowed
  • EDIT: eval or similar during runtime IS allowed.
  • Don't to forget to explain how input is passed to the program/function and give its input/output for the test cases
  • Conversion to desired input format not counted
  • Standard loopholes are disallowed
  • If your language has a function to do this, it's not allowed
  • I will not accept my own submission
  • EDIT: Output format is flexible. If not printing a list or similar, range values must be separated by one non-numeric character and separate ranges as well.

Scoring:

  • Score is in bytes, unless unfit to your language (such as codels in Piet)
  • Lowest score wins

There's a good bit of flexibility in input and output, but solutions where T/F are replaced with functions that do all the work are disallowed.

Debugging:

If you write yours in Haskell or can call it from Haskell, the following will check your function/program:

import Test.QuickCheck

tf = cycle [True,False]
gen l = foldl (++) [] $ map (\i -> [tf!!i | x<-[1..i]]) l
putIn (a,b) l = zipWith (||) l [(a <= p) && (p <= b) | p <- [0..length l]]
putAllIn rs len = foldr putIn [False|i<-[1..len]] rs
main = print $ quickCheck (check functionNameGoesHere)
share|improve this question
1  
I may be missing something, but I don't see a description of how a range is represented in the output. – Peter Taylor Jan 11 at 18:53
1  
Can the output be 1-indexed? – LegionMammal978 Jan 11 at 22:59
    
Can the ranges be half-exclusive? – lirtosiast Jan 12 at 0:58
1  
@LegionMammal978 Only if your language default is 1-indexed, for example Mathematica – Michael Klein Jan 12 at 1:00
    
@ThomasKwa Nope, that seems too different for "edge" cases – Michael Klein Jan 12 at 1:03

22 Answers 22

up vote 7 down vote accepted

Pyth, 17 16 bytes

fT.b*Y,~+ZNtZrQ8

Uses some fancy post-assign counter magic together with run length encoding.

Takes input as an array of 0s and 1s, e.g. [1, 1, 0, 1, 0]. Outputs like in the challenge, e.g. [[0, 1], [3, 3]].

Test Suite

share|improve this answer
    
I added a test suite. If the edit is approved and no one snipes, you have the shortest valid answer. – Michael Klein Jan 14 at 19:42

Pyth, 18 bytes

CxR.:++~Zkz02_B_`T

Test suite

True is represented as 1, False as 0.

Ranges are represented inclusively.

share|improve this answer
    
Can you add an explanation? – lirtosiast Jan 12 at 22:47
    
Sure, sometime else. – isaacg Jan 12 at 22:49

Retina, 82 34 27 bytes

\b(?<=(.)*_?)
$#1
_+

S_`:

The empty line should contain a single space.

Input is a flat string of _ for true and : for false. Output is space-separated pairs, each on a separate line.

Try it online.

Explanation

The heavy golfing from 82 down to 27 bytes was possible by clever choice of the representation of true and false. I've picked a word character, _, (that isn't a digit) for true and a non-word character, :, (that doesn't need escaping) for false. That allows me to detect the ends of ranges as word boundaries.

\b(?<=(.)*_?)
$#1

We match a word boundary. We want to replace that boundary with the corresponding index of the truthy value. In principle that is quite easy with Retina's recent $# feature, which counts the number of captures of a group. We simply capture each character in front of that position into a group. By counting those characters we get the position. The only catch is that the ends of the range are off by one now. We actually want the index of the character in front the match. That is also easily fixed by optionally matching a _ which isn't captured, thereby skipping one character when we're at the end of a range.

_+
<space>

Now we replace all runs of underscores with a space. That is, we insert a space between the beginning and end of each range, while getting rid of the underscores.

S_`:

That leaves the colons (and we still need to separate pairs). We do that by splitting the entire string into lines around each colon. The S actives split mode, and the _ suppresses empty segments such that don't get tons of empty lines when we have runs of colons.

share|improve this answer

MATL, 17 18 20 bytes

j'T+'1X32X34$2#XX

Uses current version (9.1.0) of the language/compiler.

Input is a string containing characters T and F. Output is a two-row table, where each column indicates a range using 1-indexing, which is the language default.

Thanks to Stewie Griffin for removing 2 bytes.

Example

>> matl
 > j'T+'1X32X34$2#XX
 >
> FTTFFFTTTT
2 7
3 10

Explanation

It's based on a simple regular expression:

j         % input string
'T+'      % regular expression: match one or more `T` in a row
1X3       % predefined string literal: 'start'
2X3       % predefined string literal: 'end'
4$2#XX    % regexp with 4 inputs (all the above) and 2 outputs (start and end indices)
          % implicitly display start and end indices
share|improve this answer

Octave, 43 Bytes

@(x)reshape(find(diff([0,x,0])),2,[])-[1;2]

find(diff([0,x,0])) finds all the positions where the input array changes between true and false. By reshaping this into a 2-by-n matrix we achieve two things: The changes from true to false, and from false to true are divided into two rows. This makes it possible to subtract 1 and 2 from each of those rows. Subtracting 1 from row one is necessary because Octave is 1-indexed, not zero-indexed. Subtracting 2 from row two is necessary because the find(diff()) finds the position of the first false value, while we want the last true value. The subtraction part is only possible in Octave, not in MATLAB.

F=0;T=1;
x=[F,F,T,T,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T]

reshape(find(diff([0,x,0])),2,[])-[1;2]
ans =    
    2   12   33   93
    3   19   54   94

x=[T,T,F,F,F,T,T,T,T,T,T,T,T,T,T,F]
reshape(find(diff([0,x,0])),2,[])-[1;2]
ans =    
    0    5
    1   14
share|improve this answer
1  
Nice use of broadcasting! – Luis Mendo Jan 11 at 22:18

CJam, 27 25 bytes

0qe`{~~{+}{1$+:X(]pX}?}/;

Expects input like TTFTFT. Try it online.

Explanation

0                               Push 0, to kick off index
qe`                             Push input and run length encode
                                e.g. FFFFTTTFT -> [[4 'F] [3 'T] [1 'F] [1 'T]]
{                 }/            For each pair in the RLE...
 ~                                Unwrap the pair
  ~                               Evaluate T -> 0 (falsy), F -> 15 (truthy)
   { }{         }?                 Ternary based on T/F
    +                                If 'F: add count to index
       1$+:X(]pX                     If 'T: output inclusive range, updating index
;                               Discard the remaining index at the top of the stack
share|improve this answer

Japt, 34 31 25 bytes

Trying a new approach really worked out this time.

V=[]Ur"T+"@Vp[YY-1+Xl]};V

Try it online!

Input is an string with F for false and T for true. Output is an array of arrays; the string representation makes it look like a single array.

How it works

          // Implicit: U = input string
V=[]      // Set V to an empty array. (Why don't I have a variable pre-defined to this? :P)
Ur"T+"    // Take each group of one or more "T"s in the input,
@         // and map each matched string X and its index Y to:
Vp[       //  Push the following to an array in V:
Y         //   Y,
Y-1+Xl    //   Y - 1 + X.length.
]};       //  This pushes the inclusive start and end of the string to V.
V         // Implicit: output last expression

Note: I now see that several people had already come up with this algorithm, but I discovered it independently.

Non-competing version, 22 bytes

;Ur"T+"@Ap[YY-1+Xl]};A

In the latest GitHub commit, I've added a new feature: a leading ; sets the variables A-J,L to different values. A is set to an empty array, thus eliminating the need to create it manually.

share|improve this answer

Python 2, 69 bytes

p=i=0
for x in input()+[0]:
 if x-p:b=x<p;print`i-b`+';'*b,
 p=x;i+=1

Example output:

2 3; 7 16; 18 18;

A direct approach, no built-ins. Tracks the current value x and the previous value p. When these are different, we've switched runs. On switching 0 to 1, prints the current index i. On switching 1 to 0, prints the current index minus one followed by a semicolon.

The if is pretty smelly. Maybe recursion would be better,

share|improve this answer

Haskell, 74 bytes

import Data.Lists
map(\l->(fst$l!!0,fst$last l)).wordsBy(not.snd).zip[0..]

Usage example: map(\l->(fst$l!!0,fst$last l)).wordsBy(not.snd).zip[0..] $ [True,False,True,True,False] -> [(0,0),(2,3)].

How it works:

                               -- example input: [True,False,True,True,False]

zip[0..]                       -- pair each element of the input with it's index
                               -- -> [(0,True),(1,False),(2,True),(3,True),(4,False)]
wordsBy(not.snd)               -- split at "False" values into a list of lists
                               -- -> [[(0,True)],[(2,True),(3,True)]]
map                            -- for every element of this list
   (\l->(fst$l!!0,fst$last l)) -- take the first element of the first pair and the
                               -- first element of the last pair
                               -- -> [(0,0),(2,3)]
share|improve this answer

J, 26 bytes

[:I.&.|:3(<`[/,]`>/)\0,,&0

This is an unnamed monadic verb (unary function) that returns a 2D array or integers. It is used as follows.

  f =: [:I.&.|:3(<`[/,]`>/)\0,,&0
  f 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0
0  1
5 14

Explanation

[:I.&.|:3(<`[/,]`>/)\0,,&0
                       ,&0  Append 0 to input
                     0,     then prepend 0.
        3(         )\       For each 3-element sublist (a b c):
               ]`>/           Compute b>c
          <`[/                Compute a<b
              ,               Concatenate them
                            Now we have a 2D array with 1's on left (right) column
                            indicating starts (ends) or 1-runs.
[:I.&.|:                    Transpose, get indices of 1's on each row, transpose back.
share|improve this answer

Ruby, 39

->s{s.scan(/T+/){p$`.size..s=~/.#$'$/}}

Sample invocation:

2.2.3 :266 > f=->s{s.scan(/T+/){p$`.size..s=~/.#$'$/}}
 => #<Proc:0x007fe8c5b4a2e8@(irb):266 (lambda)> 
2.2.3 :267 > f["TTFTTFTTTFT"]
0..1
3..4
6..8
10..10

The .. is how Ruby represents inclusive ranges.

The one interesting thing here is how I get the index of the end of the range. It's weird. I dynamically create a regular expression that matches the last character of the range, and then all subsequent characters and the end of the string in order to force the correct match. Then I use =~ to get the index of that regex in the original string.

Suspect there might be a shorter way to do this in Ruby using the -naF flags.

share|improve this answer

JavaScript (ES6), 59

An anonymous function, input as a string of T and F, returning output as an array of arrays

x=>x.replace(/T+/g,(a,i)=>o.push([i,a.length+i-1]),o=[])&&o

TEST

f=x=>x.replace(/T+/g,(a,i)=>o.push([i,a.length+i-1]),o=[])&&o

// TEST

arrayOut=a=>`[${a.map(e=>e.map?arrayOut(e):e).join`,`}]`

console.log=x=>O.textContent+=x+'\n'

;[
  'F','T','TTFT','FTTFFTTT','FTTFFFTTTT','TTFFFTTTTTTTTTTF',
  'FFTTFFFFFFFFTTTTTTTTFFFFFFFFFFFFFTTTTTTTTTTTTTTTTTTTTTTFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFTT'
].forEach(t=>console.log(t+'\n'+arrayOut(f(t))+'\n'))
<pre id=O></pre>

share|improve this answer
    
Wow, I just came up with the same solution in Japt and was about to translate it to JS. Nice one :) – ETHproductions Jan 12 at 3:05

𝔼𝕊𝕄𝕚𝕟, 18 chars / 28 bytes

ïħ`T+`,↪ᵖ[_,$Ꝉ+‡_]

Try it here (Firefox only).

Explanation

ïħ`T+`,↪ᵖ[_,$Ꝉ+‡_] // implicit: ï=input
ïħ`T+`,            // for each T-sequence...
       ↪ᵖ[_,$Ꝉ+‡_] // push [start index of sequence, end index of sequence] to the stack
                   // implicit stack output
share|improve this answer

Haskell, 62 bytes

f l|s<-zip3[0..](0:l)$l++[0]=zip[i|(i,0,1)<-s][i-1|(i,1,0)<-s]

Takes as input a list of 0's and 1's.

Given the list l, pads it with 0 on both sides and computes the indexed list of consecutive pairs. For example

l = [1,1,0]
s = [(0,0,1),(1,1,1),(2,1,0),(3,0,0)]

Then, extract the indices corresponding to consecutive elements (0,1) and (1,0), which are the starts of blocks of 0 and 1, subtracting 1 from the starts of 0 to get the ends of 1, and zips the results.

share|improve this answer
    
Wow, that bends syntax more than I thought Haskell would take. Is it equivalent to "f l=let s=zip3[0..](0:l)(l++[0]) in zip[i|(i,0,1)<-s][i-1|(i,1,0)<-s]"? – Michael Klein Jan 12 at 5:02
1  
@MichaelKlein Yes, I learned of the trick of binding in guards from nimi here. It's also equivalent to the longer binding-via-lambda f l=(\s->zip[i|(i,0,1)<-s][i-1|(i,1,0)<-s])$zip3[0..](0:l)$l++[0]. – xnor Jan 12 at 5:05

Pyth, 19 18 bytes

m-VdU2cx1aV+ZQ+QZ2

Explanation:

             implicit: Q=input
m            map lambda d:
  -V         Vectorized subtraction by [0,1]
     d
     U2     
c            split every 2 elements
  x            find all indexes of
    1          1s
    aV         in vectorized xor:
       +ZQ     Q with a 0 on the front
       +QZ     Q with a 0 on the end
  2

Try it here.

share|improve this answer

Perl, 47 bytes

s/F*(T*)(T)F*/[$-[0],$+[1]],/g;chop$_;$_="[$_]"

With the following perlrun options -lpe:

$ perl -lpe's/F*(T*)(T)F*/[$-[0],$+[1]],/g;chop$_;$_="[$_]"' <<< 'TTFFFTTTTTTTTTTF'
[[0,1],[5,14]]

Alternative where output is line separated (34 bytes):

$ perl -pE's/F*(T*)(T)F*/$-[0] $+[1]\n/g;chomp' <<< TTFFFTTTTTTTTTTF
0 1
5 15
share|improve this answer

Python 2, 108 bytes

l=input();l+=[0];o=[];s=k=0
for i,j in enumerate(l):s=j*~k*i or s;~j*l[i-1]and o.append([s,i-1]);k=j
print o

Test cases:

$ python2 rangesinlists2.py
[0]
[]
$ python2 rangesinlists2.py
[-1]
[[0, 0]]
$ python2 rangesinlists2.py
[-1,-1,0,-1]
[[0, 1], [3, 3]]
$ python2 rangesinlists2.py
[0,-1,-1,0,0,-1,-1,-1]
[[1, 2], [5, 7]]
$ python2 rangesinlists2.py
[0,-1,-1,0,0,0,-1,-1,-1,-1]
[[1, 2], [6, 9]]
$ python2 rangesinlists2.py
[-1,-1,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0]
[[0, 1], [5, 14]]
$ python2 rangesinlists2.py
[0,0,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1]
[[2, 3], [12, 19], [33, 54], [93, 94]]

Surely there's a shorter solution than this, but it works.

share|improve this answer

Haskell: 123 bytes (Example, cannot win)

f l=[(s,e)|let m=length l-1,let r=[0..m],s<-r,e<-r,and[l!!x|x<-[s..e]],s<=e,let(#)p=not$l!!p,s==0||(#)(s-1),e==m||(#)(e+1)]

Less golfed:

f l = [(start,end) | start <- [0..max], end <- [0..max], allTrue start end, start <= end, notBelow start, notAbove end]
  where
    max = (length l) - 1
    allTrue s e = and (subList s e)
    subList s e = [l !! i | i <- [s,e]]
    notBelow  s = (s == 0) || (not (l !! (s-1)))
    notAbove  e = (s == m) || (not (l !! (e+1)))
share|improve this answer
    
Even when not golfing: allTrue s e = and (subList s e) or maybe allTrue = (and.) . sublist. – nimi Jan 11 at 21:55
    
Ok, for a reason I don't remember, I thought that was more "clear" when I was ungolfing... (Edited) – Michael Klein Jan 11 at 21:59
1  
Oh, sure, opinions differ on what's "clear". I also think all (==True) (subList s e) is very clear. – nimi Jan 11 at 22:05

CJam, 30 bytes

0l~0++2ewee{1=$2,=},{~0=-}%2/`

Input as a CJam-style array of 0s and 1s. Output as a CJam-style array of pairs.

Run all test cases. (Takes care of the conversion of the input formats.)

share|improve this answer

Japt, 27 bytes

A=[];Ur"T+"@Ap[YXl +´Y]};A·

There has to be a way to golf this down...

Anyway, it's the same as my 𝔼𝕊𝕄𝕚𝕟 answer.

share|improve this answer
    
Wow, I just came up with this solution myself.... Nice algorithm! – ETHproductions Jan 12 at 3:07

PowerShell, 82 bytes

("$args"|sls 't+'-A).Matches|%{if($_){'{0},{1}'-f$_.Index,($_.Index+$_.Length-1)}}

Regex solution, using MatchInfo object's properties.

Example

PS > .\BoolRange.ps1 'F'


PS > .\BoolRange.ps1 'T'
0,0

PS > .\BoolRange.ps1 'TTFFFTTTTTTTTTTF'
0,1
5,14
share|improve this answer

Mathematica, 45 bytes

SequencePosition[#,{True..},Overlaps->False]&

Not particularly interesting; uses a builtin.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.