Runs of Ones (What Fun!)

code-golf sequence

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 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. Here's a program to generate test cases.

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

Sandbox Questions

This is a simplification of the previous question I proposed, which I decided to make a new post in order to get fresh eyes on it. The title is a bit iffy, but I don't know how much that matters.

I could also make the challenge harder by instead having the input be a list with an arbitrary number of fixed symbols along with symbol x, and ask for all start and end indices of all instances of x in list -- e.g. f([c,a,b,c,c],c) returns the indices of runs of c. However, I think the problem as described above gives more opportunity for cleverness in solutions.

Runs of Ones (What Fun!)

Runs of Ones (What Fun!)

code-golf sequence

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 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. Here's a program to generate test cases.

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

Sandbox Questions

This is a simplification of the previous question I proposed, which I decided to make a new post in order to get fresh eyes on it. The title is a bit iffy, but I don't know how much that matters.

I could also make the challenge harder by instead having the input be a list with an arbitrary number of fixed symbols along with symbol x, and ask for all start and end indices of all instances of x in list -- e.g. f([c,a,b,c,c],c) returns the indices of runs of c. However, I think the problem as described above gives more opportunity for cleverness in solutions.

Runs of Ones (What Fun!)

code-golf sequence

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 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. Here's a program to generate test cases.

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

Sandbox Questions

This is a simplification of the previous question I proposed, which I decided to make a new post in order to get fresh eyes on it. The title is a bit iffy, but I don't know how much that matters.

I could also make the challenge harder by instead having the input be a list with an arbitrary number of fixed symbols along with symbol x, and ask for all start and end indices of all instances of x in list -- e.g. f([c,a,b,c,c],c) returns the indices of runs of c. However, I think the problem as described above gives more opportunity for cleverness in solutions.

Runs of Ones (What Fun!)

code-golf sequence

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, ...a_n]\$ consisting of two distinct values \$x\$ and \$y\$, output all tuples of indices \$(i,j)\$ where the values in the subsequence \$[a_i,...,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. Here's a program to generate test cases.

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

Sandbox Questions

This is a simplification of the previous question I proposed, which I decided to make a new post in order to get fresh eyes on it. The title is a bit iffy, but I don't know how much that matters.

I could also make the challenge harder by instead having the input be a list with an arbitrary number of fixed symbols along with symbol x, and ask for all start and end indices of all instances of x in list -- e.g. f([c,a,b,c,c],c) returns the indices of runs of c. However, I think the problem as described above gives more opportunity for cleverness in solutions.

Runs of Ones (What Fun!)

code-golf sequence

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 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. Here's a program to generate test cases.

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

Sandbox Questions

This is a simplification of the previous question I proposed, which I decided to make a new post in order to get fresh eyes on it. The title is a bit iffy, but I don't know how much that matters.

I could also make the challenge harder by instead having the input be a list with an arbitrary number of fixed symbols along with symbol x, and ask for all start and end indices of all instances of x in list -- e.g. f([c,a,b,c,c],c) returns the indices of runs of c. However, I think the problem as described above gives more opportunity for cleverness in solutions.