title: Shortest distinguishable slice

text:
# Question
Title: Shortest distinguishable slice
For this challenge, a slice of a string is defined as an upper and lower index that can "cut" a piece of a string. All characters from the string in the range `[start, end)` (or `[start, end]` if you don't speak practlang) are part of that slice. If the upper index exceeds the string's length, the overflow is ignored. For example, the (zero-indexed) slice from 1 to 4 in "abcdef" is "bcd", and the slice from 3 to 7 in "Hello!" is "lo!". A slice cannot have a length of zero (i.e. both endpoints are equal), but the string cut by it may.

A slice can distinguish between strings if that slice is unique across all provided strings. For instance, the slice (1, 4) can distinguish between the strings "happy", "angry", and "hungry", but so can (2, 4) or (1, 2).

Your task is: Given a list of strings, output the shortest slice that can be used to distinguish between them.

Your input strings will only ever consist of printable ASCII characters. There will be at least one valid distinguishable slice for a given input. Your list will not contain any duplicate words. Your program may either use zero-based indexing or one-based indexing, but please specify which is being used in your submission.

Output two numbers, marking the start and end of the slice. If there are multiple distinguishable slices that tie for shortest, you may output for any or all of them.

This is , so the shortest submission in bytes for each language wins.

## Test cases

```
"happy", "angry", "hungry"
-> (1, 2) or (2, 3) or (3, 4)

"sheer", "shrew", "shine", "shire", "spike", "shy"
-> (2, 4) or (3, 5)

"snap", "crackle", "pop", "smack", "sizzle", "whiff", "sheen"
-> (0, 2) or (1, 3)

"Sponge", "Paper", "Moon", "Air", "Bowl", "Water", "Alien", "Dragon",
"Devil", "Lightning", "Nuke", "Dynamite", "Gun", "Rock", "Sun",
"Fire", "Axe", "Snake", "Monkey", "Woman", "Man", "Tree", "Cockroach", "Wolf"
-> (0, 3)

```

# Answer
# Jelly, ~~19~~ 15 bytes

```
z0ZQƑ$ƤÐƤZœi1UÄ

```

Try it online!

Output is 1-indexed, but the footer converts to 0-indexed for convenience.

```
z0                 Transpose with filler 0.
      Ƥ            For each prefix of
       ÐƤ          each suffix of the columns,
  Z                transpose back to rows
   QƑ$             and check if all rows are unique.
         Z         Transpose the results yet again,
      ƤÐƤZ         grouping results by substring length.
          œi1      Find the first multidimensional index of 1,
             U     reverse it,
              Ä    and cumsum ([start index, length] -> [start index, end index]).

```

`z0ẆµZQƑ)ƙ@Ẉœi1UÄ` is a fun 16-byter. Initially felt like  would have to be the way forward, but I only even thought of that one in the course of writing this explanation!
> 9 votes

# Answer
# JavaScript (ES6), 83 bytes

```
f=(a,n)=>[...a+0].some((_,i)=>a.every(o=w=>o[w.slice(...r=[i,i+n])]^=1))?r:f(a,-~n)

```

Try it online!

### Commented

```
f = (              // f is a recursive function taking:
  a,               //   a[] = input array
  n                //   n   = counter, initially undefined
) =>               //
[...a + 0]         // build a large enough array to try all
                   // possible starting indices in each word
.some((_, i) =>    // for each starting index i:
  a.every(o =      //   o will be used to store the word slices
    w =>           //   for each word w in a[]:
    o[             //
      w.slice(     //     isolate the slice of w defined by
        ...r =     //     the range r[]
        [i, i + n] //     consisting of [i, i + n]
      )            //
    ] ^= 1         //     toggle the flag in o for this slice
                   //     every() will fail if it was already set
  )                //   end of every()
)                  // end of some()
?                  // if successful:
  r                //   return r[]
:                  // else:
  f(a, -~n)        //   try again with n + 1

```
> 5 votes

# Answer
# Vyxal, ~~21 22~~ 21 bytes

```
vf0ÞṪÞKƛKƛ∩Þu;;∩1ÞḟṘ¦

```

Try it Online!

Port of @UnrelatedString's Jelly answer.
*-1 thanks to @UnrelatedString*

#### Explanation

```
vf0ÞṪÞKƛKƛ∩Þu;;∩1ÞḟṘ¦   # Implicit input
vf                      # Flatten each into a list of characters
  0ÞṪ                   # Transpose with filler 0
     ÞKƛ      ;         # Map over suffixes:
        Kƛ   ;          #  Map over prefixes:
          ∩             #   Transpose
           Þu           #   All unique?
               ∩        # Transpose
                1Þḟ     # First multidimensional indices of 1
                   Ṙ    # Reverse
                    ¦   # Cumulative sums
                        # Implicit output

```

Old (didn't work):

```
             # Implicit input

@Gʀ2↔µ÷$-;   # Step 1: Generate all possible slices in order
@            # Push the length of each string in the input list
 Gʀ          # Get the zero range of the maximum of this list
   2↔        # Combinations of the above list with length 2
     µ   ;   # Sort this list of pairs by the following:
      ÷      #  Dump both numbers onto the stack
       $-    #  Swap and subtract the two numbers

λ£?ƛ¥i;Þu;c  # Step 2: Get the shortest distunguishable slice
λ        ;c  # Get the first item for which the following is true:
 £           #  Save the pair in the register
  ?ƛ  ;      #  For each string in the input list:
    ¥i       #   Index the pair into the string
             #   (Vyxal supports slice indexing)
       Þu    #  And check if all the results are unique

             # Implicit output of the first pair which returns true

```
> 5 votes

# Answer
# Python, 131 bytes

```
lambda x:(r:=range(max(map(len,x))))and min([(i,j)for i in r for j in r if len({s[i:j]for s in x})==len(x)],key=lambda a:a[1]-a[0])

```

Attempt This Online!

Most likely can be golfed down further.
> 4 votes

# Answer
# , ~~113~~ ~~108~~ 106 bytes

*Edit: -2 bytes thanks to pajonk*

```
\(x,n=1:max(nchar(x)),`/`=sapply,m=n/\(j)n/\(i)(j-i+1)*all(table(substr(x,i,j))<2))which(m==min(m[m>0]),T)

```

Attempt This Online!

1-based indexing; outputs all tied minimal slices if there is more than one.

Assumes that `""` is a string-slice that is distinguishable from non-empty slices (so 1-based `(4,5)` would be a valid output for the second test case).
Add 11 bytes to avoid this.
> 3 votes

# Answer
# Pyth, ~~25~~ 20 bytes

*-5 bytes by using .C*

```
.M-FZf{I:R.*TQ.CUsQ2

```

Try it online!

Uses zero based indexing, outputs all shortest slices.

### Explanation

```
              .CUsQ2    # list all possible slices (and many more)
     f                  # filter on lambda T
        :R.*TQ          #   the input strings mapped to their slices
      {I                #   is invariant under deduplication
.M-FZ                   # take elements which maximize the first element of the slice minus the second element of the slice

```
> 3 votes

# Answer
# , 103 bytes

*Edit: 0-byte fix thanks to @Dominic van Essen.*

```
\(x){b=d=max(nchar(x)):1;for(i in b)for(j in b)if(all(table(substr(x,i,j))<2)&j-i<d-T){T=i;d=j};c(T,d)}

```

Works only in R version 4.1, so don't Attempt This Online! You can Try it online! with `function` instead of `\`.

Attempt This one Online!, which is 2 bytes longer.

Uses test suite from @Dominic van Essen's answer, which is longer, but IMHO more elegant (no loops, just `sapply`).
> 3 votes

# Answer
# Charcoal, ~~50~~ 49 bytes

```
ＷＳ⊞υι≔⌈ＥυＬιθＦ⊕θＦθ¿¬ⅉ«≔Ｅυ✂λκ⁺κι¹η¿∧⌊η⬤η⁼¹№ηλＩ⟦κ⁺κι

```

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

```
ＷＳ⊞υι

```

Input the strings.

```
≔⌈ＥυＬιθ

```

Get the length of the longest string.

```
Ｆ⊕θＦθ

```

Loop over more than enough lengths and starting indices. Edit: Saved 1 byte by looping over zero length as well (this obviously gets ignored later due to the empty slice rule).

```
¿¬ⅉ«

```

Stop once a slice has been found.

```
≔Ｅυ✂λκ⁺κι¹η

```

Get the current set of slices.

```
¿∧⌊η⬤η⁼¹№ηλ

```

If they are valid and unique, then...

```
Ｉ⟦κ⁺κι

```

... output the start and end indices.
> 2 votes

# Answer
# Julia 1.0, ~~128~~ 118 bytes

```
~a=(r=max(length.(a)...);(q=[y:x+y for x=0:r-1 for y=1:r-x])[findfirst(x->allunique(getindex.(rpad.(a,r),Ref(x))),q)])

```

Try it online!

Output is a unit range. Note that Julia defaults to 1-based indexing and inclusive number ranges.

-10 bytes thanks to Mukundan314: rewrite array comprehension to avoid calling `sort(_,by=length)` on the vector of ranges
> 2 votes

# Answer
# Scala, ~~188~~ 161 bytes

saved 27 bytes thanks to comment.

Try it online!

```
def f(s:Seq[String])=(0 to s(0).size).flatMap(i=>(i+1 to s(0).size).map(j=>(i,j))).filter(p=>s.map(_.slice(p._1,p._2)).distinct.size==s.size).minBy(p=>p._2-p._1)

```

Ungolfed version

```
object Main{
  def shortestDistinguishableSlice(strings: Seq[String]): (Int, Int) = {
    val n = strings.head.length
    (0 until n).flatMap(i => (i + 1 to n).map(j => (i, j)))
      .filter { case (i, j) => strings.map(s => s.slice(i, j)).distinct.size == strings.size }
      .minBy { case (i, j) => j - i }
  }

  def main(args: Array[String]): Unit = {
    val strings1 = Seq("happy", "angry", "hungry")
    val strings2 = Seq("sheer", "shrew", "shine", "shire", "spike", "shy")
    val strings3 = Seq("snap", "crackle", "pop", "smack", "sizzle", "whiff", "sheen")
    val strings4 = Seq(
      "Sponge", "Paper", "Moon", "Air", "Bowl", "Water", "Alien", "Dragon",
      "Devil", "Lightning", "Nuke", "Dynamite", "Gun", "Rock", "Sun",
      "Fire", "Axe", "Snake", "Monkey", "Woman", "Man", "Tree", "Cockroach", "Wolf"
    )

    println(shortestDistinguishableSlice(strings1)) // prints (1,2)
    println(shortestDistinguishableSlice(strings2)) // prints (2,4)
    println(shortestDistinguishableSlice(strings3)) // prints (0,2)
    println(shortestDistinguishableSlice(strings4)) // prints (0,3)
  }
}

```
> 1 votes

---
Tags: code-golf, string
---


# Question
Title: The Great Battle Conundrum- Who are Alive?
Maximillian is the chief commander of the Great Greek Army and he is leading his forces into a crucial war with Spain.

If all the enemy soldiers stand in a straight line incrementally marked starting from position `1`, and a particular soldier at position \\$i\\$ dies, the soldiers at position \\$2i\\$ and \\$2i+1\\$ die as well. This happens in a cascading manner and so, a major part of troops can be killed by just killing one person.

By retrospection, Maximillian realizes that this also means that if the soldier marked \\$1\\$ (standing at the head of the troops) is killed and then the entire army is defeated. This however is not an easy task as the commander of the Spanish leads the Spanish troops and stands at the head of the troops. When one cascading set of deaths is completed, the remaining troops re-align; filling in the missing gaps and the death rule applies to the new positions.

Let there be \\$N\\$ soldiers in the enemy's camp marked as \\$1,2,3,..., N\\$. Maximillian identifies a list of \\$K\\$ individuals by their marked numbers, who will be executed in a sequential manner. Output the list of soldiers left in the enemy camp in increasing order of their marked values.

---

**Input Specification:**

`input1:` `N`, number of soldiers in the enemy camp

`input2:` `K`, number of soldiers to be killed

`input3:` An array of soldiers numbered between `1` to `N` who will be killed sequentially in the mentioned order

**Output Specification:**

Output an array of numbers that belong to soldiers who are alive at the end (in increasing order). If all are dead, then output `{0}`.

---

**Test Case 1**

```
input1: 7
input2: 1
input3: {1}

```

```
Output: {0}

```

**Explanations:**

The soldiers can be represented in the following way:

When Soldier `{1}` is killed, then `{2,3}` die.

When `{2,3}` die, `{4,5,6,7}` die.

**Test Case 2**

Example 2:

```
input1: 7
input2: 2
input3: {2,7}

```

```
Output: {1,3,6}

```

**Explanations:**

The soldiers can be represented in the following way:

When Soldier - `{2}` is killed, then `{4,5}` die.

They do not have any troops at \\$2i\\$ and \\$2i+1\\$.

The new representation becomes:

This is `code-golf` so the shortest code in bytes wins.

---

## References:

# Answer
# Jelly, 16 bytes

```
Ḥ,‘$€F>ÐḟðƬF⁴R¤ḟ

```

Try it online!

```
Ḥ,‘$€F>ÐḟðƬF⁴R¤ḟ  Main Link
         ðƬ       While the results don't reach a fixed point
Ḥ                 Double each value (killed soldier)
 , $              Pair            with
    €                  each value
  ‘                                    itself incremented
     F            Flatten the result
       Ðḟ         Filter out (remove) elements that are
      >           Greater than the right argument (the number of soldiers)
           F      Flatten the accumulated list of killed soldiers
               ḟ  Filter; remove the killed soldiers from
            ⁴R¤   [1, 2, ..., N], the list of all soldiers

```
> 2 votes

# Answer
# Python, ~~125~~ ~~124~~ 119 bytes

*-1 byte thanks to @The Thonnu*

```
def f(n,k,A):*B,=range(n+1);g=lambda d:d<len(B)and g(2*d+1)|g(2*d)|B.pop(d);[g(B.index(x))for x in A];print(B[1:]or[0])

```

Attempt This Online!

Uses the array representation of a binary tree, then recursively removes the given element and the associated children of that element for each item in `A`.
> 2 votes

# Answer
# Scala, 211 bytes

Modified from @97.100.97.109's answer

Golfed version, Try it online!

```
def f(n:Int,k:Int,A:List[Int])={var B:List[Int]=(0 to n).toList;def g(d:Int):Unit={if (d<B.length){g(2*d+1);g(2*d);B=B.patch(d,Nil,1);}};A.foreach(x=> g(B.indexOf(x)));println(if(B.length>1)B.tail else List(0))}

```

Ungolfed verison:

```
object Main {
  def f(n: Int, k: Int, A: List[Int]): Unit = {
    var B: List[Int] = (0 to n).toList

    def g(d: Int): Unit = {
      if (d < B.length) {
        g(2 * d + 1)
        g(2 * d)
        B = B.patch(d, Nil, 1)
      }
    }

    A.foreach(x => g(B.indexOf(x)))
    println(if (B.length > 1) B.tail else List(0))
  }

  def main(args: Array[String]): Unit = {
    f(7, 2, List(2, 7))
  }
}

```
> 1 votes

---
Tags: code-golf, binary-tree
---


title: Great Leap to the Right

text:
# Question
Title: Great Leap to the Right
Given a string `s` consisting of characters a-z lowercase, generate 5 arrays `a1`, `a2`, `a3`, `a4`, and `a5` of size `n` (length of `s`) where the `i`-th element of each array represents the index of the next occurrence of the `i`-th character in `s`, with the following conditions:

* If no such occurrence exists, set the value to `n` (0-based indexing) or `n+1` (1-based indexing) depending on the indexing convention you use.
* `a1` represents the 1st next occurrence of the character, `a2` represents the 2nd next occurrence, `a3` represents the 4th next occurrence, `a4` represents the 8th next occurrence, and `a5` represents the 16th next occurrence.

This is a code golf challenge, so the shortest code in bytes wins.

Here are some test cases. They all use 0-based indexing.

**Input:** `aakakakakka`
**Output:**

```
1 3 4 5 6 7 8 10 9 11 11
3 5 6 7 8 10 9 11 11 11 11
7 10 9 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11

```

**Input:** `sydgdtsfixuvhdgisifdyovjcgs`
**Output:**

```
6 20 4 14 13 27 16 18 15 27 27 22 27 19 25 17 26 27 27 27 27 27 27 27 27 27 27
16 27 13 25 19 27 26 27 17 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27

```

**Input:** `qmorzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz`
**Output:**

```
59 59 59 59 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
59 59 59 59 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59
59 59 59 59 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59
59 59 59 59 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59 59 59 59 59
59 59 59 59 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59

```

# Answer
# BQN, 18 bytesSBCS

```
-∘≠↑¨<⊒¨⍷⊸∾⍟(2⋆↕5)

```

Run online!

The *Progressive Index of*  does the heavy lifting here.

`...⍟(2⋆↕5)` 1, 2, 4, 8 and 16 times:
`⍷⊸∾` prepend the unique characters to the string.

`<⊒¨` For each of the resulting strings find the progressive indices of the characters in the input string. *progressive* means that each index can only be used once. The length of the input is used as a *not found* value.
`-∘≠↑` From each resulting integer list, take as many values from the back as there are characters in the input.
> 4 votes

# Answer
# Excel, ~~111~~ 109 bytes

*With thanks to **JvdV** for the 2-byte save*.

```
=LET(
    b,LEN(A1),
    c,SEQUENCE(b),
    d,MID(A1,c,1),
    IFERROR(FIND(0,SUBSTITUTE(MID(A1,c+1,b),d,0,{1,2,4,8,16}))+c-1,b)
)

```

0-based. Input in cell `A1`. Generates an *n*-row-by-5-column array, where *n* is the length of the input string.
> 3 votes

# Answer
# , 35 bytes

```
(2^i.5){0|:i.@#+(#,~^:16[:I.{.=])\.

```

Try it online!

* `(…)\.`: Apply the verb inside to each suffix of the string, in order of start point.
    + `{.` `=` `]`: Check for equality (`=`) between the first element (`{.`) and the whole suffix (`]`, identity function). This produces a list of Booleans.
    + (`[:` to use monadically.) `I.` produces a list of indices of the 1s.
    + `#``,` `~` `^:` `16`: Take the length of the suffix (`#`) and append (`,` with `~` to reverse operands) it to the list, repeating 16 times (`^:` `16`).
* `i.` `@` `#``+`: Add (`+`) \[0,1,2,3,…\] (`#` gives the length of the string, and `i.` produces that many numbers). This adjusts the numbers from indices in the suffixes to indices in the whole string.
* `0` `|:`: Transpose.
* `(2^i.5){`: Take the rows at indices 1, 2, 4, 8, 16.
> 2 votes

# Answer
# JavaScript (ES6), 93 bytes

Expects an array of characters. Returns an array of 5 arrays of integers, using 0-based indexing.

```
f=(s,k=5)=>k--?[...f(s,k),s.map(g=(c,i,q)=>!s[i]|q>>k?i:g(c,[...s,c].indexOf(c,i+1),-~q))]:[]

```

Try it online!

### Commented

```
f = (               // f is a recursive function taking:
  s,                //   s[] = input string, as an array of characters
  k = 5             //   k = counter, initialized to 5
) =>                //
k-- ?               // decrement k; if it was not 0:
  [ ...f(s, k),     //   append the result of a recursive call
    s.map(          //   for each entry in s[],
    g = (           //   using a recursive callback function g taking:
      c,            //     c = current character
      i,            //     i = current position
      q             //     q = iteration counter, initially zero'ish
    ) =>            //
      !s[i] |       //     if s[i] is undefined
      q >> k ?      //     or we've done 2 ** k iterations:
        i           //       stop and return i
      :             //     else:
        g(          //       do a recursive call:
          c,        //         pass c unchanged
          [...s, c] //         append c to a copy of s[]
          .indexOf( //         and look in there for the position of
            c,      //         the next occurrence of c
            i + 1   //         starting the search at i + 1
          ),        //
          -~q       //         increment q
        )           //       end of recursive call
    )               //   end of map()
  ]                 //
:                   // else:
  []                //   stop

```
> 2 votes

# Answer
# Charcoal, 23 bytes

```
ＩＥ⁵Ｅθ§⁺Φ⌕Ａθλ›νμＥφＬθ⊖Ｘ²ι

```

Try it online! Link is to verbose version of code. 0-indexed. Outputs each index on its own line with each set of indices double-spaced from each other. Explanation:

```
  ⁵                     Literal integer `5`
 Ｅ                      Map over implicit range
    θ                   Input string
   Ｅ                    Map over characters
        ⌕Ａ              Find all occurrences of
           λ            Current character in
          θ             Input string
       Φ                Filtered where
             ν          Occurrence index
            ›           Is greater than
              μ         Current index
      ⁺                 Concatenated with
                φ       Predefined variable `1000`
               Ｅ        Map over implicit range
                  θ     Input string
                 Ｌ      Length
     §                  Indexed by
                     ²  Literal integer `2`
                    Ｘ   Raised to power
                      ι Outer value
                   ⊖    Decremented
Ｉ                       Cast to string
                        Implicitly print

```
> 1 votes

# Answer
# Python NumPy, 92 bytes

```
lambda*s:clip(N:=len(s),0,x:=a(17*s,0,"s"))[2**c_[:5]+a(x)[:N]]
from numpy import*
a=argsort

```

Attempt This Online!

Expects the splatted input string and returns a 2D array of integers.

### How?

Repeat the input to make sure at least 16 excess copies of every letter are available. Do an indirect sort, i.e. a sort we can take back by applying the inverse permutation. Apply the sort, shift by 1,2,4,8 or 16 and unsort. Clip to range.
> 1 votes

# Answer
# Pyth, 24 bytes

```
m@C.e+fgTkxbcz1mlzGz^2d5

```

Try it online!

### Explanation

```
                            # implicitly assign z = input()
   .e              z        # enumerated map b, k over z, indices
          xbcz1             #   get all indices of b in z
      f                     #   filter this on lambda T
       gTk                  #     T >= k
     +         mlzG         #   pad with 26 copies of len(z)
  C                         # transpose
m                      5    # map d over [0-4]
 @                          #   the element at the index
                    ^2d     #   2 ^ d

```
> 1 votes

# Answer
# Haskell, 90 bytes

```
f s=[[([n|(n,x)<-z,x==c,i<=n]++l)!!(2^j)|(i,c)<-z]|let l=length s:l;z=zip[0..]s,j<-[0..4]]

```

It's got a perfectly natural typing, and uses 0-indexing as is normal for Haskell.

```
f :: String -> [[Int]]

```

try it online, with tests
> 1 votes

# Answer
# Octave/MATLAB, 174 bytes

Modified from @loopy walt's answer

Golfed version, try it online!

```
function x=f(varargin),s=double(cell2mat(varargin));N=numel(s);[~,x]=sort(repmat(s,1,17));[~,i]=sort(x);f_i=bsxfun(@plus,i(1:N)-1,(2.^(0:4)).');x=min(max(x-1,0),N)(f_i+1);end

```

Ungolfed version:

```
function x = f(varargin)
    s = cell2mat(varargin);
    s = double(s);
    N = length(s);
    s17 = repmat(s,1,17);
    [~, x] = sort(s17);
    x=x-1;
    index_part1 = power(2, 0:4).';
    [~, index_part2 ]= sort(x);
    index_part2 = index_part2(1:N)-1;
    clipped = min(max(x, 0), N);
    sum_matrix = bsxfun(@plus, index_part2, index_part1);
    final_index = sum_matrix;
    x = clipped(final_index+1);
end

disp(f("aakakakakka"))
disp(f("sydgdtsfixuvhdgisifdyovjcgs"))
disp(f("qmorzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"))

```
> 1 votes

# Answer
# Arturo, 92 bytes

```
$[s][map 0..4'x[i:0map s'c['i+1(char? select.with:'j.n:2^x drop s i'm->c=m)?->j+i->size s]]]

```

Try it
> 0 votes

---
Tags: code-golf
---


title: Find the Cross Product

text:
# Question
Title: Find the Cross Product
The cross product of two three-dimensional vectors \\$\vec a\\$ and \\$\vec b\\$ is the unique vector \\$\vec c\\$ such that:

* \\$\vec c\\$ is orthogonal to both \\$\vec a\\$ and \\$\vec b\\$
* The magnitude of \\$\vec c\\$ is equal to the area of the parallelogram formed by \\$\vec a\\$ and \\$\vec b\\$
* The directions of \\$\vec a\\$, \\$\vec b\\$, and \\$\vec c\\$, in that order, follow the right-hand rule.

There are a few equivalent formulas for cross product, but one is as follows:

$$\vec a\times\vec b=\det\begin{bmatrix}\vec i&\vec j&\vec k\\a\_1&a\_2&a\_3\\b\_1&b\_2&b\_3\end{bmatrix}$$

where \\$\vec i\\$, \\$\vec j\\$, and \\$\vec k\\$ are the unit vectors in the first, second, and third dimensions.

### Challenge

Given two 3D vectors, write a full program or function to find their cross product. Builtins that specifically calculate the cross product are disallowed.

### Input

Two arrays of three real numbers each. If your language doesn't have arrays, the numbers still must be grouped into threes. Both vectors will have magnitude \\$\<2^{16}\\$. Note that the cross product is noncommutative (\\$\vec a\times\vec b=-\bigl(\vec b\times\vec a\bigr)\\$), so you should have a way to specify order.

### Output

Their cross product, in a reasonable format, with each component accurate to four significant figures or \\$10^{-4}\\$, whichever is looser. Scientific notation is optional.

### Test cases

```
[3, 1, 4], [1, 5, 9]
[-11, -23, 14]

[5, 0, -3], [-3, -2, -8]
[-6, 49, -10]

[0.95972, 0.25833, 0.22140],[0.93507, -0.80917, -0.99177]
[-0.077054, 1.158846, -1.018133]

[1024.28, -2316.39, 2567.14], [-2290.77, 1941.87, 712.09]
[-6.6345e+06, -6.6101e+06, -3.3173e+06]

```

This is , so the shortest solution in bytes wins.

Maltysen posted a similar challenge, but the response was poor and the question wasn't edited.

# Answer
# Jelly, ~~14~~ ~~13~~ 12 bytes

```
;"s€2U×¥/ḅ-U

```

Try it online!

### How it works

```
;"s€2U×¥/ḅ-U Main link. Input: [a1, a2, a3], [b1, b2, b3]

;"           Concatenate each [x1, x2, x3] with itself.
             Yields [a1, a2, a3, a1, a2, a3], [b1, b2, b3, b1, b2, b3].
  s€2        Split each array into pairs.
             Yields [[a1, a2], [a3, a1], [a2, a3]], [[b1, b2], [b3, b1], [b2, b3]].
       ¥     Define a dyadic chain:
     U         Reverse the order of all arrays in the left argument.
      ×        Multiply both arguments, element by element.
        /    Reduce the 2D array of pairs by this chain.
             Reversing yields [a2, a1], [a1, a3], [a3, a2].
             Reducing yields [a2b1, a1b2], [a1b3, a3b1], [a3b2, a2b3].
         ḅ-  Convert each pair from base -1 to integer.
             This yields [a1b2 - a2b1, a3b1 - a1b3, a2b3 - a3b2]
           U Reverse the array.
             This yields [a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1] (cross product).

```

## Non-competing version (10 bytes)

OK, this is embarrassing, but the array manipulation language Jelly did not have a built-in for array rotation until just now. With this new built-in, we can save two additional bytes.

```
ṙ-×
ç_ç@ṙ-

```

This uses the approach from @AlexA.'s J answer. Try it online!

### How it works

```
ṙ-×     Helper link. Left input: x = [x1, x2, x3]. Right input: y = [y1, y2, y3].

ṙ-      Rotate x 1 unit to the right (actually, -1 units to the left).
        This yields [x3, x1, x2].
  ×     Multiply the result with y.
        This yields [x3y1, x1y2, x2y3].

ç_ç@ṙ-  Main link. Left input: a = [a1, a2, a3]. Right input: b = [b1, b2, b3].

ç       Call the helper link with arguments a and b.
        This yields [a3b1, a1b2, a2b3].
  ç@    Call the helper link with arguments b and a.
        This yields [b3a1, b1a2, b2a3].
_       Subtract the result to the right from the result to the left.
        This yields [a3b1 - a1b3, a1b2 - a2b1, a2b3 - a3b2].
    ṙ-  Rotate the result 1 unit to the right.
        This yields [a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1] (cross product).

```
> 16 votes

# Answer
## **LISP, 128 122 bytes**

Hi! This is my code:

```
(defmacro D(x y)`(list(*(cadr,x)(caddr,y))(*(caddr,x)(car,y))(*(car,x)(cadr,y))))(defun c(a b)(mapcar #'- (D a b)(D b a)))

```

I know that it isn't the shortest solution, but nobody has provided one in Lisp, until now :)

Copy and paste the following code here to try it!

```
(defmacro D(x y)`(list(*(cadr,x)(caddr,y))(*(caddr,x)(car,y))(*(car,x)(cadr,y))))(defun c(a b)(mapcar #'- (D a b)(D b a)))

(format T "Inputs: (3 1 4), (1 5 9)~%")
(format T "Result ~S~%~%" (c '(3 1 4) '(1 5 9)))

(format T "Inputs: (5 0 -3), (-3 -2 -8)~%")
(format T "Result ~S~%~%" (c '(5 0 -3) '(-3 -2 -8)))

(format T "Inputs: (0.95972 0.25833 0.22140), (0.93507 -0.80917 -0.99177)~%")
(format T "Result ~S~%" (c '(0.95972 0.25833 0.22140) '(0.93507 -0.80917 -0.99177)))

(format T "Inputs: (1024.28 -2316.39 2567.14), (-2290.77 1941.87 712.09)~%")
(format T "Result ~S~%" (c '(1024.28 -2316.39 2567.14) '(-2290.77 1941.87 712.09)))

```
> 11 votes

# Answer
# J, ~~27~~ 14 bytes

```
2|.v~-v=.*2&|.

```

This is a dyadic verb that accepts arrays on the left and right and returns their cross product.

Explanation:

```
         *2&|.     NB. Dyadic verb: Left input * twice-rotated right input
      v=.          NB. Locally assign to v
   v~-             NB. Commute arguments, negate left
2|.                NB. Left rotate twice

```

Example:

```
    f =: 2|.v~-v=.*2&|.
    3 1 4 f 1 5 9
_11 _23 14

```

Try it here

Saved 13 bytes thanks to randomra!
> 10 votes

# Answer
# Dyalog APL, 12 bytes

```
2⌽p⍨-p←⊣×2⌽⊢

```

Based on @AlexA.'s J answer and (coincidentally) equivalent to @randomra's improvement in that answer's comment section.

Try it online on TryAPL.

### How it works

```
2⌽p⍨-p←⊣×2⌽⊢  Dyadic function.
              Left argument: a = [a1, a2, a3]. Right argument: b = [b1, b2, b3].

         2⌽⊢  Rotate b 2 units to the left. Yields [b3, b1, b2].
       ⊣×     Multiply the result by a. Yields [a1b3, a2b1, a3b2].
     p←       Save the tacit function to the right (NOT the result) in p.
  p⍨          Apply p to b and a (reversed). Yields [b1a3, b2a1, b3a2].
    -         Subtract the right result (p) from the left one (p⍨).
              This yields [a3b1 - a1b3, a1b2 - a2b1, a2b3 - a3b2].
2⌽            Rotate the result 2 units to the left.
              This yields [a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1].

```
> 9 votes

# Answer
# C, 156 154 150 148 144 bytes

```
#include <stdio.h>
main(){float v[6];int i=7,j,k;for(;--i;)scanf("%f",v+6-i);for(i=1;i<4;)j=i%3,k=++i%3,printf("%f ",v[j]*v[k+3]-v[k]*v[j+3]);}

```

Not going to be winning any prizes for length, but thought I'd have a go anyway.

* Input is a newline- or space-delimited list of components (i.e. a1 a2 a3 b1 b2 b3), output is space-delimited (i.e. c1 c2 c3).
* Cyclically permutes the indices of the two input vectors to calculate the product - takes fewer characters than writing out the determinants!

Demo

Ungolfed:

```
#include <cstdio>
int main()
{
    float v[6];
    int i = 7, j, k;
    for (; --i; ) scanf("%f", v + 6 - 1);
    for (i = 1; i < 4; )
        j = i % 3,
        k = ++i % 3,
        printf("%f ", v[j] * v[k + 3] - v[k] * v[j + 3]);
}

```
> 6 votes

# Answer
## Haskell, 41 bytes

```
x(a,b,c)(d,e,f)=(b*f-c*e,c*d-a*f,a*e-b*d)

```

A straightforward solution.
> 4 votes

# Answer
# Bash + coreutils, 51

```
eval set {$1}*{$2}
bc<<<"scale=4;$6-$8;$7-$3;$2-$4"

```
* Line 1 constructs a brace expansion that gives the cartesian product of the two vectors and sets them into the positional parameters.
* Line 2 subtracts the appropriate terms; `bc` does the arithmetic evaluation to the required precision.

Input is as two comma-separated lists on the command-line. Output as newline-separated lines:

```
$ ./crossprod.sh 0.95972,0.25833,0.22140 0.93507,-0.80917,-0.99177
-.07705
1.15884
-1.01812
$

```
> 4 votes

# Answer
# MATL, 17 bytes

```
!*[6,7,2;8,3,4])d

```

First input is **a**, second is **b**.

**Try it online!**

### Explanation

```
!              % input b as a row array and transpose into a column array
*              % input a as a row array. Compute 3x3 matrix of pairwise products
[6,7,2;8,3,4]  % 2x3 matrix that picks elements from the former in column-major order
)              % apply index
d              % difference within each column

```
> 4 votes

# Answer
# Pyth, 16 bytes

```
-VF*VM.<VLQ_BMS2

```

Try it online: Demonstration

### Explanation:

```
-VF*VM.<VLQ_BMS2   Q = input, pair of vectors [u, v]
              S2   creates the list [1, 2]
           _BM     transforms it to [[1, -1], [2, -2]]
      .<VLQ        rotate of the input vectors accordingly to the left:
                   [[u by 1, v by -1], [u by 2, v by -2]]
   *VM             vectorized multiplication for each of the vector-pairs
-VF                vectorized subtraction of the resulting two vectors

```
> 4 votes

# Answer
# Jelly, 5 bytes

Takes input in the form \\$\[\[x\_1,x\_2\],\[y\_1,y\_2\],\[z\_1,z\_2\]\]\\$. If you want them to be two lists of x-y-z coordinates, just prepend `Z` to the beginning of the program.

```
ṁ4ÆḊƝ

```

Try it online!

Here is a PDF explanation in case SE markdown can't handle it.

---

### The cross-product in analytic form

Let \\$(x\_1,y\_1,z\_1)\\$ be the coordinates of \\$\vec{v\_1}\\$ and \\$(x\_2,y\_2,z\_2)\\$ be the coordinates of \\$\vec{v\_2}\\$. Their analytic expressions are as follows:

$$\boldsymbol{\vec{v\_1}}=x\_1\cdot \boldsymbol{\vec{i}}+y\_1\cdot \boldsymbol{\vec{j}}+z\_1\cdot\boldsymbol{\vec{k}}$$ $$\boldsymbol{\vec{v\_2}}=x\_2\cdot \boldsymbol{\vec{i}}+y\_2\cdot \boldsymbol{\vec{j}}+z\_2\cdot\boldsymbol{\vec{k}}$$

The only thing left to do now is to also write their cross-product in terms of its coordinates in the \\$Oxyz\\$ space.

$$\boldsymbol{\vec{v\_1}}\times \boldsymbol{\vec{v\_2}}=\left(x\_1\cdot \boldsymbol{\vec{i}}+y\_1\cdot \boldsymbol{\vec{j}}+z\_1\cdot\boldsymbol{\vec{k}}\right)\times\left(x\_2\cdot \boldsymbol{\vec{i}}+y\_2\cdot \boldsymbol{\vec{j}}+z\_2\cdot\boldsymbol{\vec{k}}\right)$$

Keeping in mind that: $$\boldsymbol{\vec{i}}\times \boldsymbol{\vec{j}}=\boldsymbol{\vec{k}}, \\:\\: \boldsymbol{\vec{i}}\times \boldsymbol{\vec{k}}=-\boldsymbol{\vec{j}}, \\:\\: \boldsymbol{\vec{j}}\times \boldsymbol{\vec{i}}=-\boldsymbol{\vec{k}}, \\:\\: \boldsymbol{\vec{j}}\times \boldsymbol{\vec{k}}=\boldsymbol{\vec{i}}, \\:\\: \boldsymbol{\vec{k}}\times \boldsymbol{\vec{i}}=\boldsymbol{\vec{j}}, \\:\\: \boldsymbol{\vec{k}}\times \boldsymbol{\vec{j}}=-\boldsymbol{\vec{i}}$$

After the necessary rearrangements and calculations:

$$\boldsymbol{\vec{v\_1}}\times \boldsymbol{\vec{v\_2}}=(y\_1z\_2-z\_1y\_2)\cdot \boldsymbol{\vec{i}}+(z\_1x\_2-x\_1z\_2)\cdot \boldsymbol{\vec{j}}+(x\_1y\_2-y\_1x\_2)\cdot \boldsymbol{\vec{k}}$$

### The close relationship with matrix determinants

There's an interesting thing to note here:

$$x\_1y\_2-y\_1x\_2=\left|\begin{matrix}x\_1 & y\_1 \\\ x\_2 & y\_2\end{matrix}\right|$$ $$z\_1x\_2-x\_1z\_2=\left|\begin{matrix}z\_1 & x\_1 \\\ z\_2 & x\_2\end{matrix}\right|$$ $$y\_1z\_2-z\_1y\_2=\left|\begin{matrix}y\_1 & z\_1 \\\ y\_2 & z\_2\end{matrix}\right|$$

Where we use the notation \\$\left|\cdot\right|\\$ for matrix determinant. Notice the *beautiful* rotational symmetry?

### Jelly code explanation

Well... not much to explain here. It just generates the matrix:

$$\left(\begin{matrix}x\_1 & y\_1 & z\_1 & x\_1 \\\ x\_2 & y\_2 & z\_2 & x\_2\end{matrix}\right)$$

And for each pair of neighbouring matrices, it computes the determinant of the matrix formed by joining the two.

```
ṁ4ÆḊƝ – Monadic Link. Takes input as [[x1,x2],[y1,y2],[z1,z2]].
ṁ4    – Mold 4. Cycle the list up to length 4, reusing the elements if necessary.
        Generates [[x1,x2],[y1,y2],[z1,z2],[x1,x2]].
    Ɲ – For each pair of neighbours: [[x1,x2],[y1,y2]], [[y1,y2],[z1,z2]], [[z1,z2],[x1,x2]].
  ÆḊ  – Compute the determinant of those 2 paired together into a single matrix.

```
> 4 votes

# Answer
# Python, ~~73~~ 48 bytes

Thanks @FryAmTheEggman

```
lambda (a,b,c),(d,e,f):[b*f-c*e,c*d-a*f,a*e-b*d]

```

This is based on the component definition of the vector cross product.

Try it here
> 3 votes

# Answer
# K5, ~~44~~ ~~40~~ ~~37~~ 32 bytes

Wrote this one quite a while ago and dusted it off again recently.

```
{{x[y]-x[|y]}[*/x@']'3 3\'5 6 1}

```

In action:

```
 cross: {{x[y]-x[|y]}[*/x@']'3 3\'5 6 1};

 cross (3 1 4;1 5 9)
-11 -23 14
 cross (0.95972 0.25833 0.22140;0.93507 -0.80917 -0.99177)
-7.705371e-2 1.158846 -1.018133

```

## Edit 1:

Saved 4 bytes by taking input as a list of lists instead of two separate arguments:

```
old: {m:{*/x@'y}(x;y);{m[x]-m[|x]}'(1 2;2 0;0 1)}
new: {m:{*/x@'y}x    ;{m[x]-m[|x]}'(1 2;2 0;0 1)}

```

## Edit 2:

Saved 3 bytes by computing a lookup table with base-decode:

```
old: {m:{*/x@'y}x;{m[x]-m[|x]}'(1 2;2 0;0 1)}
new: {m:{*/x@'y}x;{m[x]-m[|x]}'3 3\'5 6 1}

```

## Edit 3:

Save 5 bytes by rearranging application to permit using a tacit definition instead of a local lambda. Unfortunately, this solution no longer works in oK, and requires the official k5 interpreter. Gonna have to take my word for this one until I fix the bug in oK:

```
old: {m:{*/x@'y}x;{m[x]-m[|x]}'3 3\'5 6 1}
new: {{x[y]-x[|y]}[*/x@']     '3 3\'5 6 1}

```
> 3 votes

# Answer
# Ruby, 49 bytes

```
->u,v{(0..2).map{|a|u[a-2]*v[a-1]-u[a-1]*v[a-2]}}

```

Try it online!

Returning after 2 years, I shaved off 12 bytes by using how Ruby treats negative array indices. `-1` is the last element of the array, `-2` the second last etc.

# Ruby, 57

```
->u,v{(0..2).map{|a|u[b=(a+1)%3]*v[c=(a+2)%3]-u[c]*v[b]}}

```

**In test program**

```
f=->u,v{(0..2).map{|a|u[b=(a+1)%3]*v[c=(a+2)%3]-u[c]*v[b]}}

p f[[3, 1, 4], [1, 5, 9]]

p f[[5, 0, -3], [-3, -2, -8]]

p f[[0.95972, 0.25833, 0.22140],[0.93507, -0.80917, -0.99177]]

p f[[1024.28, -2316.39, 2567.14], [-2290.77, 1941.87, 712.09]]

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~38 33 25~~ 24 bytes

-1 byte thanks to @att.

```
Det@{a={i,j,},##}~D~{a}&

```

Try it online!
> 3 votes

# Answer
## ES6, 40 bytes

```
(a,b,c,d,e,f)=>[b*f-c*e,c*d-a*f,a*e-b*d]

```

44 bytes if the input needs to be two arrays:

```
([a,b,c],[d,e,f])=>[b*f-c*e,c*d-a*f,a*e-b*d]

```

52 bytes for a more interesting version:

```
(a,b)=>a.map((_,i)=>a[x=++i%3]*b[y=++i%3]-a[y]*b[x])

```
> 2 votes

# Answer
# Julia 0.7, ~~45~~ 39 bytes

```
f(a,b)=1:3 .|>i->det([eye(3)[i,:] a b])

```

Try it online!

Uses the determinant-based formula given in the task description.

Thanks to H.PWiz for -6 bytes.
> 1 votes

# Answer
# Pari/GP, 41 bytes

```
(a,b)->Vec(matdet(Mat([[x^2,x,1],a,b]~)))

```

Try it online!
> 1 votes

# Answer
## TI-BASIC, ~~75~~ ~~73~~ ~~71~~ 62 bytes

-4 bytes thanks to @MarcMush
-9 bytes using `Ans` instead of `Prompt`  and `Disp`

Not 62 characters -- TI-BASIC is tokenized.

```
:Prompt A
:{Ans(2)ʟA(3)-Ans(3)ʟA(2),Ans(3)ʟA(1)-Ans(1)ʟA(3),Ans(1)ʟA(2)-Ans(2)ʟA(1

```

Usage example, computing \\$\langle 1,2,3\rangle\times\langle 0,1,0\rangle\\$:

```
{1,2,3}:pgrmXPROD
A=?{0,1,0}
                  {⁻3 0 1}

```
> 1 votes

# Answer
# CSASM v2.5.0.2, 306 bytes

```
func a:
dup
dup
ldelem 0
pop $3
ldelem 1
pop $4
ldelem 2
pop $5
dup
dup
ldelem 0
pop $a
ldelem 1
pop $1
ldelem 2
pop $2
push $1
push $5
mul
push $2
push $4
mul
sub
push $2
push $3
mul
push $a
push $5
mul
sub
push $a
push $4
mul
push $1
push $3
mul
sub
push 3
newarr f32
pop $a
push $a
swap
stelem 2
push $a
swap
stelem 1
push $a
swap
stelem 0
push $a
ret
end

```

The function `a` expects two `~arr:f32` arrays representing the two 3D vectors on the stack before calling it.
\\$\vec a\\$ should be pushed to the stack first, then \\$\vec b\\$ should be pushed.
This function leaves an `~arr:f32` array on the stack which corresponds to \\$\vec c\\$.

**Explanation:**

```
; Input: two ~arr:f32 representing the two vectors
func a:
    ; stack: [ a, b, c ], [ d, e, f ]
    ; These numbers represent the coordinates of the two vectors for an easier explanation

    ; Duplicate the second vector twice
    dup
    dup

    ; stack: [ a, b, c ], [ d, e, f ], [ d, e, f ], [ d, e, f ]
    ; Store the elements in the array to the pre-defined registers $3, $4 and $5
    ldelem 0
    pop $3
    ldelem 1
    pop $4
    ldelem 2
    pop $5

    ; Duplicate the first vector twice
    dup
    dup

    ; stack: [ a, b, c ], [ a, b, c ], [ a, b, c ]
    ; Store the elements in the array to the pre-defined registers $a, $1 and $2
    ldelem 0
    pop $a
    ldelem 1
    pop $1
    ldelem 2
    pop $2

    ; Perform the algorithm: [ bf - ce, cd - af, ae - bd ]
    ; $a = a, $1 = b, $2 = c
    ; $3 = d, $4 = e, $5 = f

    ; bf - ce
    push $1
    push $5
    mul
    push $2
    push $4
    mul
    sub

    ; cd - af
    push $2
    push $3
    mul
    push $a
    push $5
    mul
    sub

    ; ae - bd
    push $a
    push $4
    mul
    push $1
    push $3
    mul
    sub

    ; Create the result array and store it in $a
    push 3
    newarr f32
    pop $a

    ; Store the resulting values from earlier into this new array
    ; "swap" swaps the top two values on the stack
    push $a
    swap
    stelem 2

    push $a
    swap
    stelem 1

    push $a
    swap
    stelem 0

    push $a
    ret
end

```
> 1 votes

# Answer
# MATLAB/Octave, 61 bytes.

Try it online!

```
f=@(a,b)[det([1,0,0;a;b]),det([0,1,0;a;b]),det([0,0,1;a;b])];

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~24~~ 21 bytes

```
D/@HodgeDual[1##]&

```

Try it online!

is `\[TensorWedge]` (U+F3DB).
> 1 votes

# Answer
# APL(NARS), 23 chars, 46 bytes

```
{((1⌽⍺)×5⌽⍵)-(5⌽⍺)×1⌽⍵}

```

test:

```
  f←{((1⌽⍺)×5⌽⍵)-(5⌽⍺)×1⌽⍵}
  (3 1 4) f (1 5 9)
¯11 ¯23 14
  (5 0 ¯3) f (¯3 ¯2 ¯8)
¯6 49 ¯10
  (0.95972 0.25833 0.22140) f (0.93507 ¯0.80917 ¯0.99177)
¯0.0770537061 1.158846002 ¯1.018133265
  (1024.28 ¯2316.39 2567.14) f (¯2290.77 1941.87 712.09)
¯6634530.307 ¯6610106.843 ¯3317298.117

```
> 0 votes

---
Tags: code-golf, math, linear-algebra
---


title: Imtiaz Germain Primes

text:
# Question
Title: Imtiaz Germain Primes
## Description

"Imtiaz Germain primes" is not a technical name in Mathematics, but my weird creation, in the memoir of the famous mathematician Sophie Germain. These primes can be generated by the following process:

```
1. Take a Safe prime
2. Apply 2p + 1 on it to obtain a composite number
3. Apply 2p + 1 once more to obtain a prime number

```

The idea can be further illustrated in the example.

## Example

We check if `3` is a Sophie Germain prime. It has a safe prime `7` using `2p+1` so `3` is a Sophie Germain prime and can/cannot be an Imtiaz Germain prime. We take the safe prime, apply `2p+1` on it, and get `15` which must be composite according to the second step of the description, applying the same, we must get a prime next, which is `31` so `3` is an Imtiaz Germain prime. All Imtiaz Germain primes below 100M are available in Chapter 1 of the book I wrote here.

## Task

Write a program, which inputs any number, and mentions all Imtiaz Germain primes below the number. As long as fulfills the full output, you may output the Imtiaz Germain primes in reversed order. Since it is code golf, the shortest code in bytes win, if bytes are equated then the earliest posted program wins.

## Test Cases

```
10 => 3
1500 => 3 23 29 53 113 233 293 419 593 653 659 683 1013 1103 1223 1439
10000 => 3 23 29 53 113 233 293 419 593 653 659 683 1013 1103 1223 1439 1559 1583 1973 2039 2273 2339 2549 2753 3299 3359 3593 3803 3863 4019 4409 4733 4793 4919 4943 5003 5279 5639 6173 6263 6269 6323 6563 6983 7433 7643 7823 8243 8273 8513

```

# Answer
> 6 votes
# 05AB1E, ~~14~~ 13 bytes

```
ÅPʒ>3Lo*<pāÉQ

```

Try it online!

-1 thanks to @Kevin Cruijssen

~~I found a bunch of different ways for 14 bytes, but I can't find any 13 bytes solution ):~~

```
Lʒ>3Ýo*<pā3ÊQ
ÅPʒ>3Lo*<pJC5Q
ÅPʒ>3Lo*<pJƵ0Q
ÅPʒ>3Lo*<p2β5Q
ÅPʒ>3Lo*<p3LÉQ
ÅPʒ>3Lo*<pā+ÈP
Lʒ>3Ýo*<pJC13Q
Lʒ>3Ýo*<p2β13Q
Lʒ>3Ýo*<pJŽ4ιQ
Lʒ>3Ýo*<p4L3ÊQ

```

## Explanation

```
ÅP         generate all primes up to (and including) the input number
ʒ          only keep those such that
>          p+1
3L         the list [1, 2, 3]
o          2^[1, 2, 3] = [2, 4, 8]
*          times p+1 = [2p+2, 4p+4, 8p+8]
<          -1 = [2p+1, 4p+3, 8p+7]
p          is prime
ā          length range, [1, 2, 3]
É          is odd? [1, 0, 1]
Q          equal to the results of is prime

```

# Answer
> 5 votes
# Vyxal, ~~13~~ 12 bytes

```
'‡d›↔4ẎæB13=

```

Try it Online!

If I've understood the challenge correctly, for a number to be Imtiaz Germain, it has to first be prime, and applying `2p+1` 3 times must produce the required pattern. Hence, the list `[p, 2p + 1, 2(2p + 1) + 1, 2((2(2p + 1) + 1) + 1)]` must equal `[1, 1, 0, 1]`, which is `13` when converted from binary.

Accidentally the same algorithm as Jelly, which was posted while I was writing the explanation :p

## Explained

```
'‡d›↔4ẎæB13=
'             # From the range [1, input], keep numbers N where:
     4Ẏ       #   the first 4 items of
 ‡d›↔         #   applying `lambda x: 2 * x + 1` until fixed-point (yes it's infinite, but lazy evaluation means it doesn't get stuck here)
       æ      #   tested for primality
        B     #   converted from binary
         13=  #   equals 13. This works for the reason explained in the introduction.

```

# Answer
> 4 votes
# Jelly, 13 bytes

```
Ḥ‘$3Ð¡ẒḄ=ʋƇ13

```

Try it online!

## How it works

```
Ḥ‘$3Ð¡ẒḄ=ʋƇ13 - Main link. Takes an integer n on the left
         ʋ 13 - Last 4 links as a dyad f(i, 13):
  $           -   Last 2 links as a monad g(i):
Ḥ             -     2i
 ‘            -     2i+1
   3Ð¡        -   Collect [i, g(i), g(g(i)), g(g(g(i)))]
      Ẓ       -   Is prime?
       Ḅ      -   Convert from binary
        =     -   Does that equal 13? I.e. is the pattern [prime, prime, composite, prime]?
          Ƈ   - Filter 1 ≤ i ≤ n by f(i, 13)

```

# Answer
> 4 votes
# Retina 0.8.2, 107 bytes

```
.+
$*
1
8$*
1{8}
$`7$*1¶
A`^(11+)\1+$
1(1?)
$1
G`^(11+)\1+$
1(1?)
$1
A`^(11+)\1+$
1(1?)
$1
A`^(11+)\1+$
%`1

```

Try it online! Explanation:

```
.+
$*

```

Convert to unary.

```
1
8$*

```

Multiply by `8`.

```
1{8}
$`7$*1¶

```

Generate all numbers of the form `8k+7` less than that.

```
A`^(11+)\1+$

```

Delete all composite numbers.

```
1(1?)
$1

```

Integer divide by `2`.

```
G`^(11+)\1+$

```

Delete all prime numbers.

```
1(1?)
$1

```

Integer divide by `2`.

```
A`^(11+)\1+$

```

Delete all composite numbers.

```
1(1?)
$1

```

Integer divide by `2`.

```
A`^(11+)\1+$

```

Delete all composite numbers.

```
%`1

```

Convert the results to decimal.

# Answer
> 3 votes
# Arturo, ~~67~~ ~~65~~ 64 bytes

```
$=>[select..1&'x[map@++repeat[1+2*<=]3x=>prime?=@[<=x>0x=0x>0]]]

```

Try it

```
$=>[                        ; a function
    select 1..& 'x [        ; select numbers from 1 to <input> and assign current elt to x
        map [...] => prime? ; map over a block for primality
        @                   ; evaluate a block
        ++ [...] x          ; append x to the end of a block
        repeat [1+2*<=] 3   ; create the block [1+2*<=1+2*<=1+2*<=]
        =                   ; is this equal to...
        @[<=x>0x=0x>0]      ; shortest way I could think of to make [true true false true]
    ]                       ; end select
]                           ; end function

```

# Answer
> 2 votes
# Thunno `+`, \\$ 17 \log\_{256}(96) \approx \\$ 13.99 bytes

```
g1+4R2@*1-NiJB13=

```

Attempt This Online!

#### Explanation

```
g1+4R2@*1-NiJB13=  # Implicit input: + flag adds one
g                  # Filter the range by the following:   p
 1+                #  Add one                             p+1
   4R              #  Push range(4)                       p+1, [0, 1, 2, 3]
     2@            #  Push 2 ** each                      p+1, [1, 2, 4, 8]
       *           #  Multiply each                       [p+1, 2p+2, 4p+4, 8p+8]
        1-         #  Subtract one                        [p, 2p+1, 4p+3, 8p+7]
          Ni       #  Are they prime?
            J      #  Join into a single string
             B     #  Convert from binary
              13=  #  Equals 13 (0b1101)?

```

# Answer
> 2 votes
# JavaScript (ES6), 79 bytes

Returns a list.

```
f=n=>--n?(g=d=>q%--d?g(d):(q-=~q,d<2))(q=n)&g(q)&!g(q)&g(q)?[...f(n),n]:f(n):[]

```

Try it online!

### Commented

```
f = n =>         // n = upper bound
--n ?            // decrement n; if it's not 0:
  ( g = d =>     //   g is a helper function taking d = q
    q % --d ?    //   decrement d; if d is not a divisor of q:
      g(d)       //     do recursive calls until it is
    :            //   else:
      ( q -= ~q, //     update q to 2q + 1
        d < 2    //     return true if d = 1
      )          //     i.e. the original q was prime
  )(q = n) &     //   test n (should be prime)
  g(q) &         //   test 2n+1 (should be prime)
  !g(q) &        //   test 4n+3 (should be composite)
  g(q)           //   test 8n+7 (should be prime)
  ?              //   if all tests pass:
    [ ...f(n),   //     append the result of a recursive call
      n          //     followed by n
    ]            //
  :              //   else:
    f(n)         //     just do a recursive call
:                // else:
  []             //   stop

```

---

# JavaScript (V8), 75 bytes

Prints the terms in reverse order.

```
n=>{for(;--n;)(g=d=>q%--d?g(d):(q-=~q,d<2))(q=n)&g(q)&!g(q)&g(q)&&print(n)}

```

Try it online!

# Answer
> 2 votes
# , ~~27~~ 26 bytes

```
[:I.0</@:p:0 1 7 3*&.>:/i.

```

Try it online!

* `i.`: Make a list of the integers from 0 (inclusive) to the given number (exclusive).
* `0 1 7 3` `*` `&.` `>:` `/`:
    + First, apply `>:` (increase by 1) to both `0 1 7 3` and the list from above.
    + Then, multiply (`*`) them; `/` modifies the rank to produce a table of values.
    + Finally, apply the inverse of `>:`, decreasing the values by 1.
* `0` `<` `/` `@:` `p:`:
    + `0` `p:` produces 0 for primes and 1 for non-primes.
    + Then (`@:`, composition), `<` `/` inserts (`/`) `<` ('less than') between items, turning `a b c d` into `a < (b < (c < d))`.
    For Boolean (0/1) arguments, `a < b` is 1 if and only if `a` is 0 and `b` is 1. Therefore, the result of this is 1 precisely when its input is `0 0 0 1`.
* `[:` `I.`: Make a list of the indices of 1s. A cap (`[:`) is used to make this monadic.

# Answer
> 2 votes
# Python, ~~118 114 112~~ 111 bytes

```
lambda n:[i for i in range(n+1)if[*map(lambda x:all(x%k for k in range(2,x)),[i,i-~i,4*i+3,8*i+7])]==[1,1,0,1]]

```

Attempt This Online!

## Python, ~~123 119~~ 118 bytes

```
f=lambda n,i=2:i<n and([*map(lambda x:all(x%k for k in range(2,x)),[i,i-~i,4*i+3,8*i+7])]==[1,1,0,1])*[i]+f(n,i+1)or[]

```

Attempt This Online!

Probably can be improved.

*-1 from both by using a trick from @KevinCruijssen's Java answer*

#### Commented

```
lambda n: [i for i in range(n + 1) if  # Anonymous function, taking an integer n
                                       # Filter [0..n] by the following:
  [*map(                               # Apply a function to each item of a list:
lambda x:all(x%k for k in range(2, x)) #  Prime check function
    , [i, i-~i, 4*i+3, 8*i+7])         #  Applied to the list [i, 2*i+1, 4*i+3, 8*i+7]
  ] == [1, 1, 0, 1]]                   # i, 4*i+3, and 8*i+7 are prime, and 2*i+1 is not

```

```
f=lambda n, i=2: i<n and (             # Define a recursive function, f, taking an integer n,
                                       # and using an integer, i, as the recursive variable
                                       # If i is less than n:
    [...] == [1, 1, 0, 1]              #  (same as above)
  ) * [i] + f(n, i+1) or []            #  If true, add i. Make a recursive call with i+1
                                       #  Stop if i >= n

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 61 bytes

```
Select[Range@#,Boole@PrimeQ@NestList[2#+1&,#,3]=={1,1,0,1}&]&

```

Try it online!

# Answer
> 2 votes
# Java 8, ~~133~~ ~~126~~ 123 bytes

```
i->{for(;i-->3;)if(p(i)+p(i-~i)+p(8*i+7)<4&p(4*i+3)>1)System.out.println(i);};int p(int i){for(int k=i;k%--i>0;);return i;}

```

Outputs each Imtiaz Germain prime on a separated newline in reversed order.

Try it online.

**Explanation:**

```
i->{                          // Method with integer parameter and no return-type
  for(;i-->3;)                //  Loop `i` in the range (input,3]:
    if(p(i)                   //   If `i` is a prime number
       +p(i-~i)               //   and `2i+1` is a prime number
       +p(8*i+7)              //   and `8i+7` is a prime number
       <4                     //   (by checking if all three are 0 or 1)
       &p(4*i+3)              //   and `4i+3` is NOT a prime number
        >1)                   //   (by checking whether it's NOT 0 or 1)
      System.out.println(i);} //    Print `i` with trailing newline

// Separated method with integer as both parameter and return-type,
// to check whether the given number (≥2) is a prime number (0 or 1)
int p(int i){
  for(int k=i;                //  Set `k` to the given integer `i`
      k%--i>0;);              //  Decrease `i` before every iteration with `--i`
                              //  Keep looping as long as `k` is NOT divisible by `i`
  return i;}                  //  After the loop, return `i`
                              //  (if it's 1 or 0, it means it's a prime number)

```

# Answer
> 2 votes
# Charcoal, 25 bytes

```
ＩΦＮ⁼1101⭆⊖Ｅ⁴×⊕ιＸ²λ⬤…²λ﹪λν

```

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

```
  Ｎ                         Input limit
 Φ                          Filter on implicit range
           ⁴                Literal integer 4
          Ｅ                 Map over implicit range
              ι             Outer value
             ⊕              Incremented
            ×               Multiplied by
                ²           Literal integer `2`
               Ｘ            Raised to power
                 λ          Inner value
         ⊖                  Vectorised decrement
        ⭆                   Map over values and join
                   …        Range from
                    ²       Literal integer `2`
                     λ      To inner value
                  ⬤         All values satisfy
                       λ    Inner value
                      ﹪     Modulo i.e. is not a multiple of
                        ν   Innermost value
   ⁼                        Equals
    1101                    Literal string `1101`
Ｉ                           Cast to string
                            Implicitly print

```

# Answer
> 2 votes
# , ~~78~~ 75 bytes

*Edit: -1 byte thanks to pajonk*

```
f=\(x)if(x)c(x[all(sapply(x*2^(0:3)-1,\(y)sum(!y%%2:y)<2)-!-2:1)]-1,f(x-1))

```

Attempt This Online!

`n`, `2*n+1`, `2*(2*n+1)+1` and `2*(2*(2*n+1)+1)+1` can be reformulated as `x*2^(0:3)-1` using `x=n+1`.
So, we just check these for primes, and test that the desired result (`TRUE TRUE FALSE TRUE`) is always different to `!-2:1` (`FALSE FALSE TRUE FALSE`), returning `x-1` if so.

# Answer
> 2 votes
# Raku, 50 bytes

```
{grep {is-prime $_&2*$_+1&8*$_+7&none 4*$_+3},^$_}

```

Try it online!

* `grep { ... }, ^$_` returns all nonnegative integers less than the input argument `$_` that satisfies the bracketed predicate.
* `$_ & 2*$_+1 & 8*$_+7 & none 4*$_+3` is a conjunction of `$_`, the number being tested, as well as twice that number plus one, eight times that number plus seven, and a `none` junction of four times that number plus three.
* `is-prime` tests the primality of that junction, returning a truthy value if `$_`, `2*$_+1`, and `8*$_+7` are all prime, and `4*$_+3` is NOT prime.

# Answer
> 1 votes
# Factor \+ `combinators.extras math.primes`, 78 bytes

```
[ iota [ [ dup 2 * 1 + ] thrice 4array [ prime? ] map { t t f t } = ] filter ]

```

Try it online!

* `iota [ ... ] filter` select numbers up to input
* `[ dup 2 * 1 + ] thrice` push `n, n*2+1, tos*2+1, tos*2+1` to the stack
* `4array` gather them into a sequence
* `[ prime? ] map` primality test each element
* `{ t t f t } =` is it equal to `{ t t f t }`?

# Answer
> 0 votes
# PARI/GP, 145 bytes

can find all desirable numbers up to 1e7 under the time limit in TIO.

Golfed version, try it online!

```
f(n)={seq=vector(4,i,0);for(i=1,4,seq[i]=n;n=2*n+1;);[isprime(s)|s<-seq]==[1,1,0,1]}
g(N)={res=[];forprime(p=2,N,if(f(p),res=concat(res,p)));res}

```

Ungolfed version

```
is_satisfying_condition(n) = {
  seq = vector(4, i, 0);
  for(i=1, 4, seq[i] = n; n = 2*n + 1;);
  return([isprime(s) | s <- seq] == [1, 1, 0, 1]);
}

select_primes(N) = {
  result = [];
  forprime(p = 2, N, if(is_satisfying_condition(p)==1, result = concat(result, p)));
  return(result);
}

g = select_primes(10000);
print(g);

```

---
Tags: code-golf, number, number-theory, primes
---


title: How long to carry sort?

text:
# Question
Title: How long to carry sort?
Carry sort is an \\$O(n)\\$ "sorting" algorithm. Here's how it works. The algorithm moves left to right along a list. As it traverses a list it "carries" a single item, the largest item it has encountered so far. Once it encounters a larger item it picks up that item and drops the item it is already carrying in place. When it gets to the end it drops the item that it is carrying (the largest item in the list) at the end of the list.

### Worked example

Here we are going to apply carry sort to the list `[1,2,0,3,2,1,2,4,3]`

```
[1,2,0,3,2,1,2,4,3]
^

[ 2,0,3,2,1,2,4,3]
 ^
 1
[ 1,0,3,2,1,2,4,3]
  ^
  2
[ 1,0,3,2,1,2,4,3]
    ^
    2
[ 1,0,2,2,1,2,4,3]
      ^
      3
[ 1,0,2,2,1,2,4,3]
        ^
        3
[ 1,0,2,2,1,2,4,3]
          ^
          3
[ 1,0,2,2,1,2,4,3]
            ^
            3
[ 1,0,2,2,1,2,3,3]
              ^
              4
[ 1,0,2,2,1,2,3,3]
                ^
                4
[ 1,0,2,2,1,2,3,3,4]
                  ^

```

Here we can see that carry sort has definitely made the list *more* sorted than it was, but it's not perfectly sorted.

## Task

If you repeatedly apply carry sort to a list it will eventually sort the list. Your task is to take a list of integers and determine the minimum number of passes required for carry sort to sort the input list in ascending order.

This is so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

```
[] -> 0
[-2,3,9] -> 0
[4,1,2,3] -> 1
[1,3,2,4] -> 1
[4,3,2,1] -> 3
[0,-1,-2,-3,-4] -> 4
[1,2,0,3,2,1,2,4,3] -> 3

```

# Answer
# , ~~41~~ ~~40~~ 35 bytes

*Edit: -1 byte thanks to @Giuseppe and -5 bytes thanks to @Dominic van Essen.*

```
\(x)max(order(y<-c(x,Inf))-seq(!y))

```

Attempt This Online!

The idea is that we look how much to the right are the elements displaced in the input versus the sorted array, and take the maximum. This is because moving elements to the right is easy and to the left is hard (moving one space to the left requires exactly one pass).

Example:

```
x =               1  2  0  3  2  1  2  4  3
sort(x) =         0  1  1  2  2  2  3  3  4
order(x) =        3  1  6  2  5  7  4  9  8 # positions of the input in the sorted array (sort(x) === x[order(x)])
order(x)-seq(x) = 2 -1  3 -2  0  1 -3  1 -1 # how far to the right is input vs sorted
take max -> answer

```
> 11 votes

# Answer
# JavaScript (ES6), 50 bytes

This is inspired by @pajonk's excellent answer. But instead of explicitly sorting the input array, we subtract from the position of each element the number of elements that are less than or equal to it.

```
a=>a.map(m=(v,i)=>a.map(V=>i-=V<=v)|m>++i?0:m=i)|m

```

Try it online!

### Commented

```
a =>         // a[] = input array
a.map(m =    // initialize m to a non-numeric value
(v, i) =>    // for each value v at position i in a[]:
  a.map(V => //   for each value V in a[]:
    i -=     //     decrement i if
      V <= v //     V is less than or equal to v
  ) |        //   end of inner map()
  m > ++i ?  //   increment i; if m is greater than i:
    0        //     do nothing
  :          //   else:
    m = i    //     update m to i
) | m        // end of outer map(); return m

```

---

# JavaScript (ES6), 66 bytes

-1 if we return *false* for 0.

```
f=A=>([m,...a]=[...A,,],a=a.map(v=>v<m?v:m+![m=v]))==A+''?0:1+f(a)

```

Try it online!

### Commented

```
f = A =>           // recursive function taking the input array A[]
(                  // split into:
  [ m,             //   m   = first element
       ...a ] =    //   a[] = all remaining elements
                   // the array defined as:
  [ ...A,, ],      //   A[] padded with a trailing undefined value
  a = a.map(v =>   // for each element v in a[]:
    v < m ?        //   if v is less than m:
      v            //     leave v unchanged
    :              //   else:
      m + ![m = v] //     put m here and update m to v
  )                // end of map(); save the result in a[]
) == A + '' ?      // if a[] is equal to A[]:
  0                //   stop
:                  // else:
  1 +              //   increment the final result and do
  f(a)             //   a recursive call with the updated array

```
> 7 votes

# Answer
# Charcoal, ~~53~~ ~~33~~ 31 bytes

```
≔⟦⟧ηＷ⁻θυ«⊞υ⌊ιＦ⌕Ａθ⌊ι⊞η⁻κＬη»Ｉ∨⌈η⁰

```

Try it online! Link is to verbose version of code. Explanation: Having written my comment, I finally got around to implementing a version using grade up.

```
≔⟦⟧η

```

Start with an empty list.

```
Ｗ⁻θυ«

```

Repeat until the list has been graded.

```
⊞υ⌊ι

```

Track the elements already graded.

```
Ｆ⌕Ａθ⌊ι⊞η⁻κＬη

```

Save the offsets of each matching element in the list.

```
»Ｉ∨⌈η⁰

```

Output the maximum, or `0` if the list was empty.
> 5 votes

# Answer
# Excel (ms365), 137 bytes

Within the windows version one can create their own named function using the named manager. Here we will create a function named 'Z':

```
=LAMBDA(a,b,IF(AND(a=SORT(a)),b,Z(DROP(REDUCE({0;0},a,LAMBDA(c,d,LET(y,TAKE(c,-1),IF(d>y,VSTACK(c,d),VSTACK(DROP(c,-1),d,y))))),2),b+1)))

```

Now you can call 'Z' using:

```
=Z(<YourVerticalRange>,0)

```

For example:

---

If one would like to try this online, I tried to mimic this using Google Sheets:

```
=LAMBDA(a,b,IF(INDEX(AND(a=SORT(a))),b,Z(QUERY(REDUCE({0;0},a,LAMBDA(c,d,LET(y,INDEX(c,COUNT(c)),IF(d>y,VSTACK(c,d),VSTACK(QUERY(c,"limit "&COUNT(c)-1),d,y))))),"offset 2"),b+1)))(a,b)

```
> 4 votes

# Answer
# Vyxal, 25 bytes

```
{:ÞṠ¬|÷^!(~<ß$‟)„$‟^W&›}¥

```

Try it Online!

Count how many times the sweep is applied until it's sorted.
> 3 votes

# Answer
# 05AB1E, ~~19~~ 15 bytes

```
ΔZªćUεDX›iXsU]N

```

-4 bytes porting *@Arnauld*'s JavaScript answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Original 19 bytes answer:**

```
Δā<ü2vDyè©`›i®yRǝ]N

```

Try it online or verify all test cases.

**Explanation:**

```
Δ                   # Loop until the result no longer changes (aka, until it's sorted),
                    # using the (implicit) input-list
 Z                  #  Push the maximum of the list (without popping)
  ª                 #  Append this maximum to the list
   ć                #  Extract head; pop and push remainder-list and first item
                    #  separately to the stack
    U               #  Pop and store this first item in variable `X`
     ε              #  Map over the remainder-list:
      D             #   Duplicate the current integer
       X›i          #   Pop the copy, and if it's larger than `X`:
          X         #    Push `X`
          sU        #    Swap, pop, and store the current integer as new `X`
                    #   (implicit else: keep the current integer, hence the need for the
                    #   `D`uplicate before the if-statement)
]                   # Close the if-statement; map; and changes-loop
 N                  # Push the final (0-based) index of the changes-loop
                    # (which is output implicitly as result)

```

```
Δ                ]N # Same as above:
 ā                  #  Push a list in the range [1,length] (without popping)
  <                 #  Decrease it to 0-based range [0,length)
   ü2               #  Get all overlapping pairs of this index-list
     v              #  Pop and loop over each index-pair `y`:
      Dyè           #   Get the values at indices `y` in a copy of the current list
         ©          #   Store this pair of values in variable `®` (without popping)
          `›i       #   Pop the pair, and if the first is larger than the second:
             ®yRǝ   #    Swap the values at the index-pair `y` within the list:
             ®      #     Push values-pair `®`
              yR    #     Push the reversed of index-pair `y`
                ǝ   #     Insert the values at those reversed indices to the list

```
> 3 votes

# Answer
# , ~~90~~ 82 bytes

*Edit: -8 bytes thanks to Giuseppe*

```
f=\(l)`if`(is.unsorted(l),{l[c(F,d,T)]=l[c(T,d<-diff(cummax(l))>0)];f(l[-1])+1},0)

```

Attempt This Online!

Recursively performs carry-sort and counts how many times it's needed until the argument is sorted.

Take a look at pajonk's much more elegant and shorter approach that simply calculates the right answer directly, though...
> 3 votes

# Answer
# Ruby, ~~47 ...~~ 41 bytes

```
->l{l.map{*l,c=l;l.count{|a|a>c}}.max||0}

```

Try it online!
> 3 votes

# Answer
# Python \+ numpy, ~~67~~ 65 bytes

*Edit: -2 bytes thanks to @ovs.*

```
lambda x:len(x)and max(argsort(x)-r_[:len(x)])
from numpy import*

```

Attempt This Online!

Port of my R answer.
> 3 votes

# Answer
# Vyxal `G`, ~~9 7~~ 6 bytes

```
⇧$ẏ-0J

```

Try it Online! or verify all test cases

Port of @pajonk's R answer

*-2 thanks to @Neil*

#### Explanation

```
⇧$ẏ-0J  # Implicit input
⇧       # Grade up: push the indices which will sort the list
 $ẏ     # Swap and push a list in the range [0, len(input))
   -    # Subtract the range from the grade up list
    0J  # Append a 0 to this list
        # G flag gets the maximum
        # Implicit output

```

Old:

```
[⇧›$ż-G|0  # Implicit input
[          # If it isn't empty:
 ⇧         #  Grade up: push the indices which will sort the list
  ›        #  Increment it to make it one-indexed
   $ż      #  Swap and push a list in the range [1, len(input)]
     -     #  Subtract the range from the grade up list
      G    #  Pop and push the maximum item
       |0  # Otherwise, push 0
           # Implicit output

```
> 2 votes

# Answer
# BQN, 7 bytesSBCS

Another port of pajonks R answer.

```
0⌈´⍋-⊒˜

```

Run online!
> 2 votes

# Answer
# Jelly, 4 bytes

```
Ụ_JṀ

```

A monadic Link that accepts the list and yields the number of required passes.

**Try it online!**

### How?

Just as pajonk's R answer, but with automatic `0` as the maximum of an empty list.

```
Ụ_JṀ - Link: List, A
Ụ    - grade-up (A) -> list of 1-indexed indices of the sorted values
  J  - range of length (A) -> 1-based indices = [1..length(A)]
 _   - (graded indices) subtract (indices)
   Ṁ - maximum (the maximum of an empty list is 0)

```
> 2 votes

# Answer
# , 14 bytes

```
[:>./0,/:-i.@#

```

Try it online!

## Explanation

Same approach as a few answers.

```
[:>./0,/:-i.@#
       /:        grade up input
         -       and subtract from each position
          i.@#   the corresponding element in the range [0, size)
     0,          prepend zero (edge case of empty lists)
[:               and then
  >./            take the maximum of that array (which is otherwise -∞ for empty lists)

```
> 2 votes

# Answer
# Factor, 46 bytes

```
[ arg-sort [ - ] map-index 0 suffix supremum ]

```

Try it online!

Port of @TheThonnu's Vyxal answer.

* `arg-sort` Get the indices that would sort the sequence. (aka grade up/inverse permutation)
* `[ - ] map-index` Subtract each index from its element.
* `0 suffix` Append a 0.
* `supremum` Get the maximum element.
> 1 votes

# Answer
# Desmos, ~~52~~ 48 bytes

```
s=[0...x.length]
f(x)=max(sort(s,join(0/0,x))-s)

```

Try it on Desmos!

One of the only times where 0/0 is useful. Based on pajonk's answer.
-4 bytes thanks to Aiden Chow.
> 1 votes

# Answer
# APL(Dyalog Unicode), 9 bytes SBCS

```
⌈/0,⍋-⍳∘≢

```

Try it on APLgolf!

### Explanation

```
⌈/0,⍋-⍳∘≢
        ≢       ⍝ length of the input
       ⍳∘        ⍝ create a range from 1 to the length
      -         ⍝ subtract that list from...
    ⍋          ⍝ the input graded up
  0,            ⍝ prepend a zero
⌈/              ⍝ get the maximum of the resulting list

```

Just for reference, this is what the train tree looks like:

```
  ┌─┴─┐
  / ┌─┼───┐
┌─┘ 0 , ┌─┼─┐
⌈       ⍋ - ∘
           ┌┴┐
           ⍳ ≢

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 66 bytes

---

Golfed version, try it online!

```
x~Append~∞//Ordering//Max[#-Range@*Length@#/.Thread[Not@#->1]]&;

```

Ungolfed version

```
f[x_List] := Module[{y, yOrder, seqY},
  y = Append[x, Infinity];
  yOrder = Ordering[y];
  seqY = Range[Length[yOrder]] /. Thread[Not[yOrder] -> 1];
  Max[yOrder - seqY]
]

(* function testing *)
f[{}]//Print (* -> 0 *)
f[{-10}]//Print  (* -> 0 *)
f[{-2, 3, 9}]//Print  (* -> 0 *)
f[{4, 1, 2, 3}]//Print  (* -> 1 *)
f[{1, 3, 2, 4}]//Print  (* -> 1 *)
f[{4, 3, 2, 1}]//Print  (* -> 3 *)
f[{0, -1, -2, -3, -4}]//Print  (* -> 4 *)
f[{1, 2, 0, 3, 2, 1, 2, 4, 3}]//Print  (* -> 3 *)
f[{1, 1, 2, 2, 3, 3, 4, 4}]//Print  (* -> 0 *)
f[{4, 4, 3, 3, 2, 2, 1, 1}]//Print  (* -> 6 *)

```
> 1 votes

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


title: Guess The Array

text:
# Question
Title: Guess The Array
Problem author: https://stats.ioinformatics.org/people/5815

You are given a system with a hidden permutation of the numbers \\$1, 2, 3, \ldots, n\\$. Your task is to guess this permutation by asking the system a series of questions.

Each question consists of providing the system with a permutation of the numbers \\$1, 2, 3, \ldots, n\\$. The system will respond with the length of the longest common subsequence between your permutation and the hidden permutation.

A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, \\$1, 2\\$ would be considered a subsequence of \\$1, 3, 2\\$.

You must guess the hidden permutation using at most \\$n^2\\$ questions. If you exceed this limit, the system will kill your program.

You can pick an interaction protocol from the two below.

Interaction protocol 1:

* Communication with the system occurs over standard input and standard output.
* At first, the system provides you the number \\$n\\$, which is the length of the array.
* To ask the system, the program should write a single permutation of the numbers \\$1, 2, 3, \ldots, n\\$ to the standard output, followed by a newline character.
* The system will respond with a single integer, which is the length of the longest common subsequence between the permutation provided by the program and the hidden permutation.
* **You are done when you receive the number \\$n\\$ from the system.**

Interaction protocol 2:

* You can take a number \\$n\\$ and a black box function as input. The black box function `f(user_input)` calculates the longest common subsequence between `user_input` and the permutation that the system holds, provided that `user_input` is also a permutation of \\$1, 2, 3, \ldots, n\\$.
* **You are done when you receive \\$n\\$ from the black box function.**
* A call to the black box function constitutes asking the system and counts towards your question limit.

In both interaction protocols, if you want, you can communicate by passing permutations of \\$0, 1, 2, 3, \ldots, n - 1\\$ instead.

### After receiving \\$n\\$, what can I do?

The system stops monitoring your program. Your program can crash, loop forever or ask additional questions. You already guessed the permutation, congratulations.

Sample interaction:

```
Hidden permutation: 3 2 1
---
Input: 3

Output: 1 2 3

Input: 1

Output: 2 1 3

Input: 2

Output: 3 1 2

Input: 2

Output: 3 2 1

Input: 3

```

Now you've successfully guessed the permutation.

This is , shortest code wins.

# Answer
# , ~~112~~ ~~110~~ 101 bytes

```
\(f,n,g=1:n)for(i in g)for(j in g)if((d=f(b<-c((a=g[-match(i,g)])[1:j-1],i,tail(a,n-j))))>F){F=d;g=b}

```

Attempt This Online!

Uses all `n^2` guesses, even if it receives a response of `n` first. No output (but the ATO link forces the 'black box' function to print its response each time so you can at least see something!).
It's pretty efficient: if the 'black box' doesn't need to print its response (try it here), it guesses an array of 50 elements in a few seconds.

**How?**
Starts with a guess of `1..n`. Then tries all positions of each digit, updating the guess-so-far whenever the 'black box' output improves, so that each digit gets placed into its correct position in the growing longest-common-subsequence-so-far. This uses exactly `n^2` queries to the 'black box' function, with the output of `n` usually received for one of the queries of the last digit tried (unless it was already in the last position in the secret permutation).
> 4 votes

# Answer
# Pyth, 71 bytes

```
M?&GHeS[gGPHgPGH*qeGeHhgPGPH)0JK.pSQ#
=kh?tK.meShMr8SgLbKJK=ZE=KfqZgkTK

```

Try it online!

Pretty slow, won't run on TIO for \\$n\>5\\$. Truthfully I'm not sure how to prove that this will always guess the permutation in \\$n^2\\$, but assuming you didn't pose an impossible challenge then this does it. The big idea here is we always ask about the permutation which will provide the maximum amount of information. That is, we keep a list of potential matches, and every time we ask about a permutation and receive the length of the longest common subsequence, we filter this list for permutations that agree with the information. To choose the next permutation to ask about, we look at all permutations and select the one which best splits up our potential matches.

### Explanation

First we define the "length of the longest subsequence" function.

```
M                                 # define g(G,H)
 ?&GH                        0    # if G or H are empty, return 0
     eS[                    )     # otherwise return the maximum of
        gGPH                      # g(G, H[:-1])
            gPGH                  # g(G[:-1], H)
                *qeGeHhgPGPH      # 1 + g(G[:-1], H[:-1]), but only if G[-1] == H[-1]

```

Then we guess the array.

```
                                            # implicitly assign Q = eval(input())
JK.pSQ                                      # J = K = all possible permutations of [1, ..., Q]
      #                                     # loop infinitely until error
       =kh                                  # set (and print) k to the first element of
          ?tK                               # if K has more than one element
             .m           J                 #   elements of J which minimize lambda b
                      gLbK                  #     map K over g(_, b)
                 hMr8S                      #     get how many of each element there is
               eS                           #     maximum
                           K                # else: K
                            =ZE             # set Z to the next input
                               =K           # set K to
                                 f     K    # K filtered on lambda T
                                  qZgkT     # Z == g(k, T)

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 151 bytes

Modified from @Dominic van Essen's answer.

---

Golfed version, try it online!

```
Module[{g=Range[n],F=0,d,a,b,i,j},For[i=1,i<=n,i++,For[j=1,j<=n,j++,a=DeleteCases[g,i];b=Join[a[[1;;j-1]],{i},a[[-n+j;;]]];d=f[b];If[d>F,F=d;g=b];]];g]

```

Ungolfed version

```
(* First define 'black-box' function *)
lcs[x_List, y_List] := Module[{m = Length[x], n = Length[y], L, i, j},
  L = ConstantArray[0, {m + 1, n + 1}];
  For[i = 0, i <= m, i++,
   For[j = 0, j <= n, j++,
    If[i == 0 || j == 0, L[[i + 1, j + 1]] = 0,
     If[x[[i]] == y[[j]], L[[i + 1, j + 1]] = L[[i, j]] + 1,
      L[[i + 1, j + 1]] = Max[L[[i, j + 1]], L[[i + 1, j]]]
      ]
     ]
    ]
   ];
  L[[m + 1, n + 1]]
  ]

blackBox[x_List] := Module[{n = 0},
  n = n + 1;
  Print["query ", n, " output: ", lcs[x, secret]];
  lcs[x, secret]
  ]

(* Now define our 'guess_the_array' function *)
guessTheArray[f_, n_] := Module[{g = Range[n], F = 0, d, a, b, i, j},
  For[i = 1, i <= n, i++,
   For[j = 1, j <= n, j++,
    a = DeleteCases[g, i];
    b = Join[a[[1 ;; j - 1]], {i}, a[[-n + j ;;]]];
    d = f[b];
    If[d > F, F = d; g = b];
    ]
   ];
  g
  ]

secret = RandomSample[Range[20]];
guess = guessTheArray[blackBox, Length[secret]]

```
> 1 votes

---
Tags: code-golf, interactive
---


title: Longest Valid Parentheses

text:
# Question
Title: Longest Valid Parentheses
Given a string of parentheses `(` and `)`, find the length of the longest substring that forms a valid pair of parentheses.

Valid pairs of parentheses are defined as the following:

An empty string is a valid pair of parentheses. If `s` is a valid pair of parentheses, then `(s)` is also a valid pair of parentheses. If `s` and `t` are both valid pairs of parentheses, then `st` is also a valid pair of parentheses. For example, the longest valid substring of `(()())` is `(()())`, with length 6.

Write a function or program that takes a string of parentheses as input and outputs the length of the longest valid substring.

Example:

Input: `(()())` Output: `6`

Input: `)()())` Output: `4`

Input: `()(())` Output: `6`

Input: `()(()` Output: `2`

Input: `))` Output: `0`

Input:  Output: `0`

Code golf rules:

Write a function or program that takes a string of parentheses as input and outputs the length of the longest valid substring, using as few characters as possible.

The score of your solution will be the number of characters in your code. The solution with the shortest code wins. In case of ties, the earlier submission wins.

You can assume the input string contains only the characters `(` and `)`.

# Answer
> 10 votes
# Excel (ms365), 136 bytes

Formula in `B1`:

```
=LET(x,ROW(A:A),y,SCAN(")"&A1,x,LAMBDA(a,b,SUBSTITUTE(a,"("&REPT("|",(b-1)*2)&")",REPT("|",b*2)))),MAX(ISNUMBER(FIND(REPT("|",x),y))*x))

```

The idea here is that we create a loop to iteratively replace the fundamental base of balanced paranthesis, "()". The 1st replacement is simply "||". Next we replace all occurences of "(||)", with "||||" etc, untill we can't replace any more. Finally we calculate the longest occurence of consecutive "|" characters.

Yes, 136 bytes is a lot though!

# Answer
> 6 votes
# APL(Dyalog Unicode), 46 bytes SBCS

```
(⌈/≢¨×{0(∧.≤∧=∘⊃∘⌽)+\-⌿'()'∘.=⍵}¨)⍤⊃⍳∘≢,.(,/)⊂

```

Try it on APLgolf!

```
⊃⍳∘≢,.(,/)⊂                 substrings
{0(∧.≤∧=∘⊃∘⌽)+\-⌿'()'∘.=⍵}¨ map balanced?
≢¨×                         times lengths
⌈/                          max

```

# Answer
> 6 votes
# JavaScript (Node.js), 75 bytes

```
s=>[...s].map((c,i)=>q=(p=c>'('?i-a.pop():a.push(i+~p)*0)>q?p:q,q=p=a=[])|q

```

Try it online!

Or 71 bytes if we take input as array of characters.

Let us denote the input sting as `s`. Let use denote the length of longest valid parentheses string which ends by `s[i]` as `d[i]`. Then question is asking for the greatest value in array `d`.

* If `s[i]` is `(`, `d[i]` is `0`
    + It is trivial, as the last `(` does not have a matching `)` and therefore be invalid.
* If `s[i]` is `)`, we first find out the matching `(` for it
    + If there is no matching `(` for it, `d[i]` is `0`
    + If `s[j]` is some `(` character which match `s[i]`, then `s[j..i]` is a valid parentheses string. And `d[i]=i-j+1+d[j-1]`.

To find out matching `(` for `s[i]`, we use a stack named `a` in the source code, and push `j-1-d[j-1]` into it.

# Answer
> 5 votes
# Vyxal, 7 bytes

```
ǎ~øβÞGL

```

Try it Online!

## Explained

```
ǎ~øβÞGL
ǎ       # substrings of the input
 ~øβ    # with only those with balanced brackets kept
    ÞGL # get the length of the longest substring that remains

```

# Answer
> 5 votes
# BQN, 30 bytesSBCS

```
{0⌈´∾1+/¨0(=∧∧`¨∘≤)+`¨↓¯1⋆-@}

```

Run online!

`¯1⋆-@` Map `(` to 1 and `)` to ¯1.
`+`¨↓` Take the cumulative sum of each suffix.
`0(=∧∧`¨∘≤)` For each value in each suffix, is it equal to 0 and are all preceding values non-negative?
`∾1+/¨` All 1-based indices of 1s.
`0⌈´` Take the maximum or 0 if there is no such index.

# Answer
> 5 votes
# JavaScript (ES6), 95 bytes

```
f=(s,S=s)=>s!=(s=s.split`()`.join``)?f(s,S):s?Math.max(f(S.slice(1)),f(S.slice(0,-1))):S.length

```

Try it online!

# Answer
> 4 votes
# Raku, 30 bytes

```
{m:g/(\(<~~>\))*/>>.chars.max}

```

Try it online!

Uses a recursive regex to find all sets of balanced parenthesis, then takes the maximum length of those strings.

### Explanation

```
{                            }   # Anonymous codeblock
 m:g/           /                # Find all non-overlapping matches in string
     (        )*                  # Zero or more of
      \(    \)                      # Literal brackets
        <~~>                        # Containing balanced parenthesises
                >>.chars         # Map to length of string
                        .max     # Maximum

```

# Answer
> 4 votes
# , 35 34 bytes

```
[:>./@,(#*''-:#rplc&('()';'')])\\.

```

Try it online!

*-1 thanks to ovs*

* For every every substring...
* Continually replace `()` with the empty string
* If the result is the empty string, return the length, otherwise 0
* Max of all results

# Answer
> 4 votes
# \>\<\> (Fish), 135 bytes

```
0:i:0(?v$6p1+00. ;n+1-~~.?&52~\
@$:@02.\~~1-:0>:
>0&:6g2%2*1-&+:0(?v&1-$:@$:@)?^22.
>1+$1+$:{:})?v$d1.
 .1f0v!?:-1-$/ .55/
^~~~ \0n;

```

Try it

Uses the classic paste the input on the source block for easy indexing trick

# Answer
> 3 votes
# 05AB1E, 13 bytes

```
Œʒ„()õ:õQ}éθg

```

Try it online or verify all test cases

**Explanation:**

```
Œ        # Get all substrings of the (implicit) input
 ʒ       # Filter it by:
  „()    #  Push string "()"
     õ:  #  Keep replacing "()" with "" until it's no longer possible
  õQ     #  Check if what remains is an empty string ""
 }é      # After the filter: sort the remaining strings by length
   θ     # Pop and keep the last/longest
    g    # Pop and push its length
         # (which is output implicitly as result)

```

# Answer
> 3 votes
# Retina 0.8.2, 39 bytes

```
M!`((\()|(?<-2>\)))+(?(2)^)
.
.
O^`
\G.

```

Try it online! Link includes test cases. Explanation:

```
M!`((\()|(?<-2>\)))+(?(2)^)

```

Find all nontrival substrings of balanced parentheses, using .NET's balancing groups; `?<-2>` prevents the number of matched `)`s from exceeding the number of `(`s seen so far, while the `?(2)` ensures that there are no unmatched `(`s.

```
.
.

```

Take the length of each substring in unary.

```
O^`

```

Sort in reverse order.

```
\G.

```

Output the first length or `0` if there were no matches.

# Answer
> 3 votes
# JavaScript, 130 bytes

```
s=>[...s,0].map((_,i,a)=>a.map((_,j,$,S=s.slice(i,j),b=0)=>{for(l of S)if((l==')'?--b:++b)<0)break;r=b|r>(l=S.length)?r:l}),r=0)|r

```

Try it:

```
f=s=>[...s,0].map((_,i,a)=>a.map((_,j,$,S=s.slice(i,j),b=0)=>{for(l of S)if((l==')'?--b:++b)<0)break;r=b|r>(l=S.length)?r:l}),r=0)|r

;[
  '(()())', // 6

  ')()())', // 4

  '()(())', // 6

  '()(()', // 2

  '))', // 0

  '', // 0
].forEach(s=>console.log(f(s)))
```

**Algorithm**:

Take the all substrings of string and check if it is balanced parentheses. If yes, then check if the length of substring is maximum? If yes then update the max value. Else don't change the max value

# Answer
> 3 votes
# vim, 72 bytes

```
o:s/(\(a*\))/a\1a/g<C-v><CR>@"<ESC>v0dk@":s/[()]/<C-v><CR>/g
:g/^/.!wc -c
:%!sort -nr
jdG<C-x>

```

## Annotated

```
o:s/(\(a*\))/a\1a/g<C-v><CR>@"<ESC>   # insert command that recursively replaces (a*) with aa*a as long as there are matches
v0dk@"                                # pulls the above command into register " and invokes it. (Any resemblance to the word "vodka" is entirely coincidental.)
:s/[()]/<C-v><CR>/g                   # Any parentheses that remain are invalid. Split the string into separate lines with them as delimiters
:g/^/.!wc -c                          # strlen of each line (including newline)
:%!sort -nr                           # put the largest number on top
jdG<C-x>                              # delete the rest, decrement the newline away

```

`<C-v>` is 0x16, `<C-x>` is 0x18 `<ESC>` is 0x1b, and `<CR>` is 0x0d.

Try it online!

# Answer
> 2 votes
# Japt `-h`, 14 bytes

Outputs `undefined` instead of `0` (pending confirmation).

```
ã ke"%(%)" mÊÍ

```

Try it

## 9 bytes

This version takes input as a string of `1`s & `0`s, representing `(` & `)` respectively, which the comments on the challenge would seem to allow.

```
ã keA mÊÍ

```

Try it

```
ã ke"%(%)" mÊÍ     :Implcit input of string
ã                  :Substrings
  k                :Remove items that return truthy (non-empty string)
   e               :  Recursively replace
    "%(%)"         :  RegEx /\(\)/ (or A=10, in the second version)
           m       :Map
            Ê      :  Length
             Í     :Sort
                   :Implicit out output of last element

```

# Answer
> 2 votes
# Nekomata, 16 bytes

```
qe7%3%∫:çlR≥¤#aṀ

```

Attempt This Online!

```
qe7%3%∫:çlR≥¤#aṀ
q                     Non-deterministically choose a contiguous subsequence
 e7%3%                Convert the subsequence to a list of 2's and 0's
      ∫               Take the cumsum
       :              Duplicate
        çl            Prepend 0 and get the last item
          R           Range from 1 to this number
           ≥¤         Compare the cumsum and this range;
                        fail if the two list has different length,
                        or if any item in the cumsum is less than
                        the corresponding item in the range
             #        Get the length
              a       Get all possible values
               Ṁ      Get the maximum

```

# Answer
> 2 votes
# Jelly, 13 bytes

```
ẆœṣØ(F$ÐLÐḟẈṀ

```

Try it online!

Uses Kevin Cruijssen's 05AB1E algorithm, be sure to give them an upvote!

## How it works

```
ẆœṣØ(F$ÐLÐḟẈṀ - Main link. Takes a string S on the left
Ẇ             - All contiguous sublists of S
         Ðḟ   - Filter sublists, keeping those which return [] under:
      $       -   Group the last 2 links as a monad f(W):
   Ø(         -     Yield "()"
 œṣ           -     Split W on "()"
     F        -     Flatten
       ÐL     -   Repeatedly apply f(W) until a fixed point
           Ẉ  - Lengths of those remaining
            Ṁ - Maximum

```

# Answer
> 1 votes
# Charcoal, 35 bytes

```
⊞υ⁰≔⮌υθＦＳ«≦⊕υ≡ι(⊞υ⁰¿∧⊟υυ⊞θ⌊υ⊞υ⁰»Ｉ⌈θ

```

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

```
⊞υ⁰

```

Start with no characters at the current indent level.

```
≔⮌υθ

```

Also start with a maximum balanced run length of zero.

```
ＦＳ«

```

Loop over the input characters.

```
≦⊕υ

```

Increase the characters at all depths.

```
≡ι(⊞υ⁰

```

If this is a `(` then start a new depth level. Otherwise:

```
¿∧⊟υυ

```

Remove a depth level, and if there is still at least one level left, then...

```
⊞θ⌊υ

```

... push the length of the deepest level left to the list of found balanced substring lengths, otherwise...

```
⊞υ⁰

```

.. the `)` was unbalanced, so start a new empty indent level.

```
»Ｉ⌈θ

```

Output the maximum balanced substring length found.

# Answer
> 1 votes
# Scala, 242 bytes

I first know `replaceAllLiterally` in scala, it saved several bytes.

---

Golfed version, try it online!

```
def f1(s:String):Int={f(s,s)};def f(s:String,S:String):Int={if(s!=s.replaceAllLiterally("()","")){f(s.replaceAllLiterally("()",""),S)}else if(s.nonEmpty){val left=S.dropRight(1);val right=S.drop(1);math.max(f1(left),f1(right))}else{S.length}}

```

Ungolfed version, try it online!

```
object Main {
  def f1(s: String): Int = {f(s,s)}
  def f(s: String, S: String ): Int = {
    if (s != s.replaceAllLiterally("()", "")) {
      f(s.replaceAllLiterally("()", ""), S)
    } else if (s.nonEmpty) {
      val left = S.dropRight(1)
      val right = S.drop(1)
      math.max(f1(left), f1(right))
    } else {
      S.length
    }
  }

  def main(args: Array[String]): Unit = {
    println(f1("(()())")) // 6
    println(f1(")()())")) // 4
    println(f1("()(())")) // 6
    println(f1("()(()" )) // 2
    println(f1("))"    )) // 0
    println(f1(""      )) // 0
  }
}

```

---
Tags: code-golf, balanced-string
---


title: Injectively saturate bit strings

text:
# Question
Title: Injectively saturate bit strings
It can be easily proven using Hall's marriage theorem that given fixed \\$n\\$ and \\$k\<n/2\\$, there is an injective (one-to-one) function from all \\$n\\$-bit strings with \\$k\\$ ones to \\$n\\$-bit strings with \\$k+1\\$ ones such that an input and its corresponding output differ by exactly one bit. For example, with \\$n=5,k=2\\$:

```
00011 -> 00111
00110 -> 01110
01100 -> 11100
11000 -> 11001
10001 -> 10011

00101 -> 01101
01010 -> 11010
10100 -> 10101
01001 -> 01011
10010 -> 10110

```

However, the proof is non-constructive. It would be nice to have an explicit construction.

## Task

Given a nonempty \\$n\\$-bit string with \\$k\<n/2\\$ ones, output an \\$n\\$-bit string with \\$k+1\\$ ones formed only by changing one zero in the input to one, such that the \\$\binom nk\\$ distinct inputs map to \\$\binom nk\\$ distinct outputs. You must prove that your program has this property.

The bit strings may be represented in any reasonable format, including as decimal numbers and as subsets of a specified \\$n\\$-element set. You may also simply output the index of the changed bit rather than the full string.

**The output must be deterministic** — it is not allowed to simply change the first zero in the input each time for example; there must be exactly one mapping implemented for each valid \\$(n,k)\\$ pair. The program or function must also work for all valid \\$(n,k)\\$ pairs *in theory*, and have at most polynomial time complexity in \\$n\\$.

Otherwise this is ; fewest bytes wins.

---

This question was based on this MathsSE post, which at the time of posting this question had no answers. There is now an answer by Mike Earnest giving an injection that satisfies this challenge's constraints:

* Repeatedly delete occurrences of `10` in the bitstring. This leaves a string of the form `0...01...1` with at least one zero.
* Change the rightmost remaining zero (at its original location) to a one.

```
100011010001011
XX   XXXX  XX
  001    00  11
    X    X
  00      0  11
          ^ change this to 1

```

# Answer
# Python, 51 bytes

```
lambda n,k,s:sorted(set(range(n))-s)[-sum(s)%(n-k)]

```

Attempt This Online!

This is based on hyper-neutrino's answer to the 'three other numbers' challenge. Edit: I now believe I have proved its correctness. Here's a proof by contradiction:

Assume that \\$f\\$ is not injective. Then there must exist \\$s,x,y\\$ where \\$|s|=k-1\\$, \\$f(s∪\\{x\\})=y\\$ and \\$f(s∪\\{y\\})=x\\$. Take \\$x\<y\\$ without loss of generality, then $$\sum s+y\equiv-p\_x\bmod n-k$$ $$\sum s+x\equiv-p\_y\bmod n-k$$ $$y-x\equiv p\_y-p\_x\bmod n-k$$ where \\$p\_x\\$ and \\$p\_y\\$ are the indices into the corresponding 'rest' arrays. But \\$p\_y-p\_x\\$ is just the number of integers in between \\$x\\$ and \\$y\\$ which are not in \\$s\\$. Let \\$m\\$ be the number of values in \\$s\\$ which are between \\$x\\$ and \\$y\\$. We have \\$m=(y-x)-1-(p\_y-p\_x)\\$, so \\$m\equiv-1\bmod n-k\\$. Therefore \\$n-k-1\le m\le k-1\\$, implying \\$k\ge n/2\\$. But this contradicts the initial assumption that \\$k\<n/2\\$.
> 5 votes

# Answer
# Perl 5 `-p`, 21 bytes

```
s;((1(?2)*0)|0)*\K0;1

```

Try it online!

This implements the injection described by Mike Earnest: take the longest prefix consisting of balanced pairs of `1`, `0` or unpaired `0`s, and change the rightmost unpaired `0` to `1`.
> 5 votes

# Answer
# Mathematica, 75 bytes

Modified from @user1502040's answer

```
Module[{d=-Mod[Total[s],n-k]},Sort[Complement[Rangen-1,s]][[If[d==0,1,d]]]]

```

Try it online!
> 0 votes

---
Tags: code-golf, binary, open-ended-function, restricted-complexity
---