# Runs of Ones (What Fun!) [duplicate]

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 , the shortest program wins.

• May we input integers and use their binary representation? Also some more test cases in the post would be good. Jul 26, 2022 at 15:44
• You are allowed to use binary representations of integers if you want. Jul 26, 2022 at 15:46
• Is a flat list ([0,0,3,5,8,9] for example) an acceptable output format? Jul 26, 2022 at 17:16
• Since it's unambiguous, I suppose I will allow it. Jul 26, 2022 at 17:21
• Is this related to codegolf.stackexchange.com/questions/69156/…? Jul 26, 2022 at 21:10

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

• It's a great one. But it'll be helpful to explain the mechanic of this complex syntax... ;-) Aug 26, 2022 at 18:30
• @DanielHao I've added a bit of explanation. Aug 26, 2022 at 22:58

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

# 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.  # 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  # 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! # 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  # 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 • What are the instructions for running code at the Replit link? It seems to drop me into a text editor, but it won't let me save and exit so I can run the code I've entered. Jul 26, 2022 at 18:48 • @DLosc I've bound Ctrl-R to run the code, although I just reinstated the Ctrl-Q binding - both should work. Jul 26, 2022 at 18:51 • (Side note, I'll probably figure out a more convenient TIO-style code runner once development of lin stabilizes.) Jul 26, 2022 at 18:52 • Aha! That works. It's an interesting setup... now I'm wondering whether I should do something similar for one or more of my languages that are on Replit. Jul 26, 2022 at 19:08 # 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  # 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 # 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. # 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. # 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.

• Wait what... isn't this question closed as a duplicate? How did you answer this question???? Jul 27, 2022 at 3:25
• @AidenChow If you've started answering a question before it gets closed then apparently you've got a fairly long grace period for you to complete your answer. (I was waiting for the OP to reply to a comment, but I've given up waiting.)
– Neil
Jul 27, 2022 at 7:03