28
\$\begingroup\$

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)
\$\endgroup\$
6
  • 1
    \$\begingroup\$ I may be missing something, but I don't see a description of how a range is represented in the output. \$\endgroup\$ – Peter Taylor Jan 11 '16 at 18:53
  • 1
    \$\begingroup\$ Can the output be 1-indexed? \$\endgroup\$ – LegionMammal978 Jan 11 '16 at 22:59
  • \$\begingroup\$ Can the ranges be half-exclusive? \$\endgroup\$ – lirtosiast Jan 12 '16 at 0:58
  • 1
    \$\begingroup\$ @LegionMammal978 Only if your language default is 1-indexed, for example Mathematica \$\endgroup\$ – Michael Klein Jan 12 '16 at 1:00
  • \$\begingroup\$ @ThomasKwa Nope, that seems too different for "edge" cases \$\endgroup\$ – Michael Klein Jan 12 '16 at 1:03

32 Answers 32

1
2
0
\$\begingroup\$

Jelly, 13 bytes

TI’kƊ.ịⱮ$ḢẠ?U

Try it online!

+4 bytes to handle the all 0s test cases. Without that, a much cleaner 9 bytes. This uses 1 indexing, which is Jelly's default.

How it works

TI’kƊ.ịⱮ$ḢẠ?U - Main link
T             - Indices of truthy elements
    Ɗ         - Group the previous links into a monad f(T):
 I            -   Increments
  ’           -   Decrement
   k          -   Partition T at truthy indexes in the decremented increments

                This returns [[]] for [0] (and repeats) and
                [[a, b], [c, d, e], ...] for every other input

           ?  - If:
          Ạ   -   Condition: All truthy?
        $     -   If:
       Ɱ      -     For each partition:
     .ị       -       Take the 0.5th element
         Ḣ    -   Else: Return []

                For non-integer left argument, x, Jelly's ị atom takes
                floor(x) and ceil(x) and returns [floor(x)ịy, ceil(x)ịy]
                As Jelly's indexing is 1-based and modular:
                  0ị returns the last element
                  1ị returns the first element
                  .ị returns [0ị, 1ị]

            U - Reverse, as the ranges yielded by .ị are "reversed"
\$\endgroup\$
0
\$\begingroup\$

Java (JDK), 181 169 121

a->{int f=-1,p=0;for(int c:a.toCharArray()){if(c<49&f>=0){System.out.println(f+","+~-p);f=-1;}f=c>48&f<0?p:f;p++;}};

Execute:

java T 1100011111111110

Output:

0,1
5,14

Try it online!

Explained

  int f=-1,                               // index of first '1' of current range
      p=0;                                // current position in the input array
  for(int c:a[0].toCharArray()){          // loop over the input from the command line (int & char are exchangeable here
    if(c<49&f>=0){                        // 48='0'; current=0 and we had a '1' range 
      System.out.println(f+","+~-p);      // print first and current-1
      f=-1;                               // we are no longer in a 1 range
    }  
    f=c>48&f<0?                           // 49='1'; if current='1' and is first of new range, 
        p                                 // let f start here
        :f                                // otherwise f unchanged
    p++;                                  // increase current index counter
  }                                       // end of for loop
};                                        // end of function

Edits:

181 -> 169 : interface instead of class; f==-1 -> f<0

169 -> 121 : added suggestions of @ceilingcat and reduced it to a function

121 -> 116 : small, nice improvements, thanks @ceilingcat

\$\endgroup\$
0
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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