17
\$\begingroup\$

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)
\$\endgroup\$
6
  • 3
    \$\begingroup\$ In the second example, a zero-based slice of (3,5) gives output "er", "ew", "ne", "re", "ke" and "". Is this a possible valid output? \$\endgroup\$ Commented Apr 4, 2023 at 8:40
  • \$\begingroup\$ Related \$\endgroup\$
    – Giuseppe
    Commented Apr 4, 2023 at 11:17
  • \$\begingroup\$ I would think that in the second example (3,5) would not be a valid output since earlier it is stated that "a slice cannot have a length of zero" \$\endgroup\$ Commented Apr 4, 2023 at 16:46
  • 2
    \$\begingroup\$ @CursorCoercer I phrased that poorly-what I meant was that the endpoints cannot be equal because that would be an empty slice. An empty string formed by a slice is OK. Will rephrase \$\endgroup\$ Commented Apr 4, 2023 at 18:20
  • \$\begingroup\$ Will there always be at least two strings in the list? \$\endgroup\$
    – DLosc
    Commented Apr 5, 2023 at 17:26

10 Answers 10

9
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ay, mon œil! :) (Fr: oh, my eye!) \$\endgroup\$ Commented Apr 4, 2023 at 21:07
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
7
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ -20 bytes (0-indexed inclusive range) This loops through size and start point guaranteeing first element is shortest possible \$\endgroup\$ Commented Apr 5, 2023 at 5:18
3
\$\begingroup\$

R, 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.

\$\endgroup\$
3
  • \$\begingroup\$ Your assumption is fine, it is what I was going for; I just made a mistake with the test cases. \$\endgroup\$ Commented Apr 4, 2023 at 11:08
  • \$\begingroup\$ -2 bytes \$\endgroup\$
    – pajonk
    Commented Apr 4, 2023 at 19:21
  • \$\begingroup\$ @pajonk - well spotted. Thanks! \$\endgroup\$ Commented Apr 4, 2023 at 21:01
3
\$\begingroup\$

R, 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).

\$\endgroup\$
4
  • \$\begingroup\$ Fails for "abcxxxd","aocxxxe","aboxxxf","obcxxxg" (result should be 7 7)... \$\endgroup\$ Commented Apr 4, 2023 at 22:45
  • \$\begingroup\$ ...but fixed for +2 bytes. \$\endgroup\$ Commented Apr 4, 2023 at 22:47
  • \$\begingroup\$ (and \(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)} would still work for 103 bytes in R version 4.1) \$\endgroup\$ Commented Apr 4, 2023 at 22:50
  • \$\begingroup\$ @DominicvanEssen thanks for the fix! \$\endgroup\$
    – pajonk
    Commented Apr 5, 2023 at 4:25
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 50 49 bytes

WS⊞υι≔⌈EυLιθF⊕θFθ¿¬ⅉ«≔Eυ✂λκ⁺κι¹η¿∧⌊η⬤η⁼¹№ηλI⟦κ⁺κι

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

WS⊞υι

Input the strings.

≔⌈EυLιθ

Get the length of the longest string.

F⊕θFθ

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.

≔Eυ✂λκ⁺κι¹η

Get the current set of slices.

¿∧⌊η⬤η⁼¹№ηλ

If they are valid and unique, then...

I⟦κ⁺κι

... output the start and end indices.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
1
\$\begingroup\$

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)
  }
}

\$\endgroup\$
2
  • \$\begingroup\$ Wouldn't f work as the function name instead of shortestDistinguishableSlice? \$\endgroup\$
    – The Thonnu
    Commented Apr 8, 2023 at 14:20
  • \$\begingroup\$ 161 \$\endgroup\$
    – The Thonnu
    Commented Apr 8, 2023 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.