# Question
Title: Encode the systematic binary Varshamov–Tenengolts code
# Background

Here on CGCC, a commonly seen subgenre is – writing a program that works even if one character is deleted. A similar problem is studied in the field of coding theory: finding an encoding that can be decoded even if one symbol is deleted from the encoded string. In this challenge, we're looking at the "binary" variant of the problem: the codes are strings of bits, and the deletions that we're trying to harden against happen at the bit level.

Although the problem of finding the optimal code for handling a single deletion from a string of bits is still not entirely solved, one commonly used code for the purpose is the Varshamov–Tenengolts code (typically called the "VT code" for short); this code has the property that for every encoded codeword, the sum of the 1-based indexes of the 1 bits is divisible by the length of the codeword plus 1. The full version of this code is conjectured to be an optimal solution to the problem (and is known to at least be close to optimal).

This challenge is about implementing an encoder for a variant of the VT code, known as the "systematic VT code". The systematic variant occasionally wastes a bit in order to make the encoding and decoding algorithms more efficient (and is used here because I think it makes for a more interesting golfing challenge than the original version of the code).

# The task

Given a string of bits as input, output a string of bits that represents the input string encoded with the systematic binary VT code.

The following algorithm is one possible definition of the code in question: following the algorithm will let you know the systematic VT encoding of any string of bits. The task is to implement something that produces the same results as this algorithm would; your solution doesn't necessarily need to use this algorithm itself, but it does have to produce the same results.

1. Imagine an infinite array of positions into which bits can be placed. Mark those positions whose 1-based indexes are powers of 2:

```
_* _* _ _* _ _ _ _* _ _ _ _ _ _ _ _* _ _ …

```
2. Fill the input bits into the unmarked positions of the array, in order from left to right, until no input bits are left. For example, suppose we were encoding the string `01101001100`:

```
_* _* 0 _* 1 1 0 _* 1 0 0 1 1 0 0 _* _ _ …

```
3. Cut off the array after the last filled bit: anything beyond that point is deleted, whether marked or unmarked:

```
_* _* 0 _* 1 1 0 _* 1 0 0 1 1 0 0

```
4. Add together the 1-based indexes of all the 1 bits in the array so far.

```
1  2  3 4  5 6 7 8  9 10 11 12 13 14 15
_* _* 0 _* 1 1 0 _* 1  0  0  1  1  0  0
           5+6     +9      +12+13       = 45

```
5. Calculate minus this sum, wrapping-modulo the length of the array plus 1. In this case, we're calculating \\$-45\mod (15+1)\\$, which is \\$3\\$ (because \\$-45=(16\times-3)+3\\$, i.e. \\$-45\\$ has remainder \\$3\\$ upon dividing by \\$16\\$).
6. Express the resulting value as a sum of distinct powers of 2; in this case, we have \\$3=2^1+2^0=2+1\\$. (In other words, we're writing the sum in binary, and then looking at the place-value of the resulting 1s.)
7. Fill in the marked positions of the array, placing a 1 into those positions whose indexes were part of the sum in the previous step, and a 0 into those positions that weren't:

```
1  2    4        8
1* 1* 0 0* 1 1 0 0* 1 0 0 1 1 0 0

```

The result of the process is the bit string we want to create as output, e.g. for our input string `01101001100`, the output is `110011001001100`.

# Clarifications

* As usual, your submission can either be a full program or a function, and can take input and produce output via any of the usually permitted I/O methods.
* The algorithm is defined in terms of 1-based indexes, because this is necessary for the resulting code to be able to handle deletions in every position. Even if your language uses 0-based indexes, you still have to produce the same result as the algorithm above does using its 1-based indexes (e.g. the first bit of the input string has to appear as the third bit of the output string, not the first or fourth).
* You can represent the "string of bits" in the input or output as a string/list of Booleans (i.e. using the truthiness or falsiness of each element); a string/list of numbers that are each 0 or 1 (or, in output, other values that are numerically 0 or 1); or a string/list of characters that are each "0" or "1" or each have a codepoint of 0 or 1. You can't represent it as the digits of a binary or decimal number, because that would cause leading zeroes to be lost.
* In I/O, you must use the same representation consistently, e.g. if "1" has a codepoint of 0 in some encoding, you can't output a string of "1"s and say that the 0s are being output by codepoint and the 1s as characters; but you may use different encodings for the input and the output if you wish.
* Although an empty input is meaningful (and, in theory, should encode to itself), your solution doesn't need to be able to handle this particular case.

# Test cases

```
0 -> 000
1 -> 101
10 -> 11100
01 -> 10001
111 -> 001011
1101 -> 1010101
1010 -> 1111010
01101001100 -> 110011001001100

```

# Victory condition

This is a challenge: as usual for code golf, the fewer bytes there are in your answer, the better. Your submission should contain a header listing the language in which the answer is written, and the number of bytes it contains.

# Answer
# JavaScript (ES6),  ~~89~~  83 bytes

A rather literal implementation of the algorithm described in the challenge.

```
s=>(g=(q,i=j=t=0)=>s[i]?(j&++j?s[t+=j*s[i],i++]:(q/=2)*2&1)+g(q,i):"")(g()&&j*t%~j)

```

Try it online!

### Commented

```
s => (                   // main function taking the input string
  g = (                  // g is a recursive function taking:
    q,                   //   q = result of the 5th step of the algorithm
                         //       as described in the challenge,
                         //       or undefined during the first pass
    i =                  //   i = pointer in s[]
                         // and also using:
    j =                  //   j = pointer in the output string
    t = 0                //   t = sum of the indices of 1 bits
  ) =>                   //
  s[i] ?                 // if s[i] is defined:
    (                    //
      j & ++j ?          //   increment j; if j is not a power of 2:
        s[               //
          t += j * s[i], //     add j to t if s[i] is "1"
          i++            //     yield s[i] and increment i afterwards
        ]                //
      :                  //   else:
        (q /= 2) * 2 & 1 //     yield the least significant bit of q
                         //     and divide q by 2
    ) + g(q, i)          //   append the result of a recursive call
  :                      // else:
    ""                   //   stop the recursion
)(                       //
  g() &&                 // do a first call to g so that j and t are set
  j * t % ~j             // then compute the correct value of q and use
)                        // it for the second call

```
> 3 votes

# Answer
# 05AB1E, ~~29~~ ~~27~~ 26 bytes

```
gÝo<£õÜD»SÐƶ«þO(sgÌ%bRs0ζS

```

Try it online, or try all test cases.

I'm quite sure this can be golfed

# Explanation

```
g             push the input's length
Ý             push the range [0,...,length]
o             take 2^<each value>
<             remove 1 from each value

£             split the input string into subsequences of those sizes
              (e.g. ["", "0", "110", "1001100", "", "", "", "", "", "", "", ""])
õ             push the empty string
Ü             remove all of its occurrences at the end of the list
              (e.g. ["", "0", "110", "1001100"])
D             duplicate the result
»             join it by newlines
S             convert it to a list of characters
              (e.g. ["\n", "0", "\n", "1", "1", "0", "\n", "1", "0", "0", "1", "1", "0", "0"])
Ð             triplicate that list, pushing 2 new copies
ƶ             lift the first copy, multiplying each number by its 1-based index
              (and not changing the newlines)
              (e.g. ["\n", 0, "\n", 4, 5, 0, "\n", 8, 0, 0, 11, 12, 0, 0])
«             merge it with the second copy
þ             keep only the numbers from that list
O             take the sum
(             negate it

s             swap that with the third copy
g             find that list's length (e.g. 14)
Ì             add 2 to it (e.g. 16)
%             calculate (-sum) % (length+2) (e.g. 3)

b             convert it to binary (e.g. "11")
R             reverse it (e.g. "11")
s             swap, to make the copy without newlines on top
              (e.g. ["", "0", "110", "1001100"])
0ζ            zip it with the reversed binary string, using 0 as a filler
              (e.g. [["1", ""], ["1", "0"], ["0", "110"], ["0", "1001100"]])
S             convert it to a list of characters
              (e.g. ["1", "1", "0", "0", "1", "1", "0", "0", "1", "0", "0", "1", "1", "0", "0"])

```
> 3 votes

# Answer
# , 126 bytes

```
\(x){v=!(l=seq(3*sum(x|1)))
v[p<--2^l/2]=seq(!x)
v=v[l<-1:(m=which.max(v))]
v[p]=x
v[-l[p]]=-sum(which(v>0))%%(m+1)%/%-p%%2
v}
```

Attempt This Online!
> 1 votes

# Answer
# MATL, ~~27~~ 26 bytes

```
0i"NB?0]@]vtfs_ynQ\BfqW1w(

```

Try it online! Or verify all test cases.

### How it works

```
0       % Push 0 (first "marked" position)
i       % Push input: numerical vector
"       % For each digit in the input
  N     %   Push current number of elements in the stack
  B?    %   Does its binary expansion contain only ones? If so,
    0   %     Push a 0 ("marked position")
  ]     %   End
  @     %   Push current input digit
]       % End
v       % Concatenate all digits into a column vector
tf      % Duplicate, find: push 1-based positions of non-zeros
s_      % Sum, negate
y       % Duplicate from below: pushes copy of column vector
nQ      % Length plus 1
\       % Modulo
Bf      % 1-based indices of binary expansion
qW      % Subtract 1, then compute 2 raised to that, element-wise
1w(     % Write 1 at those positions. Implicitly display

```
> 1 votes

# Answer
# Charcoal, 40 bytes

```
ＦＳ«Ｗ¬＆Ｌυ⊖Ｌυ⊞υω⊞υι»⭆υ⎇ιι⎇κ﹪÷﹪±↨⌕Ａυ1¹Ｌυκ²ω

```

Try it online! Link is to verbose version of code. I/O is as digit strings. Explanation:

```
ＦＳ«

```

Loop over the input bits.

```
Ｗ¬＆Ｌυ⊖Ｌυ⊞υω

```

Skip over powers of `2`. (`0` also gets skipped over, which adjusts for 0-indexing.)

```
⊞υι

```

Push the next bit in the position where it is to be output.

```
»⭆υ⎇ιι⎇κ﹪÷﹪±↨⌕Ａυ1¹Ｌυκ²ω

```

Fill in the skipped bits with the base `2` of the shortfall.
> 1 votes

# Answer
# Husk, 29 bytes

```
ΣSżż+öm;↔ḋ§%o→Lȯ_ΣWIΣmΘCΘm←İ2

```

Try it online!
> 0 votes

# Answer
# Desmos, 250 bytes

```
g(a)=2^a2-a-2
L=l.length
C=ceil(log_2L)-1
c=\{L<3:L,g(C)<L:C+1,C\}
K=2^c+L-g(c-1)
B=[1...K]
A=-0^{mod(log_2B,1)}
D=\{A=0:l[B+\sum_{n=1}^BA[n]],A\}
E=2^{[0...c]}
F=(i-mod(floor(mod(-B[D=1].total,K+1)/E),2)E)^2.min
f(l)=[\{D[i]>=0:D[i],F=0,0\}\for i=B]

```

The function \\$f(l)\\$ takes in a list of bits and returns the encoded list of bits. Pretty much follows the exact algorithm specified in the challenge.

Holy crap it's long. 100% can be golfable, but I'm too lazy to do that.

Try It On Desmos!

Try It On Desmos! - Prettified
> 0 votes

---
Tags: code-golf, string, binary, checksum
---


title: Restricted Integer Partitions

text:
# Question
Title: Restricted Integer Partitions
\\$P\_k(n)\\$ means the number of partitions of \\$n\\$ into exactly \\$k\\$ positive parts. Given \\$n\\$ and \\$k\\$, calculate \\$P\_k(n)\\$.

> Tip: \\$P\_k(n) = P\_k(n−k) + P\_{k−1}(n−1)\\$, with initial values \\$P\_0(0) = 1\\$ and \\$P\_k(n) = 0\\$ if \\$n \leq 0\\$ or \\$k \leq 0\\$. \[Wiki\]

# Examples

```
n    k    Ans
1    1    1
2    2    1
4    2    2
6    2    3
10   3    8

```

# Rules

# Answer
# Python 2, ~~61~~ ~~55~~ ~~51~~ 50 bytes

*-10 bytes thanks to Erik the Outgolfer. -1 byte thanks to Mr. Xcoder.*

I will say, I did copy the hint from OP and translate it to Python. :P

```
P=lambda n,k:n*k>0and P(n-k,k)+P(n-1,k-1)or+(n==k)

```

Try it online!
> 4 votes

# Answer
# Swift, ~~76~~ 73 bytes

```
func P(_ n:Int,_ k:Int)->Int{return n*k>0 ?P(n-k,k)+P(n-1,k-1):n==k ?1:0}

```

Try it online!

---

# Explanation

### How does the code structurally work?

First of all, we define our function `P`, with two integer parameters `n` and `k`, and give it a return type of `Int`, with this piece of code: `func P(_ n:Int,_ k:Int)->Int{...}`. The cool trick here is that we tell the compiler to ignore the names of the parameters, with `_` followed by a space, which saves us two bytes when we call the function. `return` is obviously used to return the result of our nested ternary described below.

Another trick I used was `n*k>0`, which saves us a couple of bytes over `n>0&&k>0`. If the condition is true (both the integers are still higher than `0`), then we recursively call our function with `n` decremented by `k` as our new `n` and `k` stays the same, and we add the result of `P()` with `n` and `k` decremented by 1. If the condition is not true, we return either `1` or `0` depending on whether `n` is equal to `k`.

### How does the recursive algorithm work?

We know that the first element of the sequence is **p0(0)**, and so we check that both integers are positive (`n*k>0`). If they are not higher than 0, we check if they are equal (`n==l ?1:0`), here being two cases:

* There is exactly 1 possible partition, and thus we return 1, if the integers are equal.
* There are no partitions if one of them is already 0 and the other is not.

However, if both are positive, we recursively call `P` twice, adding the results of `P(n-k,k)` and `P(n-1,k-1)`. And we loop again until `n` has reached 0.

---

* *Note:* The spaces cannot be removed.
> 4 votes

# Answer
# Pyth, 9 7 6 bytes

-1 byte thanks to Erik the Outgolfer!

```
/lM./E

```

Try it online!

Inputs to the program are reversed (i.e. `k, n`).
> 4 votes

# Answer
# Jelly, 6 bytes

```
œċS€ċ⁸

```

Try it online!
> 3 votes

# Answer
# Mathematica, 33 bytes

```
Length@IntegerPartitions[#,{#2}]&

```

here is n x k table

```
 \k->
 n1  0  0   0   0   0   0   0   0   0
 |1  1  0   0   0   0   0   0   0   0
 v1  1  1   0   0   0   0   0   0   0
  1  2  1   1   0   0   0   0   0   0
  1  2  2   1   1   0   0   0   0   0
  1  3  3   2   1   1   0   0   0   0
  1  3  4   3   2   1   1   0   0   0
  1  4  5   5   3   2   1   1   0   0
  1  4  7   6   5   3   2   1   1   0
  1  5  8   9   7   5   3   2   1   1

```
> 3 votes

# Answer
# MATL, 14 bytes

```
y:Z^!S!Xu!Xs=s

```

Try it online!

### Explanation

Consider inputs `6`, `2`.

```
y     % Implicitly take the two inputs. Duplicate from below
      % STACK: 6, 2, 6
:     % Range
      % STACK: 6, 2, [1 2 3 4 5 6]
Z^    % Cartesian power
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 1; 2 2; ...; 6 6]
!S!   % Sort each row
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 1 2; 2 2; ...; 6 6]
Xu    % Unique rows
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 2; ...; 6 6]
!Xs   % Sum of each row, as a row vector
      % STACK: 6, [2 3 ... 6 7 4 ... 12]
=     % Equals, element-wise
      % STACK: [0 0 ... 1  0 0 ... 0]
s     % Sum. Implicitly display
      % STACK: 3

```
> 3 votes

# Answer
# JavaScript (ES6), ~~42~~ ~~40~~ 39 bytes

I think this works.

```
f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y

```

---

## Try it

```
k.value=(
f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y
)(i.value=10,j.value=3)
onchange=_=>k.value=f(+i.value,+j.value)
```

```
*{font-family:sans-serif}input{margin:0 5px 0 0;width:100px;}#j,#k{width:50px;}
```

```
<label for=i>n: </label><input id=i type=number><label for=j>k: </label><input id=j type=number><label for=k>P<sub>k</sub>(n): </label><input id=k readonly>
```
> 3 votes

# Answer
## Haskell, 41 bytes

```
0#0=1
n#k|n*k>0=(n-k)#k+(n-1)#(k-1)
_#_=0

```

Try it online!
> 3 votes

# Answer
# Pari/GP, 35 bytes

Pari/GP has a built-in for iterating over integer partitions.

```
n->k->i=0;forpart(x=n,i++,,[k,k]);i

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~41~~ 40 bytes

```
f(n,k){n=n*k>0?f(n-k,k)+f(--n,--k):n&k;}

```

Try it online!
> 2 votes

# Answer
# Haskell, 41 bytes

```
n&0=0^n
n&k=sum$map(&(k-1))[n-1,n-k-1..0]

```

Try it online!

An alternate recurrence.
> 2 votes

# Answer
# 05AB1E, 5 bytes

```
ÅœIùg

```

Try it online or verify all test cases.

**Explanation:**

```
Åœ     # Get all lists of positive integers that sum to the first (implicit)
       # input-integer `n`
   ù   # Only keep the lists with a length equal to
  I    # the second input-integer `k`
    g  # Pop and push the length to get the amount of remaining lists
       # (which is output implicitly as result)

```
> 2 votes

# Answer
# Jelly, 13 bytes

I ~~have a feeling~~ know this basic approach **won't** be the golfiest!

```
RŒṖL€€Ṣ€QṀ€=S

```

**Try it online!**
> 1 votes

# Answer
# 05AB1E, 9 bytes

```
L²ã€{ÙO¹¢

```

Try it online!
> 1 votes

# Answer
# CJam, 18 bytes

```
{_,:)@m*:$_&::+e=}

```

Try it online!

Expects inputs in reverse, i.e. `k n` instead of `n k`.
> 1 votes

# Answer
# Scala, 98 bytes

Well this is some easy unreworked use of OP's tip.

`k` and `n` are the parameters of my recursive function `f`.

```
def f(n:Int,k:Int):Int={(k,n)match{case(0,0)=>1
case _ if k<1|n<1=>0
case _=>f(n-k,k)+f(n-1,k-1)}}

```

Try it online!
> 1 votes

# Answer
# R (+ pryr), 49 bytes

```
f=pryr::f(`if`(k<1|n<1,!n+k,f(n-k,k)+f(n-1,k-1)))

```

Which evaluates to the recursive function

```
function (k, n)
if (k < 1 | n < 1) !n + k else f(n - k, k) + f(n - 1, k - 1)

```

`(k < 1 | n < 1)` checks if any of the initial states are met. `!n + k` evaluates to TRUE (1) if both `n` and `k` are 0, and FALSE (0) otherwise. `f(n - k, k) + f(n - 1, k - 1)` handles the recursion.
> 1 votes

# Answer
# Regex  (Perl/PCRE+`(?^=)`RME), ~~32~~ 28 bytes

```
^((?^=(\2?x))(\1|^x)x*)+,\2$

```

Try it on replit.com (RegexMathEngine)

Takes its input in unary, as the lengths of two strings of `x`s delimited by a `,`, specifying \\$(n,k)\\$. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)

This simply enumerates all the partitions. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary-sized partition on the first iteration, then increasing it by an arbitrary nonnegative integer on each subsequent iteration. Each iteration increments the counter, which is then compared with \\$k\\$ at the end.

On each iteration, the size of the partition (arbitrarily chosen) is captured in `\1`, which is accessed via a nested backreference. The counter is stored in `\2`. Lookinto is used to ensure there is room to read and increment `\2` on each iteration.

```
^                   # tail = N
(                   # \1 = the following, looping:
    (?^=            # Lookinto; tail = N
        (           # \2 = sum of the following:
            \2?     # previous value of \2 if set, else 0
            x       # 1
        )
    )
    # \1 = the sum of the below items
    (
        \1          # On subsequent iterations, \1
    |
        ^x          # On the first iteration, 1
    )
    x*              # any nonnegative integer
    # \1 = some of the above items
)+                  # Iterate the above as many times as possible, min 1
,                   # Assert tail == 0; tail = K
\2$                 # Assert tail == \2

```

This uses nested backreferences (supported by Java / Perl / PCRE / .NET), a branch reset group (Perl / PCRE / Python`regex`), and a **lookinto**, a feature just added to RegexMathEngine. The parameterless form of it, `(?^=pattern)`, is equivalent to one of the common uses of variable-length lookbehind, `(?<=(?=pattern)^.*)` – it allows matching against the entire string, even after the top-level cursor has advanced past the start. It also has a parametrized form, e.g. `(?^5=pattern)` will match `pattern` against the current contents of `\5`.

# Regex  (RME / Perl / PCRE2 v10.35+), ~~36~~ 34 bytes

```
^((?|(?=.*,(\2x))\1x*|^(x)+))+,\2$

```

Try it on replit.com (RegexMathEngine)
Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
Attempt This Online! \- PCRE2 v10.40+
Attempt This Online! \- PCRE2 v10.40+ - test cases only

Without lookinto, there's still always room within \\$k\\$, accesible via lookahead, to count iterations.

Starting with a positive arbitrary-sized partition on the first iteration is done by `^(x)+`, which also initializes the counter to \\$1\\$. On subsequent iterations, `\1x*` advances by the sum of `\1` and any arbitrary nonnegative integer, which also gets captured in `\1`. At the end, `,` asserts that the cumulative sum is equal to \\$n\\$.

To enforce \\$k\\$ as the number of partitions, it starts by setting `\2` \\$=1\\$ on the first iteration with `^(x)+`. On subsequent iterations, `(?^=(\2x))` increments `\2` by \\$1\\$. Lookahead is used to avoid not having room for `\2`\\$+1\\$ when nearing the end of \\$n\\$. The Branch Reset Group `(?|`...`|`...`)` allows `\2` to be captured/recaptured in these two places.

```
^                   # tail = N
(                   # \1 = the following, looping:
    (?|             # Branch Reset Group
        # This alternative can only match on iterations after the first, because
        # it unconditionally matches \1 and \2.
        (?=         # Lookahead
            .*,     # tail = K
            (\2x)   # \2 += 1
        )
        \1x*        # \1 += {any nonnegative integer}; tail -= \1
    |
        ^           # Anchor to start, to only match on the first iteration.
        (x)+        # \2 = 1; \1 = {any nonnegative integer}; tail -= \1
    )
)+                  # Iterate the above as many times as possible, min 1
,                   # Assert tail == 0; tail = K
\2$                 # Assert tail == \2

```

# Regex  (RME / Perl / PCRE2), 50 bytes

```
^((?=(?(3)(\3)))((?|(?=.*,(\4x))\2x*|^(x)+)))+,\4$

```

Try it on replit.com (RegexMathEngine)
Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
Try it online! \- PCRE2 v10.33 / Attempt This Online! \- PCRE2 v10.40+
Attempt This Online! \- PCRE2 v10.40+ - test cases only

PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied back and forth between `\2` and `\3` using only forward-declared backreferences.

This would also make the regex compatible with Python`regex` and Ruby, but they have no way of doing  output without source code modifications.

It still doesn't work under PCRE1, probably due to its bug where in certain conditions, captures are not reverted to their earlier values when backtracking: Try it online!

```
^                      # tail = N
(                      # \1 = the following, looping:
    (?=
        (?(3)(\3))     # If \3 is set, \2 = \3, else leave \2 unset
    )
    (                  # \3 = the following, to avoid a nested backreference
        (?|            # Branch Reset Group
            # This alternative can only match on iterations after the first,
            # because it unconditionally matches \1 and \2.
            (?=
                .*,    # tail = K
                (\4x)  # \4 += 1
            )
            \2x*       # \3 = \2 + {any nonnegative integer}; tail -= \3
        |
            ^          # Anchor to start, to only match on the first iteration.
            (x)+       # \4 = 1; \3 = {any nonnegative integer}; tail -= \3
        )
    )
)+                     # Iterate the above as many times as possible, min 1
,                      # Assert tail == 0; tail = K
\4$                    # Assert tail == \4

```
> 1 votes

# Answer
# Vyxal, 5 bytes

```
ṄvL=∑

```

Try it Online!

# Jelly, 5 bytes

```
ŒṗẈ=S

```

Try it online!

Dang it, ninja'd by Kevin because I took the time to get the shortest jelly answer too :p

Exact same approach as the 05ab1e answer, derived independently - both answers get the integer partitions of the first input and then count the number of partitions where the length equals the second input.
> 1 votes

---
Tags: code-golf, combinatorics, integer-partitions
---


title: Find ranges of True values in a list

text:
# Question
Title: Find ranges of True values in a list
# 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)

```

# Answer
> 7 votes
# 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 `0`s and `1`s, e.g. `[1, 1, 0, 1, 0]`. Outputs like in the challenge, e.g. `[[0, 1], [3, 3]]`.

Test Suite

# Answer
> 9 votes
# Pyth, 18 bytes

```
CxR.:++~Zkz02_B_`T

```

Test suite

True is represented as `1`, False as `0`.

Ranges are represented inclusively.

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

# Answer
> 5 votes
# 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

```

# Answer
> 5 votes
## 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,

# Answer
> 4 votes
# 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.

# Answer
> 4 votes
# 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

```

# Answer
> 4 votes
## 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

```

# Answer
> 4 votes
# Vyxal, ~~12~~ 11 bytes

```
0J0p¯T⁽‹ẇ2ẇ

```

Try it Online!

Translation of my Jelly answer.

## Explanation

```
0J0p¯T⁽‹ẇ2ẇ
0J             Append 0
  0p          Prepend 0
    ¯         Deltas
     T        Truthy indices
      ⁽ ẇ     Apply to even indices
       ‹        Decrement
         2ẇ   Split into chunks of 2

```

*-1 byte thanks to lyxal*

# Answer
> 3 votes
## 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)]

```

# Answer
> 3 votes
# 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.

# Answer
> 3 votes
## 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.

```

# Answer
> 3 votes
# Jelly, 12 11 10 bytes

```
;0ŻIT’Ðes2

```

Try it online!

Accepts a list of zeros and ones. Outputs a list of 1-based ranges.

## Explanation

Using \[1,1,0,1\] as an example.

```
;0ŻIT’Ðes2   Main monadic link
;0           Append a zero: [1,1,0,1,0]
  Ż          Prepend a zero: [0,1,1,0,1,0]
   I         Increments: [1,0,-1,1,-1]
    T        Indices of truthy alements: [1,3,4,5]
      Ðe     Apply to even indices:
     ’         Decrement: [1,2,4,4]
        s2   Split into groups of two: [[1,2],[4,4]]

```

# Answer
> 2 votes
## 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.

# Answer
> 2 votes
# 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>
```

# Answer
> 2 votes
## 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

```

# Answer
> 2 votes
# , 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

```

# Answer
> 2 votes
## 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.

# Answer
> 2 votes
## APL, 17 chars

```
{(↑,↑∘⊖)¨⍵⊂⍵×⍳⍴⍵}

```

In `⎕IO←0` and `⎕ML←3`. In English:

* `⍵×⍳⍴⍵`: zero out the elements of the index vector as long as the argument where the argument is false
* `⍵⊂`: cut at the beginning of each run of truths and throw away the false's
* `(↑,↑∘⊖)¨`: take the first and last element of each subarray

# Answer
> 1 votes
## 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)))

```

# Answer
> 1 votes
## 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.

# Answer
> 1 votes
## CJam, 30 bytes

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

```

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

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

# Answer
> 1 votes
# 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.

# Answer
> 1 votes
# Husk, 14 bytes

```
§zeW<om←W>`:0Θ

```

Try it online!

# Answer
> 1 votes
# K (oK), 19 bytes

```
+&:'+{y&~x,z}.'-3':

```

Try it online!

Uses `-n':` (window) so the inner `{y&!x,z}` function has access to the previous (`x`), current (`y`), and next (`z`) value in the input boolean list.

# Answer
> 1 votes
# Jelly, 13 bytes

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

```

Try it online!

+4 bytes to handle the all `0`s 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"

```

# Answer
> 1 votes
# Husk, 11 bytes

```
m§e←→ġo=→ηf

```

Try it online!

```
m§e←→ġo=→ηf
         ηf     # get truthy indices
     ġo=→       # group runs of adjacent values
m               # then, for each group
 §e←→           # get the first & last elements

```

# Answer
> 1 votes
# 05AB1E, 12 bytes

Uses `0/1` for `F/T`.

```
Åγ.¥ü2sÏ€εN-

```

Try it online!

`Åγ` run-length encodes the input, pushing the chunk elements and the chunk lengths.
takes the cumulative sum of the chunck lengths and prepends a 0.
`ü2` creates pairs of all adjacent numbers in this list.
`s` swaps to the list of chunk elements.
`Ï` selects each pair which is at the same index as a truthy chunk. The selected pairs are now the half-inclusive truthy range `[a, b)`.
`€ε` iterates over every number in every range, and `N-` subtracts the 0-based index from each number to get the inclusive ranges.

Try it with step-by-step output!

# Answer
> 1 votes
# Vyxal, 9 bytes

```
ẏ‡?iŻv₍gG

```

Try it Online!

# Answer
> 0 votes
# 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

```

# Answer
> 0 votes
# Mathematica, 45 bytes

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

```

Not particularly interesting; uses a builtin.

# Answer
> 0 votes
**Clojure, 109 chars**

```
#(first(reduce(fn[[r i]p](let[e(+(count p)i)][(if(first p)(conj r[i(dec e)])r)e]))[[]0](partition-by not %)))

```

The first thing that came to my mind, based on `reduce` and `partition-by`.

Simple test case (maps `T` to `true` and `F` to `false`):

```
(def f #(first(reduce(fn[[r i]p](let[e(+(count p)i)][(if(first p)(conj r[i(dec e)])r)e]))[[]0](partition-by not %))))
(f (map #(= 'T %) '[F,T,T,F,F,T,T,T]))

```

# Answer
> 0 votes
# Japt, 14 bytes

Takes input as an array of bits.

```
ð òÈnYÉÃmg[TJ]

```

Try it

# Answer
> 0 votes
# 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

# Answer
> 0 votes
# 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, as Jelly is).

**Try it online!** Or see the test-suite.

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

```

i.e. get a pair of lists of:

1. indices of truthy values with no truthy value to their right (run starts); and
2. indices of truthy values with no truthy value to their left (run ends)

...and transpose that to a list of `[run start, run end]` pairs.

# Answer
> 0 votes
# Knight, <sup>62</sup> 61 bytes

```
;=i 0;=s T;W;=i+i 1=nP;=nEn&|&s n&!s!n;O Is i-i 1=s!s&!sO-i 1

```

Try it online!

*-1 thanks to Steffan*

Uses 1 indexing.

## how

```
;=i 0          # Set i = 0
;=s T          # Set s (for "searching for a 1" to true)
;W;=i+i 1=nP   # While reading a line of input "n" and
               # storing it in n, and incrementing i...
;=nEn          # Coerce "n" to a number, so we can use
               # it as a boolean (string "1" would be false)
&|&s n &!s !n  # If we're "searching" and found a 1 or
               # are not searching and found a 0...
;O Is i-i 1    # output the current index when searching,
               # or the current index - 1 otherwise.
=s!s           # and toggle "searching" status
&!sO-i 1       # if we end on a 1, output again the
               # final index - 1

```

---
Tags: code-golf, array
---