| Bytes | Lang | Time | Link |
|---|---|---|---|
| 038 | Uiua | 241024T195157Z | noodle p |
| nan | Scala | 230408T141659Z | 138 Aspe |
| 021 | Vyxal | 230404T083339Z | The Thon |
| 118 | Julia 1.0 | 230404T213957Z | Ashlin H |
| 020 | Pyth | 230404T165640Z | CursorCo |
| 049 | Charcoal | 230404T091903Z | Neil |
| 103 | R | 230404T193402Z | pajonk |
| 106 | R | 230404T084747Z | Dominic |
| 083 | JavaScript ES6 | 230404T003618Z | Arnauld |
| 015 | Jelly | 230404T004221Z | Unrelate |
| 131 | Python | 230404T012237Z | Youserna |
Scala, 188 161 bytes
saved 27 bytes thanks to comment.
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)
}
}
Vyxal, 21 22 21 bytes
vf0ÞṪÞKƛKƛ∩Þu;;∩1ÞḟṘ¦
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
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)])
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
Pyth, 25 20 bytes
-5 bytes by using .C
.M-FZf{I:R.*TQ.CUsQ2
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
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.
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).
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)
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.
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)
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
Jelly, 19 15 bytes
z0ZQƑ$ƤÐƤZœi1UÄ
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!
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])
Most likely can be golfed down further.