Runs of Ones (What Fun!) [duplicate]

Question

Suppose you have an array with some known set of values (e.g. a string of \$0\$ and \$1\$) and you want to get all the locations of \$1\$s. Instead of storing a list of all the indices, if the \$1\$s come in "clumps" you can sometimes save space by storing starting and ending indices of "runs" of values -- i.e. substrings which contain just a bunch of \$1\$s in a row. For example, take the following list:

i =  0 1 2 3 4 5 6 7 8 9 
a = [1 0 0 1 1 1 0 0 1 1]
     ^     ^ ^ ^     ^ ^
i =  0     3 4 5     8 9 

So we output \$[(0,0), (3,5), (8,9)]\$.

More formally: Given an array \$[a_1, \ldots, a_n]\$ consisting of two distinct values \$x\$ and \$y\$, output all tuples of indices \$(i,j)\$ where the values in the contiguous subsequence \$[a_i, \ldots, a_j]\$ are all \$y\$. You must return as few tuples as necessary to cover all \$y\$ in the array -- e.g. in the above example you should not return \$[(0,0), (3,4), (5,5), (8,9)]\$ .

You may use any two distinct values for the input list, and your indices may start from 0 or 1.

Some test cases:

Input	Output
[]	[]
[0]	[]
[1, 1, 1]	[(0, 2)]
[1, 0, 0, 1]	[(0, 0), (3, 3)]
[0, 1, 0, 1]	[(1, 1), (3, 3)]
[1, 0, 0, 1, 1, 1, 0, 0, 1, 1]	[(0,0), (3,5), (8,9)]

Here's a program to generate test cases.

Standard loopholes are forbidden. Since this is code-golf, the shortest program wins.

Answer 1

Python, 57 bytes

lambda L,i=0:[l+j for j,l in enumerate(L+[0])if i^(i:=l)]

Attempt This Online!

Outputs the flattened sequence of endpoints.

How

Loops using the walrus operator to keep a delayed-by-one copy of the current element. xors to detect changes. By pre- and appending a zero it makes sure that an even number of changes starting with an "on"-change are recorded.

Answer 2

R, 52 43 bytes

\(x,r=rle(c(0,x)))if(any(x))cumsum(r$l)-r$v

Attempt This Online!

Outputs a flat vector 1-indexed.

Explanation outline:

1. Take run length encoding of the input with 0 prepended.
2. Cumulative sum of the lengths - these are ends of the runs of zeros and ones.
3. Because we prepended a 0, these are off by one. So actually ends of runs of zeros are starts of runs of ones. And ends of runs of ones are off by one.
4. Correct the above by substracting value of the run.

Answer 3

Vyxal, 9 bytes

aƛ?0pøĖ¦ε

Try it Online!

aƛ?0pøĖ¦ε
a         # Are there any ones in the list?
 ƛ        # Map over a list in the range [1, that]. For 0 this will just be an empty array, otherwise [1].
  ?       #  Push input
   0p     #  Prepend a zero
     øĖ   #  Run-length encode: Push their values and their lengths, separately, each onto the stack.
       ¦  #  Cumulative sum of the lengths
        ε #  For each in that, take the absolute difference of it and its corresponding value.

Returns a singleton list of the list, or in the case of an empty list, an empty list (not [[]]). If that's not allowed:

Vyxal, 10 bytes

a[0pøĖ¦ε|¾

Try it Online!

a[0pøĖ¦ε|¾
a          # Are there any ones in the list?
 [         # If so:
  0p       #  Prepend a zero to the input
    øĖ     #  Run-length encode: Push their values and their lengths, separately, each onto the stack.
      ¦    #  Cumulative sum of the lengths
       ε   #  For each in that, take the absolute difference of it and its corresponding value.
        |  # Otherwise:
         ¾ #  Push an empty list

Other solutions:

Vyxal, 14 bytes

ẏ‡?iḊ'h?i;v₍gG

Try it Online!

ẏ‡?iḊ'h?i;v₍gG
ẏ               # Push a list in the range [0, length)
 ‡  Ḋ           # Adjacent group by:
  ?i            #  Index into the input
     '          # Filter for {when this returns 1}:
      h?i;      #  Index the first item of this list into the input
          v₍gG  # For each, get a list [min, max].

Once a bug is fixed, this will work:

Vyxal, 12 bytes

Ġ?żȮ•*~hv₍gG

Try it online! Includes a workaround that costs 3 bytes.

Ġ?żȮ•*~hv₍gG
Ġ            # Group consecutive identical items into their own list (call this x)
 ?ż          # On the input, get a range [1, length] (call this y)
   Ȯ         # Over, push x again
    •        # Mold y like x
     *       # Vectorizically multiply this by x
     v⟑;     # Bug workaround
      ~h     # Filter for where the first item is not 0
        v₍gG # For each, get a list [min, max]

Vyxal, 11 bytes

k+ƛ?T$Ȯ+F;∩

Try it Online!

Port of Jelly.

k+ƛ?T$Ȯ+F;∩
k+          # Push [1, -1].
  ƛ         # Map over it:
   ?T       #  Get truthy indices in the input (call this X).
     $      #  Swap so the current item (call it Y) is at the top.
      Ȯ     #  Over, push the item next the top item at the stack. Stack: X, Y, X.
       +    #  Vectorizing addition, call this Z.
        F   #  Filter-reject: remove items in X that are in Z.
         ;  # Close map.
          ∩ # Transpose.

Answer 4

Jelly, 8 bytes

Tḟ+¥ⱮØ+Z

A monadic Link that accepts a list and yields a list of start, end pairs of truthy runs (1-indexed).

Try it online!

How?

Tḟ+¥ⱮØ+Z - Link: list, A
T        - Truthy indices of A -> t
     Ø+  - [1,-1]
    Ɱ    - map (for n in [1,-1]) with:
   ¥     -   last two links as a dyad f(t, n):
  +      -     t add n (vectorises)
 ḟ       -     t filter discard those
       Z - transpose

Answer 5

JavaScript (ES6), 55 bytes

Expects a binary string. Returns a space-separated list of comma-separated 0-based indices.

s=>s.replace(/1+|0/g,(s,i)=>+s?[i,i+s.length-1]+' ':'')

Try it online!

Answer 6

Pip -p, 13 bytes

B-%_MEa@*`\b`

Takes a string containing the characters 1 and , as a command-line argument. Outputs a flat list of 0-based indices. Try It Online!

Explanation

B-%_MEa@*`\b`
       @*      Find all indices
      a        in command-line argument
         `\b`  of regex matches of word boundaries
               This gives us the beginning and end of each run of 1s, but the end index
               is one past the final 1 in each run, so:
    ME         Enumerate that list and map this function:
B-               The value minus
  %_             its index mod 2
               I.e., subtract 1 from every second element of the list

Answer 7

lin, 46 bytes

"1+".?g ?M \; `'
"index""0", g:"len over +1-"'

Try it here! Takes string and returns an iterator.

For testing purposes (use -i flag if running locally):

"1001110011" ; `_
"1+".?g ?M \; `'
"index""0", g:"len over +1-"'

Explanation

Prettified code:

"1+".?g ?M \; `'
["index" "0"] g:.( len over + 1- )

• "1+".?g ?M get matches of consecutive 1s
• \; `' map...
  • ["index" "0"] g: keep index and matched 1s from match object
  • .( len over + 1- ) get length of 1s, add index, decrement

Answer 8

Charcoal, 26 bytes

ＩΦＥ⪪θ0∧ι⁺⟦⁰⊖Ｌι⟧⁺Ｌ⪫…⪪θ0κωκι

Try it online! Link is to verbose version of code. Explanation:

    θ                       Input string
   ⪪ 0                      Split on literal string `0`
  Ｅ                         Map over pieces
       ι                    Current piece
      ∧                     Logical And
          ⁰                 Literal integer `0`
             ι              Current piece
            Ｌ               Length
           ⊖                Decremented
         ⟦    ⟧             Make two-element list
        ⁺                   Vectorised plus
                    θ       Input string
                   ⪪ 0      Split on literal string `0`
                  …         Truncated to length
                      κ     Current index
                 ⪫     ω    Joined
                Ｌ           Length
               ⁺            Plus
                        κ   Current index
 Φ                          Filtered where
                         ι  Current piece
Ｉ                           Cast to string
                            Implicitly print

Answer 9

Desmos, 68 bytes

L=join(0,l,0)
g(k)=[0...L.length][L[2...]=L+2k-1]+k
f(l)=(g(1),g(0))

The function \$f\$ returns a list of 1-indexed coordinate pairs. Seems golfable.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 10

C (clang), 83 bytes

c;i;f(*l,n){for(c=i=0;i<=n;++i)l[n-1]*i/n||i-n&&l[i]-c?printf("%d ",i-c,c=l[i]):0;}

Try it online!

Inputs a pointer to an array of \$1\$s and \$0\$s and its length (because pointers in C carry no length info).
Outputs the starting and ending indices of all the runs of consecutive \$1\$s to stdout.

Answer 11

J, 21 bytes

[:]`<:/[email protected]~:/\0,,&0

Try it online!

Returns a column vector.

• 0,,&0 Bookend the input with zeros.
• 2~:/ For every consecutive pair, are they unequal?
• [: ... I. Get the indexes of the ones, that is, the indexes where we transition from a 0 to a 1 or vice-versa. We are almost done now, but our ending indexes are one too high...
• ]`<:/. So we alternately transform each element by the identity ] and decrement <: functions.

The TIO link has a handful of alternate approaches, but this was the shortest I found.

Answer 12

Retina, 25 bytes

L$`(?<!1)1*(?=1)
$.` $.>`

Try it online! Link includes test cases. Explanation: Retina can compute the character index of the start of the match, and Retina 1 can also compute the character index of the end of the match, but unfortunately the question requires inclusive ranges so rather than simply matching 1+ a more complicated regex is required.